秩序之舞——排序算法中的数字星河

一引言在计算机科学的世界里排序是最基础、也最重要的核心算法之一。无论是日常开发中的列表数据整理、数据库查询的结果规整还是电商平台商品价格、销量的智能排行亦或是机器学习、大数据处理中的数据预处理环节排序算法都无处不在默默支撑着程序高效运转。排序的本质就是将一组无序的数据元素按照既定规则升序、降序、自定义权重重新排列为有序序列。而市面上并没有万能的排序算法有的实现简单却效率偏低有的时间复杂度优异但逻辑晦涩有的适合小规模数据有的在海量数据场景下才能发挥优势。冒泡、选择、插入、希尔、归并、快速排序…… 这些经典排序算法不仅是编程入门的必学知识点更是面试高频考点也是我们理解时间复杂度、空间复杂度、稳定性三大算法核心概念的最佳载体。本文就带大家从零拆解常见经典排序算法从底层原理、代码实现、复杂度分析到适用场景逐一梳理帮你彻底吃透排序逻辑既能手写源码也能在实际开发中精准选型。二冒泡排序以及鸡尾酒排序这是许多入门者都信手拈来的冒泡排序默认排升序my_swapa函数在此处实现下面的排序算法就不再对此作过多赘述了)void my_swap(int* a, int* b) { int temp *a; *a *b; *b temp; } void bubbleSort(int* a, int size) { for (int i 0; i size - 1; i) { int flag 0; for (int j 0; j size - 1 - i; j) { if (a[j] a[j 1]) { my_swap(a[j], a[j1]); flag 1; } } if (flag 0)break; } }注释其中flag相关语句是对算法的优化每次交换就改变flag的值当一趟排序下来flag的值没有改变就说明此趟排序中数组已经有序了就停止。其算法作用示意图如下但是这样的冒泡排序还是有一定的缺陷排序顺序只能单向走小元素在最右侧时移动极慢乌龟问题因此我们引入鸡尾酒排序。鸡尾酒排序 双向冒泡排序普通冒泡从左往右一趟只把最大值冒泡到最右边鸡尾酒排序先左→右再右→左来回双向遍历像调酒来回摇晃杯子一样所以叫鸡尾酒排序相关算法原理1. 第一轮从左向右冒泡把最大值推到数组末尾2. 第二轮从右向左冒泡把最小值推到数组开头3. 不断左右来回遍历逐步收紧左右边界4. 重复直到整个数组有序相关代码实现//鸡尾酒排序双向冒泡排序 void cocktailSort(int* a, int size) { int left 0; int right size-1; int flag 0; for (int i left; i right; i) { if (a[i] a[i 1]) { my_swap(a[i], a[i 1]); flag 1; } } if (flag 0)return; flag 0; for (int i right; i left; i--) { if (a[i] a[i - 1]) { my_swap(a[i], a[i - 1]); flag 1; } } if (flag 0)return; }作用示意图三、直接插入排序和希尔排序首先看一个生活场景你一定玩过纸牌我们都是这么玩的左手拿已经理好的有序牌从小到大排好每次右手摸一张新牌从左手手里的牌从后往前依次比对找到合适位置把新牌插进去左手始终保持全程有序直到摸完所有牌。这就是直接插入排序的原版逻辑一模一样。我们通过代码来类比一下void insertSort(int *a,int size) { for(int i0;isize-1;i) { int endi; // end左手有序区最后一张牌 int tempa[end1]; // temp右手新摸来的一张牌 // 从后往前比对手牌 while(end0) { if(a[end]temp) { a[end1]a[end]; // 手里大牌往后挪一位 end--; } else break; // 找到比它小的停下不用再往前找 } a[end1]temp; // 把新牌插进空位 } }算法的逻辑是这样的假定我们规定【0end】这一个区间是有序的我们再引入一个元素a[end1],再通过算法使【0end1】有序主要步骤为从后往前找比a[end1]元素大的值让他们整体向后挪动一位直到找到第一个比a【end1】还要小的元素将a[end1]元素放置在这个元素后面就可以了。值得注意的是两个循环条件1 isize-1:endi,但是引入元素a【end1】end1size2 end0:当找不到比a【end1】还要小的元素时a【end1】应该放置在a【0】的位置上故此时end10,end-1,整个while循环的执行条件应该是end0,使得end-1时刚好退出循环。插入排序的示例图如下我们通过计算可以知道整个算法的交换语句运行次数最坏满足等差数列时间复杂度为O(n^2)怎样使得算法效率提高,希尔在这个算法的基础之上做出了调整得到了大名鼎鼎的希尔排序。我们首先来看一看代码void shellSort(int* a, int size) { int gap size; while(gap1) { gap gap / 3 1; for (int j 0; j size - gap; j) { int end j;//记录有序数组尾端下标 int temp a[end gap]; while (end 0) { if (temp a[end]) { a[end gap] a[end]; end-gap; } else break; } a[end gap] temp; } } }先回顾直接插入排序核心思想1. 原理把数组分成已排序区间和未排序区间第 1 个元素默认是有序区间从第 2 个元素开始逐个把未排序区间的元素插入到前面有序区间的合适位置像打牌时一张张摸牌插到手里已排好的牌里。2. 直接插入排序的致命缺点数据逆序程度大时每次插入都要大量元素后移效率极低只能一个一个元素慢慢往前挪步子太小慢得离谱时间复杂度最坏O(n2)数据量大时完全不能用。希尔给出的优化方法是根据元素对应下标对于gap的余数分组每组分别套用直接插入排序的思路将直接插入排序操作中的1全部变为gap)作为一次预排序每组数据都有序了。我们可以发现当gap足够大时大的元素经过一次排序调整距离结尾更近但是排序用时较长gap较小时大的元素在排序调整后中距离结尾更远但是排序时间更短所以我们让gap递减进行多次预排序就可以使数组有序。排序示例图如下四、计数排序举个最接地气的例子班级按考试分数排队假设一场考试满分只有5 分分数范围很小只能是 0、1、2、3、4、5班里同学分数如下分数列表[3, 1, 4, 1, 5, 3, 2, 3]现在要从小到大给所有人按分数排序你会怎么最简单排普通人的思路先数一下得 0 分几个人、1 分几个人、2 分几个人……5 分几个人然后按分数从小到大依次把人列出来就行。我们数一遍0 分0 人1 分2 人2 分1 人3 分3 人4 分1 人5 分1 人然后顺着写1,1,2,3,3,3,4,5直接排好序了这就是计数排序的核心思想。通过例子我们可以得知计数排序具有一定的局限性只适用于元素较为紧凑的一系列数据排序当元素大小分布较为分散时使用计数排序就明显有所不足人为实现会导致效率低下计算机实现会导致占用大量内存导致内存利用效率不高具体代码如下void countSort(int* a, int size) { int min a[0], max a[0]; for (int i 0; i size; i)//遍历找最大最小元素以方便开辟辅助数组 { if (a[i] max)max a[i]; if (a[i] min)min a[i]; } int* index (int*)calloc(sizeof(int) ,(max - min 1)); for (int cur 0; cur size; cur)index[a[cur] - min];//计数 int j 0; for (int i 0; i max - min 1; i) { while (index[i]--) { a[j] imin; j; } }; }这里运用到简单哈希的思想1.首先遍历整个数组找到最大元素和最小元素即数据范围。2.根据数据范围动态开辟计数数组数组大小为max-min1)3.遍历整个原数组进行计数4.遍历计数数组来写入数据到原数组相关示例图解如下五、选择排序void selecSort(int * a,int size) { // i 从 size-1 开始到 1 结束 for(int i size - 1; i 1; i--) { int index 0; // 找 0~i 最大值 for(int j 0; j i; j) { if(a[j] a[index]) index j; } // 交换 a[i] 和 最大值 my_swap(a[i], a[index]); } }这是一个朴素的选择排序每i趟排序选出一个最大值放置在数组倒数第i个位置。但是一趟排序只能确定一个元素的位置故算法最坏时间复杂度为O(n^2)。我们可以稍作改进每次选出一个最大的元素一个最小的元素这样一趟排序下来就有两个元素的位置确定了。//选择排序 void selectSort(int* a, int len) { int begin 0; int endlen-1; while(beginend) { int max begin, min begin; for (int i begin 1; i end; i) { if (a[i] a[max])max i;//找到一趟中最大元素的下标 if (a[i] a[min])min i;//找到一趟中最小元素的下标 } my_swap(a[begin], a[min]); if (max begin)max min;//特例一趟中maxbegin my_swap(a[end], a[max]); begin; end--; } }值得注意的是这个程序有一个小细节if (max begin)max min;这样做的原因是当beging刚好是max记录的下标时第一次交换就会导致max下标失效所以在第二次交换前要检查max下标的有效性。代码运行关键步骤图解六、堆排序堆排序是基于数据结构堆来实现的相关细节请看往期博客c语言数据结构——堆详解下面是代码实现//升序建大堆 void adjustDown(int* arr, int size, int parent) { int child 2 * parent 1; while(childsize) { if (child 1size arr[child 1] arr[child]) child; if (arr[child] arr[parent]) { my_swap(arr[child], arr[parent]); parent child; child parent * 2 1; } else break; } } void heapSort(int* arr, int size) { for (int i (size - 1 - 1)/2; i 0; i--) { //向下调整建堆 adjustDown(arr,size, i); } int end size - 1; while (end 0) { my_swap(arr[0], arr[end]); adjustDown(arr, end, 0); end--; } }再次强调算法思想1.向下调整建堆升序建大堆降序建小堆2.交换首位元素对堆顶元素调用向下调整算法类似于堆顶元素的删除算法七归并排序给出一个生活中的小例子场景两摞已经排好序的作业本合并成一摞整体有序班里有两组同学的数学作业本都已经各自按分数从低到高排好了第一组[60, 72, 85]第二组[65, 78, 90, 95]现在老师要把两摞有序的本子合成一摞从头到尾有序你会怎么干不用打乱重排最聪明的做法两边各拿最上面一本比大小把分数低的先放到新队伍里哪一边拿完了剩下的直接全部接在后面。过程60 vs 65 → 放 6072 vs 65 → 放 6572 vs 78 → 放 7285 vs 78 → 放 7885 vs 90 → 放 85最后把 90、95 直接补上最终[60,65,72,78,85,90,95]相关算法涉及两个有序数组的合并两个有序数组的合并算法题归并排序的核心思想是1将数组一分为二2将两个数组分别排有序3.将两个有序数组合并那么怎么将两个数组排有序呢这不又回到问题本身了吗是不是有递归的味道相关代码实现//归并排序 void _mergeSort(int* a, int *arr,int left,int right) { if (left right)return; int mid (left right) / 2; //分治数组划分[left,mid][mid1,right]注意[left,mid-1][mid,right]分法有bug _mergeSort(a, arr, left, mid); _mergeSort(a, arr, mid 1, right); int begin1 left, end1 mid; int begin2 mid 1, end2 right; int i left; //两个有序数组的合并 while (begin1 end1 begin2 end2) { if (a[begin1] a[begin2])arr[i] a[begin1]; else arr[i] a[begin2]; } while (begin1 end1) arr[i] a[begin1]; while (begin2 end2)arr[i] a[begin2]; memcpy(aleft, arrleft, sizeof(int) * (right - left 1)); } void mergeSort(int* a, int size) { int* arr (int*)malloc(sizeof(int) * size); if (arr NULL) { perror(malloc fail); return; } _mergeSort(a, arr, 0, size - 1); free(arr); arr NULL; }归并排序相关图解第一步[8,4,5,7,1,3,6,2]/ \[8,4,5,7] [1,3,6,2]/ \ / \[8,4] [5,7] [1,3] [6,2]/ \ / \ / \ / \[8] [4] [5] [7] [1] [3] [6] [2]第二步[8] [4] → [4,8] [5] [7] → [5,7][1] [3] → [1,3] [6] [2] → [2,6][4,8] [5,7] → [4,5,7,8][1,3] [2,6] → [1,2,3,6]最后合并两大段[4,5,7,8] [1,2,3,6]↓最终有序[1,2,3,4,5,6,7,8]归并排序还有非递归版本//非递归版 void mergeSort2(int* a, int size) { //开辟辅助数组 int* nums (int*)malloc(sizeof(int) * size); for(int gap1;gapsize;gap*2) { //[i,gapi-1] [gapi,2*gapi-1] for (int i 0; i size; i 2 * gap) { int begin1 i, end1 gap i - 1; int begin2 gap i, end2 2 * gap i - 1; //处理越界情况 if (begin2 size)break;//第二组数据越界第一组数据部分越界不需要再归并了 if (end2 size)end2size-1;//第二组数据部分越界更新end2 int j begin1; //两个有序数组的合并 while (begin1 end1 begin2 end2) { if (a[begin1] a[begin2])nums[j] a[begin1]; else nums[j] a[begin2]; } while (begin1 end1) nums[j] a[begin1]; while (begin2 end2)nums[j] a[begin2]; memcpy(a i, nums i, sizeof(int) * (end2 - i 1)); } } free(nums); nums NULL; }这里有两个小细节已知将相邻的一段数据划为两段数据[i,gapi-1] [gapi,2*gapi-1]if (begin2 size)break;//第二组数据越界第一组数据部分越界不需要再归并了if (end2 size)end2size-1;//第二组数据部分越界更新end2再归并两段数据八快速排序首先来一个小例子引入场景全班同学按身高排队随便先挑一个人当基准中间人比如身高 170cm。所有人分成三拨比170 矮的站左边刚好 170站中间比170 高的站右边然后左边矮的一堆再随便挑一个中间人再分高矮右边高的一堆同样再分一直递归分下去全班自然就从矮到高排好了。这就是快排核心选基准、分区、左右递归我们首先写一个朴素的快速排序haore)版本//快速排序 void quickSort0(int* a, int left, int right) { if (left right)return; int keyi left; int end right; int begin left1; while (begin end) { while (begin end a[end] a[keyi])end--;//右边找大 while (begin end a[begin] a[keyi])begin;//左边找小 my_swap(a[begin], a[end]);//交换一大一小 } my_swap(a[begin], a[keyi]);//当二者相遇再交换keyi和begin指向的元素 quickSort(a, left, begin - 1);//begin左边排有序 quickSort(a, begin 1,right);//begin右边排有序 }算法的核心是将每个数组的第一个元素作为基准值用左右指针先让右指针找比基准值小的数之后让左指针找比基准值要大的数二者交换累次循环直到左右指针相遇每次都是右指针先移动再交换相遇位置所对应的元素和基准值此时由于基准值所在位置左边都是比它小的值右边都是比它大的值此时基准值在数组中的位置就唯一确定了。将基准值从原数组中忽略左右部分分别进行如上操作递归就可以使原数组有序了。代码演示图解数组[5, 3, 8, 4, 2, 7, 1, 6]初始调用quickSort0(a, left0, right7)plaintextleft0 right7 keyi 0 基准值 a[0] 5 begin left 1 1 end right 7初始状态下标 0 1 2 3 4 5 6 7数值5, 3 , 8 , 4 , 2 , 7 , 1 , 6 keyi begin end进入第一层 while (begin end) 循环第一步end 左移找 5 的数循环while (begin end a[end] a[keyi]) end--从最右端往左扫跳过所有≥5 的数扫到 a [6]1 小于 5停下plaintext下标 0 1 2 3 4 5 6 7 数值**5** , 3 , 8 , 4 , 2 , 7 , 1 , 6 keyi begin end第二步begin 右移找 5 的数循环while (begin end a[begin] a[keyi]) begin从 begin 往右扫跳过所有≤5 的数扫到 a [2]8 大于 5停下plaintext下标 0 1 2 3 4 5 6 7 数值**5** , 3 , 8 , 4 , 2 , 7 , 1 , 6 keyi begin end第三步不相遇交换 begin 和 end 元素my_swap(a[begin], a[end]);交换后数组plaintext下标 0 1 2 3 4 5 6 7 数值**5** , 3 , 1 , 4 , 2 , 7 , 8 , 6 keyi begin end继续循环begin end 再次执行end 继续左找小于 5 → 走到下标 4数值 2begin 继续右找大于 5 → 此时begin 和 end 碰到一起停止循环相遇最终状态plaintext下标 0 1 2 3 4 5 6 7 数值**5** , 3 , 1 , 4 , 2 , 7 , 8 , 6 keyi begin end跳出大循环交换基准位 和 相遇位置my_swap(a[begin], a[keyi]);交换基准 5 和 相遇位置 2单趟走完数组变成plaintext下标 0 1 2 3 4 5 6 7 数值 2 , 3 , 1 , 4 ,**5**, 7 , 8 , 6✅ 效果基准值 5 归位左边全部 ≤5右边全部 ≥5我们发现当数组元素是有序的排升序原数组降序时算法就会退化时间复杂度降为On^2)当我们选取的基准值是每趟排序中的中位数时函数调用栈帧创建的结构就形似二叉树时间复杂度为NlogN)所以我们设计出了一种三数取中算法来让基准值尽量为中位数同时当待排序元素较少时我们使用插入排序也能使排序性能提高int getMed(int* a, int left, int right) { int med (left right)/ 2; if (a[left] a[right]) { if (a[right] a[med])return med; else if (a[med] a[left])return left; else return right; } else { if (a[left] a[med])return left; else if (a[med] a[right])return right; else return med; } } void quickSort(int* a, int left, int right) { if (left right)return; if (right - left 1 10)//小区间优化 { insertSort(a left, right - left 1); } else { int keyi left; int end right; int begin left;//不可跳过设置begin为left1:9 8 7 6 int med getMed(a, left, right); my_swap(a[keyi], a[med]);//三数取中算法避免退化成o(N^2) while (begin end) { while (begin end a[end] a[keyi])end--;//右边找小 while (begin end a[begin] a[keyi])begin;//左边找大 my_swap(a[begin], a[end]);//交换一大一小 } my_swap(a[begin], a[keyi]);//当二者相遇再交换keyi和begin指向的元素 quickSort(a, left, begin - 1);//begin左边排有序 quickSort(a, begin 1, right);//begin右边排有序 } }下面是挖洞法对快速排序的实现基本逻辑和上面相同只是更直观//挖洞法 void quickSort2(int* a, int left,int right) { if (left right)return; int tempa[left],holeleft; int end right, begin left; while (beginend) { while (end begina[end] temp)end--; a[hole] a[end]; hole end; while (end begin a[begin] temp)begin; a[hole] a[begin]; hole begin; } a[hole] temp; quickSort2(a, left, hole - 1); quickSort2(a, hole 1, right); }前后指针法实现快速排序//前后指针法 void quickSort3(int* a, int left, int right) { if (left right)return;//递归返回条件 int cur left 1;//遍历找小 int prev left;//指向左边最后一个小于a[left]的元素 while (cur right) { if (a[cur] a[left] prev ! cur)my_swap(a[cur], a[prev]);//cur找小就交换 cur; }//最后一次交换后prev停留在比a[left]小的元素的位置 my_swap(a[prev], a[left]); quickSort3(a, left, prev - 1); quickSort3(a, prev 1, right); }三区间划分法实现快排算法实现用到了三指针和这道OJ题的算法思想相似数组的三段划分三段划分思想的核心是定义三个指针prev,cur,endcur负责遍历整个数组prev指向第一个区间的末尾end指向最后一个区间的开始就这样在遍历的过程中数组被分割成4个部分【leftprev】【prev1,cur-1】【cur,end-1】【end,right】开始时prevleft-1;endright1;当curend时遍历结束上述区间的第三个就不存在了整个数组被分成三个区间当然划分的方法也有讲究假设最终的123区间分别满足特性1特性2特性3当cur指向元素满足特性2时只需要将cur;让这个元素囊括到2区间当cur指向元素满足特性3是只需要将end--,再交换cur,end所指向的元素即可由于cur右边区域的元素还没有遍历的无法确定其特性还需再次判断cur不能当cur指向元素满足特性1时将prev,交换cur与prev所指向元素cur,相当于将1区间扩容将2区间首元素移动到后面。单趟排序将数组按照上面思想按照基准值进行划分再对 基准值的区间进行递归排序操作就可以让数组有序了。非递归法实现快排//非递归版本 void quickSort5(int* a, int left, int right) { stackint st; st.push(right); st.push(left); while (!st.empty()) { left st.top(); st.pop(); right st.top(); st.pop(); if (left right) continue; int keyi left; int begin left, end right; while (begin end) { // 找小从右向左 while (begin end a[end] a[keyi]) end--; // 找大从左向右 while (begin end a[begin] a[keyi]) begin; my_swap(a[begin], a[end]); } // 将基准值放到正确位置 my_swap(a[begin], a[keyi]); // 压入右子区间 [begin1, right] if (begin 1 right) { st.push(right); st.push(begin 1); } // 压入左子区间 [left, begin-1] if (left begin - 1) { st.push(begin - 1); st.push(left); } } }核心思路是用栈这个数据结构来模拟函数递归调用的过程主要算法和hoare版本相同模仿递归的过程是按照栈的后进先出原则来实现首先将待排序数组的左右下标传入出栈获取进行一趟排序之后首先压入右子区间的左右下标然后是左子区间如果区间违法就不入栈再循环进行出入栈排序的操作直到栈中元素为空。这个算法是来拟合二叉树的前度遍历。九、常用八大排序的性能总结排序算法平均时间复杂度最好时间复杂度最坏时间复杂度空间复杂度稳定性排序方式冒泡排序O(n2)O(n)O(n2)O(1)稳定原地直接插入排序O(n2)O(n)O(n2)O(1)稳定原地简单选择排序O(n2)O(n2)O(n2)O(1)不稳定原地希尔排序O(n1.3)O(n)O(n2)O(1)不稳定原地堆排序O(nlogn)O(nlogn)O(nlogn)O(1)不稳定原地快速排序O(nlogn)O(nlogn)O(n2)O(logn)递归栈不稳定原地归并排序O(nlogn)O(nlogn)O(nlogn)O(n)稳定非原地计数排序O(nk)O(nk)O(nk)O(nk)稳定非原地稳定性判断核心理解一、什么是排序稳定性定义假设数组中有两个相等的元素排序前A在B前面排序后如果A 仍然在 B 前面→稳定排序如果A、B 相对位置颠倒了→不稳定排序值相等的元素排序后相对位置不变 排序具有稳定性二、举个秒懂例子有数组括号是原始身份2(①) , 5 , 2(②) , 3两个22①在前2②在后稳定排序结果2(①) , 2(②) , 3 , 5相等元素保持原来先后顺序✅ 稳定不稳定排序可能出现2(②) , 2(①) , 3 , 5相等元素位置颠倒❌ 不稳定三、为什么会不稳定核心原因算法存在远距离交换只要有跨位置直接交换相等元素就容易打乱相对次序相邻交换、后移覆盖 一般是稳定的四、八大排序稳定 / 不稳定 归类 原因✅ 稳定排序冒泡排序只相邻交换相等不交换 → 稳定直接插入排序元素后移不跳跃交换 → 稳定归并排序左右合并时相等优先放左边原有元素 → 稳定计数排序计数排序一般只用于整形数据的排序研究稳定性意义不大❌ 不稳定排序简单选择排序直接把最值和最前面远距离交换容易打乱相等元素如果中间有和被交换数据大小相同的元素希尔排序分组跳跃式插入不是相邻移动 → 不稳定快速排序基准交换是远距离交换→ 不稳定堆排序堆调整是上下层远距离交换→ 不稳定