1.直接插入排序

• 稳定排序，最坏时间复杂度O(N^2)，最好O(N)

//直接插入排序
void InsertSort(int* a, int n)
{//从下标为1处开始for (int i = 1; i < n; i++){int tmp = a[i];int end = i - 1;while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}//因从头开始进行插入比较，即保证了待插入值之前的元素已经是有序的了//故后部的插入比较若已满足排序要求，则直接跳出循环，并将与tmp比较//的end位置的后一位置为tmpelse{break;}}a[end + 1] = tmp;}
}

 
 

2. * 希尔排序

• 分组插排，先进行预排序，使目标数组接近有序(对间隔为gap的数进行插入排序)
• 再直接插入排序(gap=1)
• gap的变化一般为 gap/=2 或 gap=gap/3+1
• 不稳定排序，时间复杂度O(N*1.3)

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){//控制gapgap /= 2;	for (int i = gap; i < n; i++){//下标为i处的tmp值与在其之前每间隔gap的元素比较//不满足排序顺序则后移//且每次都是与之前的元素比较，以此能保证//每次tmp值比较的停止位置之前都是有序的int tmp = a[i];int end = i - gap;while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}//比较满足排序要求则停止，将与tmp比较的end位置的后一位置为tmpa[end + gap] = tmp;}}
}

关于希尔排序的时间复杂度

• gap变化到1，执行次数为log2N或log3N
• 每个gap内的执行次数量级都为N，系数可能不同，
• gap变化至1时，相当于直接插入排序，并且经过预排序，已经为最好情况，量级为N
• 结论：希尔排序的时间复杂度为 O(N^1.3)，（优于O(N*logN)）

 

3.选择排序

• 可单边遍历，也可两边同时遍历
• 两边遍历时，每次遍历找到的最小值放左边，最大值放右边
• 注意考虑left于maxi 或 right 与 mini 重叠时要进行修正
• 不稳定排序，时间复杂度为O(N^2)

//选择排序
void SelectSort(int* a, int n)
{单边找小//int left = 0;////while (left < n)//{//	int mini = left;//	//注意每次遍历起点为left//	for (int i = left; i < n; i++)//	{//		if (a[i] < a[mini])//		{//			mini = i;//		}//	}//	Swap(&a[left++], &a[mini]);//}//双边同时找//每次遍历范围为[left, right]int left = 0, right = n - 1;while (left < right){int mini = left, maxi = right;for (int i = left; i <= right; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[left++], &a[mini]);//因为这里先交换了left和mini，可能maxi与left重叠//直接交换maxi处的最大值已经通过left被交换到mini了//所以考虑此情况需要重置maxi到已交换到的mini处if (left == maxi){maxi = mini;}Swap(&a[right], &a[maxi]);}}

 

4. * 堆排序

• 先建堆，再调堆
• 现在原数组上构建出堆，排升序建小堆，排降序建大堆，
• 建好堆再将堆顶与尾部数据交换，同时有效位减一，对交换后的堆顶进行向下调整，
• 若为排升序建小堆，第一次交换并调整后，尾部为最大值，堆顶为次大值，以此循环，完成排序
• 不稳定排序，时间复杂度为O(N*logN)

void AdjustUp(int* a, int child)
{int parent = (child - 1) / 2;while (child > 0){if (a[child] > a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}void AdjustDown(int* a, int parent, int n)
{int child = 2 * parent + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){child++;}if (a[parent] < a[child]){Swap(&a[parent], &a[child]);}elsebreak;parent = child;child = 2 * parent + 1;}
}
void HeapSort(int* a, int n)
{向上调整建堆//for (int i = 1; i < n; i++)//{//	AdjustUp(a, i);//}//向下调整建堆for (int i = n - 1; i >= 0; i--){AdjustDown(a, (i - 1) / 2, n);}int end = n;//首尾交换向下调整排序for (int i = n - 1; i >= 0; i--){Swap(&a[i], &a[0]);end--;AdjustDown(a, 0, end);}
}

 

5.冒泡排序

• 稳定排序，时间复杂度为O(N^2)

void BubbleSort(int* a, int n)
{for (int j = 0; j < n - 1; j++){for (int i = 1; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);}}}
}

 
 

6. * 快速排序

6.1递归快排

6.1.1 hoare版

• 将头位置的元素作为基准值
• 小于基准值的放左边，大于基准值的放右边
• 最后将基准值放至比较结束位置
• 根据基准值最后位置将数组分割成两个区间(剔除基准值)
• 对分割后的区间进行分治
• 不稳定排序，时间复杂度为 O(N*logN)
• 类似二叉树的前序，递归深度为 logN
  

