目录前言一、排序算法1、归并排序2、归并非递归3、计数排序4、排序算法复杂度及稳定性分析为什么快排比归并快快排快在哪里归并排序的优势C 标准库怎么选总结前言本文将继续介绍两种高效的排序算法——归并排序、计算排序。归并排序在一些场合下如外部排序非常有效当数据量非常大且无法全部加载到内存时可以将其分块处理。而计数排序是一种非比较排序算法适用于特定范围内的整数排序在许多数情况下计算排序可以秒杀我们介绍过的所有排序。一、排序算法1、归并排序| 算法思路归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列间段有序。动图演示代码实现//子函数void_MergeSort(int*arr,int*tmp,intbegin,intend){if(beginend){return;}intmid(beginend)/2;//[begin, mid] [mid 1, end]_MergeSort(arr,tmp,begin,mid);_MergeSort(arr,tmp,mid1,end);intbegin1begin,end1mid;intbegin2mid1,end2end;intibegin;while(begin1end1begin2end2){if(arr[begin1]arr[begin2]){tmp[i]arr[begin1];}else{tmp[i]arr[begin2];}}while(begin1end1){tmp[i]arr[begin1];}while(begin2end2){tmp[i]arr[begin2];}memcpy(arrbegin,tmpbegin,(end-begin1)*sizeof(int));}//归并排序voidMergeSort(int*arr,intn){int*tmp(int*)malloc(n*sizeof(int));if(tmpNULL){perror(malloc fail);return;}_MergeSort(arr,tmp,0,n-1);free(tmp);tmpNULL;}归并排序有几个需要特别注意的点分割区间一定要按[begin, mid] [mid 1, end]分不然会导致死循环memcpy(arr begin, tmp begin, (end - begin 1) * sizeof(int));一定是归并一组拷贝一组因为如果存在越界的情况还整体拷贝肯定会出错归并排序算法的时间复杂度是O(N*logN)空间复杂度是O(N).2、归并非递归递归改非递归有两种办法一种是用栈模拟一种是用循环处理。上篇文章中快排非递归我们是利用栈实现的但是归并的非递归使用栈解决不了因为快排的递归过程是一个类似前序遍历的过程而归并是一个类似后续的过程它是先将区间循环分割成只有一个数据再反向进行归并栈是做不到这一点的。所以归并的非递归我们考虑用循环来实现。我们可以直接将原数组一一归并再二二归并再四四归并……//归并非递归voidMergeSortNonR(int*arr,intn){int*tmp(int*)malloc(n*sizeof(int));if(tmpNULL){perror(malloc fail);return;}//gap是每组归并数据的个数intgap1;while(gapn){//i表示每组归并的起始位置for(inti0;in;i2*gap){intbegin1i,end1igap-1;intbegin2igap,end2i2*gap-1;intji;while(begin1end1begin2end2){if(arr[begin1]arr[begin2]){tmp[j]arr[begin1];}else{tmp[j]arr[begin2];}}while(begin1end1){tmp[j]arr[begin1];}while(begin2end2){tmp[j]arr[begin2];}//memcpy(arri,tmpi,(end2-i1)*sizeof(int));}gap*2;//一一归二二归四四归}free(tmp);tmpNULL;}memcpy(arr i, tmp i, (end2 - i 1) * sizeof(int));for (int i 0; i n; i 2 * gap)int begin2 i gap, end2 i 2 * gap - 1;但是上面的代码还不完善仅限2的次方个数的数据归并如果不是2的次方个数则会越界。越界无非下面三种情况[begin1, end1] [begin2,end2][begin1, end1] [begin2,end2][begin1,end1] [begin2,end2]其中第二种和第三种可以归为一类因为begin2越界说明我们需要排序的数据已经排好序了越界的部分不是我们的区间我们根本不用管直接退出循环就行了。而第一种情况只需要处理一下就好让end2变成n - 1就行了。代码示例//归并非递归voidMergeSortNonR(int*arr,intn){int*tmp(int*)malloc(n*sizeof(int));if(tmpNULL){perror(malloc fail);return;}//gap是每组归并数据的个数intgap1;while(gapn){//i表示每组归并的起始位置for(inti0;in;i2*gap){intbegin1i,end1igap-1;intbegin2igap,end2i2*gap-1;//第二组都越界不存在不是我们需要排序的数据if(begin2n){break;}//begin2没越界end2越界只需要修正一下就好if(end2n){end2n-1;}intji;while(begin1end1begin2end2){if(arr[begin1]arr[begin2]){tmp[j]arr[begin1];}else{tmp[j]arr[begin2];}}while(begin1end1){tmp[j]arr[begin1];}while(begin2end2){tmp[j]arr[begin2];}//归并一次拷贝一次memcpy(arri,tmpi,(end2-i1)*sizeof(int));}gap*2;}free(tmp);tmpNULL;}3、计数排序计数排序又称为鸽巢原理是对哈希直接定址法的变形应用。其排序步骤为1. 统计相同元素出现的次数将统计到的次数作为count数组以元素值对应下标处的值2. 根据统计的结果将序列回收到原来的序列中3. 动态开辟的count数组要初始化为全0本质利用count数组的自然序号排序为了保证开辟大小合适的count数组我们可以用待排数据中最大值减最小值加一的方法来确定一个合适的范围max - min 1。然后再用元素值减去最小值的方法来和count数组形成相对映射关系arr[i] - min得到的值是几就在数组对应下标位置递增。最后一步排序的时候不要忘了在原数组中插入的值还要加上最小值并且count数组中下标对应位置的值是几就循环几次如果对应位置是0的话说明原数组没有这个下标数就不进入循环。大致思想如下代码如下//计数排序voidCountSort(int*arr,intn){intminarr[0];intmaxarr[0];for(inti1;in;i){if(arr[i]min){minarr[i];}if(arr[i]max){maxarr[i];}}intrangemax-min1;int*count(int*)calloc(range,sizeof(int));if(countNULL){perror(calloc fail);return;}//统计次数for(inti0;in;i)//遍历原数组{count[arr[i]-min];}//排序intj0;for(inti0;irange;i)//遍历count数组{while(count[i]--){arr[j]imin;}}free(count);countNULL;}计数排序的时间复杂度为O(N range)相比较前几种排序算法计数排序效率是非常高的但速度快的同时也有空间消耗计数排序的空间复杂度为O(range)所以计数排序也算是拿空间换时间。计数排序虽然相对其他排序算法快且稳定但也存在一些缺陷只能排整数不能排浮点数要求数据比较集中不然空间开销太大4、排序算法复杂度及稳定性分析稳定性如果待排序数据中有多个相同的的数据若经过排序这些相同的数据相对位置保持不变则称这种排序算法是稳定的。排序算法时间复杂度空间复杂度稳定性插入排序O(N^2)O(1)稳定希尔排序O(N^1.3)O(1)不稳定选择排序O(N^2)O(1)不稳定堆排序O(N*logN)O(1)不稳定冒泡排序O(N^2)O(1)稳定快速排序O(N*logN)O(logN)不稳定归并排序O(N*logN)O(N)稳定计数排序O(N range)O(range)稳定为什么快排比归并快快排平均情况下比归并快核心原因在于“内存访问的局部性”和“常量因子”而不是时间复杂度。两者的时间复杂度都是 O(N log N)但工程实践中快排通常能快 2~3 倍。维度快速排序归并排序时间复杂度平均 O(N log N)稳定 O(N log N)空间复杂度O(log N)递归栈O(N)额外数组比较次数~1.39 N log₂ N~1.0 N log₂ N比快排少数据移动次数少原地交换多需要拷贝到临时数组再拷贝回来缓存命中率高顺序扫描 局部交换低两个数组来回跳快排快在哪里原地排序内存访问局部性好快排的partition是在原数组上扫描和交换访问的是连续内存区域CPU 缓存命中率高。归并排序需要申请额外的O(N)数组在合并时从原数组读到临时数组再从临时数组写回原数组——数据来回拷贝缓存更容易失效。// 快排交换两个元素原地if(a[i]pivot)swap(a[i],a[left]);// 归并拷贝到临时数组tmp[i]a[left];// 最后还要拷贝回来a[i]tmp[i];一次归并 两次拷贝读写快排 一次交换。交换只涉及两个位置拷贝涉及整个区间。比较操作更简单快排的核心操作是a[i] pivot——单个比较。归并排序的核心是a[i] a[j]——两个子数组之间的比较。虽然都是比较但快排的比较更直接分支预测更容易成功。不产生额外内存分配归并排序每次递归都需要O(N)的临时数组频繁分配/释放内存或需要预先分配一个全局 buffer 复用。快排只用递归栈几乎不分配额外内存。常数因子更小快排的比较次数虽然略多约 1.39N log₂N vs 归并的 1.0N log₂N但数据移动次数少得多。在绝大多数 CPU 上数据移动比比较更昂贵因为涉及内存读写。归并排序的优势既然归并慢为什么还需要它场景归并胜出稳定排序归并是稳定的快排不稳定链表排序归并不需要额外数组改指针就行快排无法随机访问最坏情况保证归并稳定 O(N log N)快排最坏 O(N²)虽然概率极低外排序归并适合磁盘/网络等外部排序C 标准库怎么选// C std::sort 的实现std::sort(a.begin(),a.end());// 混合排序Introsort快排 堆排 插排C 的std::sort不是纯快排而是Introsort内省排序用快排递归深度超过阈值时自动切换为堆排序保证 O(N log N)。当子区间很小 16时用插入排序——因为插入排序对小数组更快缓存友好 无递归。这种混合策略兼顾了快排的速度和堆排的最坏情况保证。总结这些排序算法各有千秋在某些特定的情况下某个算法的性能尤为突出在一些复杂的排序中为了追求性能往往使用混合排序这使得性能大大提高。