简单排序算法代码

80 阅读 0 评论 53 点赞

我是靠谱客的博主舒适店员，这篇文章主要介绍简单排序算法代码，现在分享给大家，希望可以做个参考。

简单排序算法

插入排序

将无序子序列的元素依次通过比较插入有序子序列中

适用于基本正向有序/n较小的情况

选择排序

第i次选择时 “选择”序列中第i小的记录，并把该记录放到序列的第i个位置上
相当于每一趟都扫描剩余的序列元素并将最小值放到剩余序列的第一个位置已选择过的元素不再进行扫描
适用于地址排序
template <typename T>
void select_sort(T arr[], int len ) {
int min = 0;
for (int sub = 0; sub < len; sub++) {
int min = sub; //记录最小值的下标
for (int sub1 = sub; sub1 < len; sub1++) {
if (arr[sub1] < arr[min]) min = sub1;
}
std::swap(arr[sub], arr[min]);
}
}

算法稳定性

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

希尔排序(ShellSort)

通过非相邻元素的比较触发插入排序的最佳情况时间复杂度为O(nlogn)

//以3为倍数 对整体进行希尔排序
template <typename T>
void shell_sort(T array[], int length) {
int h = 1;
while (h < length / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < length; i++) {
for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
std::swap(array[j], array[j - h]);
}
}
h = h / 3;
}
}
// bk's version
template <typename T>
void ShellSort(T array[], int length, int gap) {
int needChange = 0;
if (length / gap <= 1) needChange = 1;
else needChange = length / gap - 1; //将数组划分为n个区间段 那么起始位置需要改变(n - 1)次
int compare1 = 0, compare2 = gap;
while (needChange--) {
int count = 1;
while (count <= gap && compare2 < length) { //每一次的比较次数取决于间距 即两个相邻区间间隔为gap的元素进行交换判定 同时请注意边界
if (array[compare1] >= array[compare2])
std::swap(array[compare1], array[compare2]);
compare1++; compare2++;
count++;
}
}
}

快速排序

将数列划分为两部分递归进行快速排序