//hoare版
int PartSort1(int* a, int left, int right)
{//keyi位置的值会影响快排效率//如果a[keyi]本身最大或最小，//为最坏情况，时间复杂度O(N2)//为保证较高效率，决定keyi时//尽量保证其为一个适中对值，将其放到left位置处//优化1.生成一个随机位置keyi/*if (left < right){int randi = left + (rand() % (right - left));Swap(&a[left], &a[randi]);}*///优化2.三数取中int mid = GetMidPos(a, left, right);Swap(&a[left], &a[mid]);//优化方案使用一组有序的用例进行测试//有序用例的数据个数如果较大，会栈溢出//可在release版本下测试较多的数据int keyi = left;while (left < right){//left和right每次移动都要判断left<rightwhile (left < right && a[right] >= a[keyi]){right--;}while (left < right && a[left] <= a[keyi]){left++;}//交换同时不同各自向中移动，下次循环自会移动Swap(&a[left], &a[right]);}Swap(&a[keyi], &a[left]);return left;
}

 

6.1.2 挖坑法

• 记录首个数据key
• 右边先走找到小将其填入坑，同时其所处位置成为坑
• 左边后走找到大将其填入坑，同时其所处位置成为坑
• 左后L与R相遇在坑上，最后向此坑中填入key
• 返回最后的相遇位置作为分割区间点
  

//挖坑法
int PartSort2(int* a, int left, int right)
{//三数取中int mid = GetMidPos(a, left, right);Swap(&a[left], &a[mid]);//优化方案使用一组有序的用例进行测试//有序用例的数据个数如果较大，会栈溢出//可在release版本下测试较多的数据int key = a[left];int pit = left;while (left < right){while (left < right && a[right] >= key){right--;}a[pit] = a[right];pit = right;while (left < right && a[left] <= key){left++;}a[pit] = a[left];pit = left;}a[pit] = key;return pit;
}

 

6.1.3 前后指针法

• cur向右找小，找到 prev++，cur与prev 交换值
• cur 没找到，cur++
• cur 加至越界，跳出循环，key值与此时的prev交换
• 返回最后的prev 作为分割区间点

//前后指针法
int PartSort3(int* a, int left, int right)
{//三数取中int mid = GetMidPos(a, left, right);Swap(&a[left], &a[mid]);//优化方案使用一组有序的用例进行测试//有序用例的数据个数如果较大，会栈溢出//可在release版本下测试较多的数据int keyi = left;int prev = left, cur = left;while (cur <= right){if (a[cur] >= a[keyi]){cur++;}else{Swap(&a[++prev], &a[cur++]);}}Swap(&a[keyi], &a[prev]);return prev;
}

6.1.4 关于每个区间操作的结束位置总是小于key

• 因为是右边先走，所以能保证相遇位置能小于左边的 key，即右边向左找小的停止位置一定比key小
• 有几种R停止的情况
  • R 找到小，L 没找到大，直接遇到 R
  • R 没找到小，直接遇到 L，相遇点小于 key，或者直接走到key

6.1.5 关于有序原数据的效率优化

• 如果原数据本身是有序的，快速排序的时间复杂度会达到 O(N^2)
• 优化方案使用一组有序的用例进行测试
• 有序用例的数据个数如果较大，会栈溢出
• 可在release版本下测试较多的数据，(debug模式下数据个数为10000都会栈溢出)

Release模式下测试数据个数为100000的有序数组

 

两种优化方式

//优化1.生成一个随机位置keyiif (left < right){int randi = left + (rand() % (right - left));Swap(&a[left], &a[randi]);}优化2.三数取中int mid = GetMidPos(a, left, right);Swap(&a[left], &a[mid]);//优化方案使用一组有序的用例进行测试//有序用例的数据个数如果较大，会栈溢出//可在release版本下测试较多的数据

同样条件下优化后测试

• 三数取中取到的key一定是一个较为适中的值
• 而随机选key有可能仍然是最值
• 相对来说，三数取中法优化更彻底

 

6.2 非递归快排

• 非递归的优化目的主要是因为递归快排如果处理较多数据，递归的层次太深，很容易导致栈溢出
• 将递归改为循环，并且运用栈实现快排的非递归版

非递归快排用过栈实现

//快速排序非递归
void QuickSortNor(int* a, int left, int right)
{//创建栈ST st;StackInit(&st);st.a = (int*)malloc(sizeof(int) * (right - left + 1));if (st.a == NULL){printf("malloc fail\n");exit(-1);}//首先将数组头尾压入栈StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){//依次取栈顶作为一次排序的区间int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int keyi = PartSort3(a, begin, end);//将[begin,keyi-1] [keyi+1,end]区间的边界(若存在)入栈//先入右边界，后入左边界，以确保拿到栈顶先处理左边界if (keyi + 1 < end){StackPush(&st, end);StackPush(&st, keyi + 1);}if (keyi - 1 > begin){StackPush(&st, keyi - 1);StackPush(&st, begin);}}
}

 
 

