排序算法Sort排序是计算机科学中最基础、最经典的算法问题之一也是面试和实际开发中的高频考点。本文系统性地解析了七大经典排序算法插入排序、希尔排序、冒泡排序、选择排序、堆排序、快速排序Hoare版三数取中以及三路快速排序。每种算法都配有完整的C语言实现、逐行解释、时间复杂度分析和关键陷阱提示。目标读者正在学习数据结构与算法的在校学生、准备技术面试的求职者以及需要复习排序算法核心思想的开发者。核心价值代码实战导向每个算法都提供可直接运行的C语言实现并附有逐行注释帮助理解每一行代码的作用。陷阱全解析特别总结了每个算法最容易出错的地方如选择排序的maxi修正、快排的end先走原则、三路快排的i前进逻辑避免踩坑。工业级优化不仅讲解基础版本还引入了三数取中、三路划分等工程优化技巧提升算法在实际场景中的性能。对比与选型通过复杂度总表和适用场景分析帮助你根据数据规模、有序度、稳定性等需求选择最合适的排序算法。无论你是为了通过考试、准备面试还是想在项目中写出更高效的排序代码这篇文章都将为你提供清晰的思路和实用的代码参考。排序像整理一手乱牌有的算法是一张张往手里插插入有的是按间隔分组排再合并希尔有的是两两比较冒泡冒泡有的是挑最大最小放两头选择有的是建堆取顶堆排有的是分地盘递归快排。各有各的脾气和适用场景。核心思想排序没有「最好」只有「最适合」。选择排序算法要看数据规模、是否基本有序、是否稳定、是否要原地空间 O(1)、是否含大量重复元素。本项目实现了插入、希尔、冒泡、选择、堆排、快排Hoare 三数取中、三路快排。先讲辅助函数再逐一拆解每种排序。辅助函数交换 SwapvoidSwap(int*a,int*b){intc*a;*a*b;*bc;}逐行解释传指针才能修改实参。经典三变量交换。工程提示现代编译器下用临时变量的交换往往比「不用临时变量的位运算异或交换」更快异或交换有数据依赖、不可并行、且ab时会清零且可读性好所以别迷信「不用临时变量更高级」。向下调整 AdjustDown堆排用voidAdjustDown(int*a,intn,intparent){intchild2*parent1;// 左孩子while(childn){if(child1na[child]a[child1])// 大根堆选较大孩子child;if(a[child]a[parent])// 孩子比父大就下沉{Swap(a[child],a[parent]);parentchild;child2*parent1;}elsebreak;}}逐行解释注意这里是大根堆的向下调整a[child] a[child1]选大孩子a[child] a[parent]才下沉和堆模块里小根堆的比较符号相反。堆排升序要用大根堆——因为要把最大值换到末尾。child1 n防右孩子越界。1. 插入排序 InsertSortO(n²)稳定小数据王者voidInsertSort(int*a,intsz){// 排序[0,end]有序把 end1 插入for(inti0;isz-1;i){intendi;inttmpa[end1];// 待插元素先存起来while(end0){if(tmpa[end])// 比 tmp 大的往后挪{a[end1]a[end];end--;}elsebreak;}a[end1]tmp;// 找到位置放下}}原理像整理扑克牌——左手中已排好序从右手抽一张在左手从右往左找位置比它大的牌往后挪一格找到空位插进去。逐行解释外层i控制把哪个元素插入a[i1][0, i]始终有序。tmp必须先存——因为a[end1]会被后面的挪动覆盖不存就丢了。内层while从end往左扫比tmp大的就右移一格直到找到不大于tmp的位置。a[end1] tmp把待插元素放进空位。关键点tmp必须提前保存最高频考点。最好情况基本有序O(n)最坏 O(n²)。稳定相等元素不交换相对顺序不变。小数据量16时比快排还快所以快排常在小区间切换到插入排序。2. 希尔排序 ShellSortO(n^1.3)不稳定插入的升级voidShellSort(int*a,intn){intgapn;while(gap1){gapgap/31;// 缩小间隔1 保证最后 gap1for(inti0;in-gap;i){intendi;inttmpa[endgap];// 跨 gap 取待插元素while(end0){if(tmpa[end]){a[endgap]a[end];// 跨 gap 挪动end-gap;}elsebreak;}a[endgap]tmp;}}}原理插入排序在「基本有序」时很快但整体乱时慢。希尔先按大间隔gap分组做插入排序让远的元素快速归位逐步缩小gap最后gap1做一次普通插入排序收尾。因为前面已让数组「基本有序」最后一次插入排序接近 O(n)。逐行解释gap gap/3 1每次缩到约 1/31保证gap最终会变成 1否则gap可能卡在 2→0 跳出漏了最后一次完整排序。内层和插入排序几乎一样只是步长从 1 变成gap——同一个位置可以同时排多个间隔为 gap 的组代码里用i从 0 到n-gap相当于多组并排。a[endgap] tmp放回时也要跨gap。注释里的笔误项目代码注释中旧版本写成了a[end1] tmp应该是a[endgap] tmp跨 gap 放回。当前实际代码已修正为a[endgap]。关键点gap序列影响性能gap/31是常用序列平均约 O(n^1.3)。不稳定相同元素可能分到不同组相对顺序会变。3. 冒泡排序 BubbleSortO(n²)稳定教学用voidBubbleSort(int*a,intn){for(intj0;jn-1;j)// n-1 趟{for(inti1;in-j;i)// 每趟把最大冒到末尾{if(a[i-1]a[i])// 前比后大就交换Swap(a[i-1],a[i]);}}}原理相邻元素两两比较前大后小就交换每趟把当前最大值「冒泡」到末尾。逐行解释外层j控制趟数n-1 趟内层i扫一遍未排序部分。n-j是因为末尾j个已排好不用再比。优化点未实现加一个flag若某趟无任何交换说明已有序提前结束——最好情况可到 O(n)。当前实现无论是否有序都跑满 O(n²)。关键点稳定相等不交换。简单但慢基本只在教学和「几乎有序 数据量小」时用。4. 选择排序 SelectSortO(n²)不稳定每轮选两头voidSelectSort(int*a,intn){intbegin0,endn-1;while(beginend){intmaxibegin,minibegin;for(intimini1;iend;i)// 一轮同时找最大和最小{if(a[i]a[maxi])maxii;if(a[i]a[mini])minii;}Swap(a[mini],a[begin]);// 最小放开头if(maxibegin)// ⚠️ 关键maxi 被 mini 换走了maximini;Swap(a[maxi],a[end]);// 最大放末尾begin;end--;}}原理每轮在[begin, end]里同时找最小值和最大值最小放begin最大放end两端向中间收拢。比普通「每轮只找最小」的版本少一半轮次。逐行解释 关键陷阱一轮同时更新maxi和mini。Swap(a[mini], a[begin])把最小换到开头——但如果maxi恰好等于begin这一步把a[begin]即原最大值换到了mini位置maxi下标失效所以下一行if(maxi begin) maxi mini;修正最大值现在在mini处。这是选择排序最经典的坑先换 mini 可能破坏 maxi 指向必须判断修正。关键点不稳定交换跨越了相等元素。虽优化了一半轮次但比较次数仍是 O(n²)。5. 堆排序 HeapSortO(n log n)不稳定原地voidHeapSort(int*a,intn){// 建大根堆从最后一个非叶子节点开始向下调整for(inti(n-2)/2;i0;i--)AdjustDown(a,n,i);// 反复取堆顶最大放末尾缩小堆再调整for(intendn-1;end0;end--){Swap(a[0],a[end]);// 堆顶最大换到末尾AdjustDown(a,end,0);// 对 [0, end) 重新向下调整}}原理升序要建大根堆。建堆后堆顶是最大值交换到末尾然后对剩余部分end减小重新向下调整恢复堆序。重复 n-1 次数组即升序。逐行解释建堆从(n-2)/2最后一个非叶子节点开始往前每个节点向下调整。这是 O(n) 建堆法不是逐个 push 的 O(n log n)。排序循环Swap(a[0], a[end])把当前堆顶最大换到end位置end--缩小堆的范围AdjustDown(a, end, 0)对剩下的堆顶做一次向下调整注意传入end而非n因为末尾已排好不再参与。关键点升序用大根堆最大值往末尾送降序用小根堆。不稳定。原地排序空间 O(1)。建堆 O(n)排序 n 次 O(log n) 调整总体 O(n log n)。6. 快速排序 QuickSortHoare 版 三数取中三数取中 Getmidi优化 pivotintGetmidi(int*a,intleft,intright){intmidi(leftright)/2;if(a[left]a[midi]){if(a[midi]a[right])returnmidi;elseif(a[left]a[right])returnright;elsereturnleft;}else{if(a[right]a[left])returnleft;elseif(a[midi]a[right])returnmidi;elsereturnright;}}原理快排最怕有序数据——如果每次选第一个做 pivot有序数组会让每轮只分出一个元素退化到 O(n²)。三数取中从left、mid、right三个位置选中间值做 pivot避免极端。逐行解释通过嵌套比较三个位置的值返回中间值的下标。逻辑绕但本质就是「三个数里排中间那个」。不是为了找最大或最小而是找中位让划分更均衡。Hoare 划分版 QuickSortvoidQuickSort(int*a,intleft,intright){if(leftright)return;// 区间长度 1 终止intmidiGetmidi(a,left,right);Swap(a[midi],a[left]);// pivot 换到 left 位置intkeyileft;intbeginleft,endright;while(beginend){// end 先走找比 pivot 小的while(beginenda[end]a[keyi])end--;// begin 后走找比 pivot 大的while(beginenda[begin]a[keyi])begin;Swap(a[begin],a[end]);// 交换这对逆序}Swap(a[keyi],a[end]);// pivot 归位到相遇点keyibegin;QuickSort(a,left,keyi-1);// 递归左半QuickSort(a,keyi1,right);// 递归右半}原理选一个 pivot把数组分成「小于 pivot / pivot / 大于 pivot」三段pivot 到位再递归排左右两段。分治思想。逐行解释 关键点Getmidi选 pivot 并换到left避免有序退化。为什么end先走pivot 在leftend从右找小的begin从左找大的。当begin和end相遇时相遇点的值应该比 pivot 小因为是end最后停在那这样Swap(a[keyi], a[end])才能把 pivot 换到正确的「左小右大」分界。如果begin先走相遇点可能是比 pivot 大的值pivot 换过去就错了。这是 Hoare 划分最核心的细节。a[end] a[keyi]用而非遇到相等的也跳过避免相等元素卡住循环。递归终止left right区间空或单元素已有序。关键点平均 O(n log n)最坏 O(n²)三数取中极大缓解。递归深度 O(log n)栈空间。不稳定。工程优化未实现小区间如 16切换插入排序减少递归开销尾递归优化减少栈深度。7. 三路快速排序 QuickSort3Way解决大量重复元素voidQuickSort3Way(int*a,intleft,intright){if(leftright)return;intmidiGetmidi(a,left,right);Swap(a[midi],a[left]);intkeya[left];// 三段循环不变量// a[left..lt-1] key// a[lt..i-1] key// a[i..gt] 未处理// a[gt1..right] keyintltleft;intgtright;intileft;while(igt){if(a[i]key)// 小于换到 区{Swap(a[i],a[lt]);lt;i;// i 前进换来的已检查过}elseif(a[i]key)// 大于换到 区{Swap(a[i],a[gt]);// ⚠️ i 不前进换来的 a[gt] 没检查过gt--;}else// 等于留在 区{i;}}// 只递归 区和 区 区已就位不再处理QuickSort3Way(a,left,lt-1);QuickSort3Way(a,gt1,right);}原理荷兰国旗问题Dutch National Flag。传统快排两路划分在大量重复元素时会退化很多元素等于 pivot反复无效交换。三路把数组分成 key、 key、 key三段 key段直接跳过不再递归重复元素越多越快。逐行解释 关键点三个游标维护循环不变量lt是区右端gt是区左端i是当前考察位置。a[i] key换到区末尾lt、i。换来的元素来自lt位置属于区已检查过所以i前进。a[i] key换到区开头gt--。i不前进——因为从gt换过来的元素还没检查过下轮要再看它。a[i] key留在区i。递归只处理区[left, lt-1]和区[gt1, right] key段跳过。i是否前进是最关键的细节和时i时i不动。搞反了会漏判或多判。关键点解决大量重复元素的退化问题重复越多越接近 O(n)。仍然 O(n log n) 平均、不稳定。复杂度与特性总表算法平均时间最坏时间空间稳定性适用场景插入排序O(n²)O(n²)O(1)✅稳定小数据 / 基本有序希尔排序O(n^1.3)O(n²)O(1)❌不稳定中等规模冒泡排序O(n²)O(n²)O(1)✅稳定教学 / 几乎有序选择排序O(n²)O(n²)O(1)❌不稳定数据量小堆排序O(n log n)O(n log n)O(1)❌不稳定大数据 原地快排两路O(n log n)O(n²)O(log n)❌不稳定通用最快三路快排O(n log n)O(n log n)O(log n)❌不稳定大量重复元素常见陷阱清单插入排序不先存tmp→ 待插元素被覆盖丢失。希尔排序gap不加 1→gap卡在 2 跳出漏最后一次完整排序。选择排序maxi begin不修正→maxi指向被mini交换走的值结果错误。堆排序升序建小根堆→ 应建大根堆最大值往末尾送。Hoare 快排begin先走→ 相遇点可能是大值pivot 归位错误。三路快排a[i] key时i→ 漏判换来的元素。quicksort_残缺函数→ 代码里有个未完成的quicksort_含未定义的swap、逻辑残缺会导致编译失败建议删除。快排不处理有序退化→ 应加三数取中或随机化 pivot本项目已加三数取中 ✅。我的实现 vs 教科书实现亮点快排加了三数取中防有序退化 三路划分防重复退化这是工业级优化意识。选择排序双向选 max/min 减半轮次。残缺代码quicksort_函数未完成会编译失败应删除。注释笔误希尔排序注释旧版本a[end1] tmp应为a[endgap]实际代码已对。缺归并排序稳定 O(n log n)外部排序、链表排序必备。缺非比较排序计数排序、基数排序、桶排序线性时间适合整数范围有限。缺快排优化小区间切换插入排序、非递归用栈模拟。测试覆盖三路快排测了全相等/大量重复/已排序/逆序四种 case测试意识好。拓展知识点变体与进阶归并排序分治 合并稳定 O(n log n)适合链表排序和外部排序数据放不下内存时。手写重点在merge的双指针合并和临时数组。计数排序统计每个值出现次数适合值域小的整数O(nk)。非比较排序能突破 O(n log n) 下界。基数排序按位个十百…用计数排序适合定长整数或字符串。桶排序分桶后桶内排序适合均匀分布数据。双轴快排Dual-PivotJDKArrays.sort对基本类型的实现两个 pivot 分三段实测比单轴快。常见考点必刷快排的 pivot 优化三数取中、随机化防有序退化。三路划分大量重复元素的优化荷兰国旗问题。堆排序建堆 O(n) 证明调整距离求和。排序稳定性哪些稳定插入/冒泡/归并哪些不稳定希尔/选择/堆/快及稳定性的应用场景多关键字排序。快排非递归用栈模拟递归避免栈溢出。各排序手写面试常要求手写快排、归并、堆排。与其他结构的关系堆排序依赖堆结构见 Binary_Tree 模块的AdjustDown/AdjustUp归并排序体现分治和快排同源快排的划分思想与 BST 的构建同构一次快排划分 ≈ 把 pivot 插入 BST。排序是二分查找、贪心、双指针等算法的前置条件——很多算法要求输入有序。一句话记忆法插入像理牌先存 tmp希尔按 gap 缩冒泡相邻换选择两头挑且防 maxi 被换走堆排建大根堆取顶快排 end 先走 三数取中三路分 且遇大于 i 不动。