void quickSort(int arr[], int startPos, int endPos) {
if (startPos >= endPos) return;
int left = startPos;
int right = endPos;
int key = arr[startPos]; //作为比较值
while (true) { //此方法为左右两指针遍历数组
while (arr[left] <= key && left < endPos) left++; //从左往右寻找比key大的元素
while (arr[right] >= key && right > startPos) right--; //从右往左寻找比key小的元素
if (left >= right) break; //如果左右指针相对位置发生变化 则break
else std::swap(arr[left], arr[right]);
}
/*
一定要与对侧指针交换元素 比如说将左边第一个元素设为key 那么与右指针交换元素
同理如果将右边第一个元素设为key 那么与左指针交换元素
原因1: 同侧指针在极端情况下将越过自身 如序列3 5 13情况 如果key与同侧指针交换元素 排序后结果为5 3 13
原因2: 对侧指针将保证对侧的元素均比key值大(小)；同侧元素因为结束条件是左右指针交换了位置 因此同侧元素排列顺序的正确性也得到了保证
*/
std::swap(arr[startPos], arr[right]);
quickSort(arr, startPos, right - 1);
quickSort(arr, right + 1, endPos);

二路归并

采用分治法，是一种建立在归并操作上的一种有效、稳定的算法。
即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

template <typename T>
void merge(T arr[], T temp[], int leftPos, int rightPos, int rightEnd) {
int leftEnd = rightPos - 1; //计算左边结束下标
int tempPos = leftPos; //起点为左序列的起点
int numEle = rightEnd - leftPos + 1; //计算合并序列的总元素个数
while (leftPos <= leftEnd && rightPos <= rightEnd) { //相当于比较两个指针所指向的元素大小 将较小的元素放入临时数组中
if (arr[leftPos] <= arr[rightPos])
temp[tempPos++] = arr[leftPos++];
else temp[tempPos++] = arr[rightPos++];
}
while (leftPos <= leftEnd) { //考虑到左序列有剩余元素
temp[tempPos++] = arr[leftPos++];
}
while (rightPos <= rightEnd) { //考虑到右序列有剩余元素
temp[tempPos++] = arr[rightPos++];
}
/* 将temp复制到arr */
for (int times = 1; times <= numEle; times++) {
arr[rightEnd] = temp[rightEnd];
rightEnd--;
}
return;
}
template <typename T>
void mergeSort(T arr[], T temp[], int left, int right) { //归并排序是基于分治思想的一种排序算法
if (left < right) {
int mid = (left + right) / 2;
/* 分治中的"分" */
mergeSort(arr, temp, left, mid); //使左序列变为有序序列
mergeSort(arr, temp, mid + 1, right); //使右序列变为有序序列
/* 分治中的"治" */
merge(arr, temp, left, mid + 1, right); //将两个有序序列进行归并
}
return;
}

堆排序

首先建立大顶堆，然后将堆顶的元素取出，作为最大值，与数组尾部的元素交换，并维持残余堆的性质；

之后将堆顶的元素取出，作为次大值，与数组倒数第二位元素交换，并维持残余堆的性质；

以此类推，在第n-1次操作后，整个数组就完成了排序。

template <typename T>
void sift_down(T arr[], int start, int end) {
/* 对于堆排序 我们关心的是根结点与较大子结点的大小关系 */
int parent = start;
int child = parent * 2 + 1;
while (child <= end) {
if (child + 1 <= end && arr[child] < arr[child + 1]) child++; //取出较大的子结点
if (arr[parent] >= arr[child]) return;
else {
std::swap(arr[child], arr[parent]);
/* 孩子结点与父结点交换位置 */
parent = child;
child = parent * 2 + 1;
}
}
}
template <typename T>
void heap_sort(T arr[], int len) {
for (int sub = (len - 1 - 1) / 2; sub >= 0; sub--) sift_down(arr, sub, len - 1); //层序遍历建堆
for (int sub = len - 1; sub >= 1; sub--) {
std::swap(arr[0], arr[sub]); //堆顶元素与数组尾部元素交换
sift_down(arr, 0, sub - 1); //找出最大值
}
}

基数排序

将关键码看成若干个关键字符合而成而后对每个关键字进行计数排序

前一次排序是为后一次排序服务是在相同的关键字中确定相对的大小顺序排序是分门别类的

桶排序按下列步骤进行：

设置一个定量的数组当作空桶；
遍历序列，并将元素一个个放到对应的桶中；
对每个不是空的桶进行排序；
从不是空的桶里把元素再放回原来的序列中。

int maxBit(int data[], int len) { //返回最大元素的位数
int maxData = data[0];
for (int sub = 1; sub < len; sub++) { //找最大值
if (data[sub] > maxData) maxData = data[sub];
}
int digit = 1;
while (maxData >= 10) { //计算位数
maxData /= 10;
digit++;
}
return digit;
}
void radixSort(int data[], int len) {
int* bucket = new int[len]; //创建临时数组记录数据
int* count = new int[10]; //计数器 统计最低位从0~9的元素个数分布情况
int divisor = 1; //每一轮的除数
int subBucket = 0, subCount = 0; //分别作为桶与计数器的下标
int LSD = 0; //Least Significance Digit
int frequency = maxBit(data, len); //为进行几轮循环提供依据
for (int times = 1; times <= frequency; times++) {
for (subCount = 0; subCount < 10; subCount++) count[subCount] = 0; //每一轮计数器q
for (subBucket = len - 1; subBucket >= 0; subBucket--) { //计数器开始计数
LSD = (data[subBucket] / divisor) % 10; //取最低数的数字
count[LSD]++;
}
/* 重定位 将count位置与bucket位置进行一一对应的映射 可以理解为二维向一维展开 */
for (subCount = 1; subCount < 10; subCount++) count[subCount] += count[subCount - 1];
for (subBucket = len - 1; subBucket >= 0; subBucket--) {
LSD = (data[subBucket] / divisor) % 10;
bucket[count[LSD] - 1] = data[subBucket]; //将原本data中的元素重定位至bucket中
count[LSD]--;
}
for (subBucket = 0; subBucket < len; subBucket++)
data[subBucket] = bucket[subBucket];
divisor *= 10;
}
}