7. * 归并排序

• 先分割，在由下至上逐层归并
• 每次归并结果放入一个临时数组
• 最后将临时数组的数据拷贝到原数组

7.1 递归版归并

void _MergeSort(int* a, int left, int right, int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2;//分治[left, mid] [mid+1, right]_MergeSort(a, left, mid, tmp);_MergeSort(a, mid + 1, right, tmp);int i = left;int j = mid+1;int k = 0;//某一半区间全部放入了tmp，跳出循环while (i <= mid && j <= right){if (a[i] < a[j]){tmp[k++] = a[i++];}else{tmp[k++] = a[j++];}}//某一半区间全部放入了tmp，将另一半剩余元素全部移入tmpwhile (j <= right){tmp[k++] = a[j++];}while (i <= mid){tmp[k++] = a[i++];}//将tmp中归并后的有序数组按原位置拷贝到原数组memcpy(a + left, tmp, sizeof(int) * (right - left + 1));}void MergeSort(int* a, int n)
{//开辟一块临时空间暂存归并后的有序数组int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail\n");exit(-1);}int left = 0;int right = n - 1;_MergeSort( a, left, right, tmp);
}

 

7.2 非递归版归并

• 非递归的归并排序主要是要处理越界问题
• 如果产生越界，根据情况将某一边界进行重置
  
• 两种实现方法，基本思想一致，只是拷贝的时机不一样，第二种方法可简化到两种情况
• 一种是梭哈版：一个gap循环内的多组数归并完拷贝一次，
• 一种非梭哈版：一个gap循环内的一组数归并完随即拷贝

void MergeSortNoR(int* a, int n)
{//梭哈版--一个gap循环内的多组数归并完拷贝一次int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail\n");exit(-1);}int gap = 1;while (gap < n){int j = 0;for (int i = 0; i < n; i += 2 * gap){//控制归并的两部分int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;//处理几种越界问题，根据发生前后（调试发现）if (begin2 >= n){end2 = n - 1;}if (end2 >= n){end2 = n - 1;}if (end1 >= n){end1 = n - 1;}//[begin1, end1] [begin2, end2]while (begin1 <= end1 && begin2 <= end2){//这行代码决定排序是否稳定， <= 则稳定//若相等，前面的数先放，可确保相等数据相对位置不变）if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}}memcpy(a, tmp, sizeof(int) * n);gap *= 2;}//非梭哈版，一个gap循环内的一组数归并完随即拷贝int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){printf("malloc fail\n");exit(-1);}int gap = 1;while (gap < n){int j = 0;for (int i = 0; i < n; i += 2 * gap){//控制归并的两部分int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;printf("[%d, %d][%d, %d] ", begin1, end1, begin2, end2);//处理几种越界问题，根据发生前后（调试发现）if (end1 >= n || begin2 >= n){break;}if (end2 >= n){end2 = n - 1;}/*if (begin2 >= n){end2 = n - 1;}if (end2 >= n){end2 = n - 1;}if (end1 >= n){end1 = n - 1;}*///[begin1, end1] [begin2, end2]while (begin1 <= end1 && begin2 <= end2){//这行代码决定排序是否稳定， <= 则稳定//若相等，前面的数先放，可确保相等数据相对位置不变）if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}//拷贝memcpy(a + i, tmp + i, sizeof(int)* (end2 - i + 1));}printf("\n");gap *= 2;}
}

  

8. 非比较排序

计数排序

• 先统计每个数据出现的次数
• 将次数相对映射至计数数组，(根据原数据范围实现相对映射)
• 根据计数数组重写原数组
• 适用于范围不大且数据集中的整型排序
• 时间复杂度为 O(N+range)，range 为原数据的分布范围

void CountSort(int* a, int n)
{//相对映射int min = a[0], max = a[0];for (int i = 0; i < n; i++){if (a[i] < min){min = a[i];}if (a[i] > max){max = a[i];}}int range = max - min + 1;int* count = (int*)calloc(range, sizeof(int));if (count == NULL){printf("calloc fail\n");exit(-1);}//计数for (int i = 0; i < n; i++){count[a[i] - min]++;}//重写int i = 0;for (int j = 0; j < range; j++){while (count[j]--){a[i++] = j + min;}}free(count);count = NULL;
}

 

排序算法时间复杂度和稳定性

稳定性：排序后相等元素的相对位置是否改变