排序算法大概是数据结构里最像“武功招式”的东西了。不管你是科班出身还是半路转码第一道绕不过去的坎基本都是它。面试问到算法冒泡、选择、插入、希尔、归并、快速、堆这七大经典排序出现的频率高得吓人而且往往不只是让你背个复杂度还要你当场手写实现、分析稳定性、说清楚优化点。这篇博文我就把这七个排序算法的原理、C实现、复杂度推导、常见坑位一次性讲透顺便聊聊实际工程里到底该怎么选型。内容适合正在学数据结构的初学者也适合准备面试想系统梳理一遍的读者——你不需要再翻好几篇博客拼凑答案这里就是一个完整的、能直接照着敲代码的参考。1. 排序算法全景图复杂度、稳定性与适用场景的底层逻辑1.1 为什么排序是数据结构的“第一道门槛”很多初学者会问现在随便调一个std::sort就能排序为什么还要自己手写排序算法这个问题就像问“有计算器了为什么还要学四则运算”——计算器只负责给出结果而你要理解结果为什么正确、什么时候高效、什么时候会崩。排序是后续一切数据操作的基石二分查找要求数据有序去重和归并依赖有序序列树形结构和索引的构建也常常以排序为前置步骤。更重要的是排序算法是训练算法思维最好的素材。七种经典排序覆盖了枚举、交换、分治、递归、堆结构、增量优化等核心思想你把这些吃透了再看动态规划、图论、字符串匹配都会轻松很多。要是第一关就含糊过去后面很多内容都容易悬空。这也是我把“复杂度”和“稳定性”放在最前面讲的原因——不理解这两个指标你就不知道什么时候该用什么排序哪怕是照着别人的代码抄也会踩坑。1.2 复杂度、稳定性与内存占用的三重考量评价一个排序算法业内基本看三个维度时间复杂度、空间复杂度、稳定性。时间复杂度和空间复杂度不用多解释稳定性这里要特别强调一下稳定排序指的是当两个元素的值相等时它们在排序前后的相对顺序保持不变。这个性质看起来玄乎实际上在业务场景中非常重要。举个例子一个表格先按“更新时间”排过序再按“优先级”排序如果第二轮的排序算法不稳定那么“更新时间”的顺序就被打乱了用户看到的就是一团乱麻。七种经典排序的这三个维度我整理成了一张表建议直接收藏排序算法平均时间复杂度最好情况最坏情况额外空间稳定性冒泡排序O(n²)O(n)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序O(n^1.3)左右看增量序列O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)递归栈不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定这张表信息量很大我用生活化一点的方式解释一下大O的含义O(n²)意味着数据量翻倍耗时变成原来的四倍O(n log n)意味着数据量翻倍耗时只是原来的两倍多一点。所以当数据规模从一万涨到十万O(n²)算法的耗时差了100倍而O(n log n)算法只差了大约10倍左右。这就是为什么实际工程中几乎不会用冒泡排序处理大规模数据而快排、归并、堆排序能扛住大数据量。2. 入门三剑客冒泡、选择、插入——O(n²)排序里藏着的细节2.1 冒泡排序从版本演进看优化思路冒泡排序的原理最简单从头开始两两比较相邻元素如果顺序不对就交换一轮下来最大的元素就像气泡一样“浮”到了最后面。重复 n-1 轮就全部有序了。最基础的写法长这样void bubbleSort(vectorint a) { int n a.size(); for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (a[j] a[j1]) { swap(a[j], a[j1]); } } } }但真实场景中我们会加两个优化。第一个优化很自然如果某一轮从头到尾都没发生交换说明数组已经有序了直接退出循环。第二个优化我特别推荐记录每一轮最后一次发生交换的位置这个位置之后的元素已经是有序的下一轮只需要扫到这个位置之前即可。实现起来也不难void bubbleSortOptimized(vectorint a) { int n a.size(); int lastSwap n - 1; while (lastSwap 0) { int currentBorder lastSwap; lastSwap 0; for (int i 0; i currentBorder; i) { if (a[i] a[i1]) { swap(a[i], a[i1]); lastSwap i; } } } }第二个优化的价值在于如果数组大概率接近有序它能大幅减少无意义的扫描。你可能会问既然有更高效的排序学冒泡还有什么意义我的回答是冒泡排序是最容易验证“交换类排序”思想的模型也是理解“最好情况O(n)”这个复杂度的最佳载体——当你写出的冒泡能在一轮扫描后提前退出它处理有序数组的时间就是O(n)这是很多初学者没注意到的点。但平心而论工程里真的不推荐用它除非数据量极小且你需要稳定的简单实现。2.2 选择排序最直观但交换最少的算法选择排序的思路比冒泡更“偷懒”每一轮从待排序区间里找到最小值把它放到区间最前面重复 n-1 轮。它最大的特点是不管数据长什么样比较次数永远是 n(n-1)/2但因为每一轮最多只交换一次总的交换次数是 O(n)这一点在“写入成本极高”的场景下反而有价值。void selectionSort(vectorint a) { int n a.size(); for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) { minIdx j; } } swap(a[i], a[minIdx]); } }选择排序有一个几乎所有教材都会提但初学者经常记错的点它是不稳定的。比如数组是 [5a, 5b, 1]第一轮找到最小值 1和第一个位置的 5a 交换数组变成 [1, 5b, 5a]两个 5 的相对顺序就变了。实际使用中只要涉及多个字段排序稳定性往往很关键所以选择排序在业务代码里出场率不高。不过它的实现太简单了笔试里偶尔会要求写而且它也是理解“原地排序”和“最坏情况与最好情况时间复杂度相同”的绝佳例子。2.3 插入排序近乎有序数据的最强王者插入排序的想法特别像打扑克牌时整理手牌你摸到一张新牌把它插到手里已经排好序的牌堆中。代码实现上我们从第二个元素开始每次把当前元素“抽”出来在它左边的有序区间里找到正确位置然后插入进去。void insertionSort(vectorint a) { int n a.size(); for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { a[j1] a[j]; --j; } a[j1] key; } }插入排序最迷人的地方是它的自适应能力如果数组已经基本有序内部 while 循环几乎不会执行整体退化到接近 O(n)。这个特性让它在实际工程里成了“万金油配角”——排序库的底层经常在处理小规模数据时切换到插入排序比如数据量小于16个左右时插入排序实际比快排还快原因在于它没有递归调用、也没有额外的分区操作常数项极小。我见过很多人在写插入排序时犯一个低级错误把a[j] key写成a[j] key。这会导致相同元素的相对顺序发生改变破坏稳定性。虽然插入排序本身是稳定的但一旦你把变成它就不稳定了。面试官如果问“你能让插入排序不稳定吗”答案就是改这个比较符号。这个小细节最能体现一个人是不是真的理解了稳定性的本质。3. 进阶高效排序快速排序与归并排序——分治思想的正反面3.1 快速排序平均最快的比较排序但细节决定成败快速排序是实践中最常用的比较排序算法它的核心思想是选一个基准元素pivot把数组分成小于基准和大于基准的两部分然后递归地对左右两部分继续排序。关键在于分区partition这一步我给出一个经典的原地分区实现int partition(vectorint a, int l, int r) { int pivot a[l]; int i l 1, j r; while (true) { while (i j a[i] pivot) i; while (i j a[j] pivot) --j; if (i j) break; swap(a[i], a[j]); } swap(a[l], a[j]); return j; } void quickSort(vectorint a, int l, int r) { if (l r) return; int p partition(a, l, r); quickSort(a, l, p - 1); quickSort(a, p 1, r); }这个实现里我故意选了最简单的方式固定取左端元素作为 pivot。这样写很好理解但有个致命问题如果数组已经有序每轮分区选到的都是最小值或最大值左右两边极不平衡递归深度会退化成 O(n)整体复杂度劣化成 O(n²)。这也解释了为什么网上有“快速排序在有序数组上非常慢”的说法。工程上的解法有两个。一是随机选取 pivot从根源上避免“总选到最值”的极端情况。二是“三数取中”取左端、右端、中间三个元素的中值作为 pivot比纯随机更稳定。在进入递归前还可以加一道优化当区间长度小于某个阈值时改用插入排序。我在自己的代码里一般是阈值取15左右实测对性能提升很明显。如果数据量极大递归调用可能会导致栈溢出这时可以把递归改成显式栈用循环模拟递归过程也就是常见的非递归快速排序写法。这里还要提醒一个面试高频考点快排的分区写法有两种流派一种是上面这种双侧扫描法Hoare 变体另一种是单侧扫描的 Lomuto 分区法。Lomuto 实现起来更短但交换次数多Hoare 分区更高效但边界条件容易写错。我强烈建议你把两种都练熟这样面试官无论怎么追问都能接住。3.2 归并排序稳定而可控的分治方案归并排序走的是“先分后合”的路线把数组从中间切开递归地把左右两半排好序然后把两个有序子数组合并成一个。它最大的优势有两点一是时间复杂度稳定在 O(n log n)不管数据分布如何二是稳定因为合并时遇到相等元素我们总是先取左半边的元素。void merge(vectorint a, int l, int mid, int r) { vectorint tmp(r - l 1); int i l, j mid 1, k 0; while (i mid j r) { tmp[k] (a[i] a[j]) ? a[i] : a[j]; } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int t 0; t (int)tmp.size(); t) { a[l t] tmp[t]; } } void mergeSort(vectorint a, int l, int r) { if (l r) return; int mid l (r - l) / 2; mergeSort(a, l, mid); mergeSort(a, mid 1, r); if (a[mid] a[mid1]) { merge(a, l, mid, r); } }在我这个实现里加了一个小优化只有当a[mid] a[mid1]时才执行 merge。因为如果左半最大值已经小于右半最小值说明两边已经整体有序不需要合并这样可以省掉很多无用功。另一个常见的工程优化是提前分配好一个全局辅助数组避免每次 merge 都重新分配内存。这个优化在性能敏感场景下收益很明显毕竟频繁的动态内存分配是很大的开销。归并排序还有一个重要身份它是外部排序的基础。所谓外部排序是指数据量大到内存装不下必须放在磁盘上处理。此时把大文件切分成长度适中的块每块读入内存排序后写回再把这些有序块两两归并最终生成整个有序文件——这个过程用的核心操作就是 merge。所以别再觉得归并排序没用它在数据库、大数据处理里是不可或缺的底层算法之一。4. 跳跃式插入与树形选择希尔排序和堆排序4.1 希尔排序插入排序的gap跳水式改进希尔排序是插入排序的“威力加强版”。它不再每次都只比较相邻元素而是先按一定间隔 gap 将数组分成若干个子序列对每个子序列做插入排序然后不断缩小 gap直到 gap 等于 1最后做一次标准的插入排序收尾。这样做的目的是让元素一开始就能跨越很远地移动尽早让数组接近有序最后一轮插入排序时移动次数会非常少。void shellSort(vectorint a) { int n a.size(); for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key a[i]; int j i; while (j gap a[j - gap] key) { a[j] a[j - gap]; j - gap; } a[j] key; } } }这里 gap 的取法用的是最简单的“每次减半”。但我要提醒你增量序列的选择直接决定希尔排序的时间复杂度。Knuth 序列gap gap / 3 1和 Sedgewick 序列在实践中表现更好最坏情况能控制在 O(n^1.5) 以内。如果你是应付笔试写减半版本完全够了如果你要在真实项目里用建议至少换成 Knuth 序列。希尔排序的稳定性问题比选择排序更明显因为元素会跨越 gap 进行交换相等的元素可能被分到不同的子序列里相对顺序天然就无法保证。这在理解上要特别注意。另外希尔排序虽然是插入排序的升级版但它的最好情况复杂度也是 O(n)也就是说处理近似有序的大数组时表现非常好而且不需要额外空间这是它相对归并排序的一个重要优势。4.2 堆排序用完全二叉树玩出稳定输出堆排序的思路稍微抽象一点先把数组整理成一个大顶堆也就是一棵完全二叉树其中每个父节点的值都大于等于它的子节点。堆顶就是全局最大值把它和数组末尾交换最大值归位然后对剩下的部分重新调整成堆再取次大值……如此循环数组从后往前就被排好了。void siftDown(vectorint a, int i, int n) { while (true) { int left 2 * i 1; if (left n) break; int largest left; int right left 1; if (right n a[right] a[left]) { largest right; } if (a[i] a[largest]) break; swap(a[i], a[largest]); i largest; } } void heapSort(vectorint a) { int n a.size(); for (int i n / 2 - 1; i 0; --i) { siftDown(a, i, n); } for (int end n - 1; end 0; --end) { swap(a[0], a[end]); siftDown(a, 0, end); } }很多人不理解为什么建堆的循环只从n/2 - 1开始。因为完全二叉树中叶子节点本身已经满足堆的性质无需调整n/2 - 1正好是最后一个非叶子节点的下标。从它开始往前逐个调用 siftDown就能在 O(n) 时间内完成建堆这个复杂度比很多人直觉的 O(n log n) 要低是个很有意思的数学结论有兴趣可以自己推导一下。堆排序最大的优势是额外空间 O(1)时间稳定在 O(n log n)理论上是个很完美的原地排序算法。但它实际用起来常常比归并和快排慢原因是它访问数组时跳跃性很强缓存命中率不高在大数据量下吃亏。堆排序另外一个身份更出名它是“Top K 问题”的经典解法。比如要在海量数据里找出最大的1000个我们只需要维护一个大小为1000的小顶堆遍历一遍数据堆顶就是当前第1000大的值时间复杂度只有 O(n log k)这个场景下堆的能力无可替代。5. 实战经验调试、测试、什么时候用哪种排序5.1 用四类测试集验证你的排序实现我在手写排序算法时从来不会只拿一个随机数组测一遍就说“搞定”。因为正确性验证需要覆盖不同的数据形态尤其是那些能把算法逼到最坏情况的形态。我建议你至少准备四类测试集随机数组、近乎有序的数组、包含大量重复值的数组、以及小规模数组。随机数组用来验证算法的普适正确性近乎有序的数组专门用来考验快排的退化风险和插入排序的自适应能力大量重复值的数组能暴露稳定性问题和分区不均问题小规模数组则用来验证边界条件比如 n0、n1、n2。测试的正确性判断不能光看最终结果是否有序还需要写一个校验函数检查每个元素是否都还在、是否出现了不该有的值覆盖。我踩过的坑就是归并排序的辅助数组下标没理清导致排序结果“看起来有序但其实少了元素”。另外我强烈建议你在学习阶段给算法加上“计数器”。比如在比较和交换的地方各加一个全局计数变量跑同一组数据观察不同算法的比较次数和交换次数。你会发现快排和归并的比较次数比冒泡少一到两个数量级这种直观感受比背任何结论都要深刻。5.2 常见bug与排查技巧实录排序算法代码量不大但该出的毛病一个都不少。我把这些年见到的典型问题和排查思路整理成了一个速查表症状常见原因排查与修复建议插入排序结果乱序内层 while 退出后位置赋错或比较符号写成了检查a[j1] key是否在正确位置保证稳定性快速排序在有序数组上极慢固定取左端为 pivot导致分区极端失衡改用随机 pivot 或三数取中面试时主动讲出这个风险点快速排序递归栈溢出数据量大且 pivot 选择不当递归深度接近 n设置最小阈值切换插入排序或改非递归栈实现归并排序结果丢失元素merge 时辅助数组长度或下标计算错误打印每轮 merge 前后的数组重点检查r - l 1和回填循环堆排序总是少排一个/堆顶错误建堆起始下标写成了 n/2或 siftDown 边界条件不对确认从n/2 - 1开始建堆检查右孩子是否存在希尔排序最后一轮后仍有错序gap 序列没有最终落到 1确保最后一次循环 gap 等于 1否则无法保证全局有序要特别说下快排栈溢出的问题。在面试里很多人一听到“递归版快排”就默认没问题但数据量达到几十万甚至上百万时系统栈可能扛不住。我的建议是面试写递归版可以但要主动说明生产环境会考虑阈值切换和非递归化这会成为明显的加分项。排查这类问题还有一个通用思路先缩小数据规模复现再打印关键循环中每个变量的变化比瞪着眼睛看代码高效得多。5.3 工程中的选型建议与C sort的隐藏优化看完七个排序的原理你可能会问那到底该用哪个我的实际建议很简单粗暴数据量很小比如小于几十个直接插入排序最省心。数据近乎有序插入排序几乎接近 O(n)。大规模一般场景优先快速排序但要处理好 pivot 选择和退化问题。有稳定性要求用归并排序尤其是多字段排序场景。内存极其紧张堆排序额外空间 O(1)。数据量大到内存装不下归并排序的外排思路。你可能已经发现了真正适合工程生产环境的其实没有一个算法是单独打天下。C 标准库里的std::sort就是一种混合策略快速排序作为主干当递归深度过深时切换堆排序避免最坏情况当区间长度小于一定阈值时切换插入排序利用它的低常数优势。这种混合设计的思路比背住任何一个算法本身都更有价值。还有一点容易被忽略std::stable_sort底层走的是归并排序路线用来保证稳定性。所以在 C 里遇到需要稳定排序的场景直接调stable_sort就是标准答案。Java 的Arrays.sort也类似对基本类型用双轴快速排序对对象类型用 TimSort一种优化归并背后都是同样的道理没有万能算法只有根据场景把多种算法组合起来的工程智慧。最后说个我个人的经验。手写这七个排序时我建议你按“冒泡 → 选择 → 插入 → 希尔 → 归并 → 快排 → 堆”的顺序推进因为后面每一个算法几乎都是前面某个算法的升级版。每学完一个就在纸上画出它的分区或合并过程再对着代码模拟一遍小数组的完整执行。排序算法这东西看得懂和写得对中间隔着很多次调试但只要这个坎迈过去了后面学任何算法都会顺畅得多。真遇到瓶颈时记住一个笨办法把数组缩小到 5 个元素手动模拟每一步的交换哪里卡住哪里就是你理解上的漏洞。 
长河君 · 2026/9/9 19:24:01 · 阅读 1.2k 七大排序算法全解析：从原理到C++实现与工程选型
排序算法大概是数据结构里最像“武功招式”的东西了。不管你是科班出身还是半路转码第一道绕不过去的坎基本都是它。面试问到算法冒泡、选择、插入、希尔、归并、快速、堆这七大经典排序出现的频率高得吓人而且往往不只是让你背个复杂度还要你当场手写实现、分析稳定性、说清楚优化点。这篇博文我就把这七个排序算法的原理、C实现、复杂度推导、常见坑位一次性讲透顺便聊聊实际工程里到底该怎么选型。内容适合正在学数据结构的初学者也适合准备面试想系统梳理一遍的读者——你不需要再翻好几篇博客拼凑答案这里就是一个完整的、能直接照着敲代码的参考。1. 排序算法全景图复杂度、稳定性与适用场景的底层逻辑1.1 为什么排序是数据结构的“第一道门槛”很多初学者会问现在随便调一个std::sort就能排序为什么还要自己手写排序算法这个问题就像问“有计算器了为什么还要学四则运算”——计算器只负责给出结果而你要理解结果为什么正确、什么时候高效、什么时候会崩。排序是后续一切数据操作的基石二分查找要求数据有序去重和归并依赖有序序列树形结构和索引的构建也常常以排序为前置步骤。更重要的是排序算法是训练算法思维最好的素材。七种经典排序覆盖了枚举、交换、分治、递归、堆结构、增量优化等核心思想你把这些吃透了再看动态规划、图论、字符串匹配都会轻松很多。要是第一关就含糊过去后面很多内容都容易悬空。这也是我把“复杂度”和“稳定性”放在最前面讲的原因——不理解这两个指标你就不知道什么时候该用什么排序哪怕是照着别人的代码抄也会踩坑。1.2 复杂度、稳定性与内存占用的三重考量评价一个排序算法业内基本看三个维度时间复杂度、空间复杂度、稳定性。时间复杂度和空间复杂度不用多解释稳定性这里要特别强调一下稳定排序指的是当两个元素的值相等时它们在排序前后的相对顺序保持不变。这个性质看起来玄乎实际上在业务场景中非常重要。举个例子一个表格先按“更新时间”排过序再按“优先级”排序如果第二轮的排序算法不稳定那么“更新时间”的顺序就被打乱了用户看到的就是一团乱麻。七种经典排序的这三个维度我整理成了一张表建议直接收藏排序算法平均时间复杂度最好情况最坏情况额外空间稳定性冒泡排序O(n²)O(n)O(n²)O(1)稳定选择排序O(n²)O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n)O(n²)O(1)稳定希尔排序O(n^1.3)左右看增量序列O(n²)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)递归栈不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定这张表信息量很大我用生活化一点的方式解释一下大O的含义O(n²)意味着数据量翻倍耗时变成原来的四倍O(n log n)意味着数据量翻倍耗时只是原来的两倍多一点。所以当数据规模从一万涨到十万O(n²)算法的耗时差了100倍而O(n log n)算法只差了大约10倍左右。这就是为什么实际工程中几乎不会用冒泡排序处理大规模数据而快排、归并、堆排序能扛住大数据量。2. 入门三剑客冒泡、选择、插入——O(n²)排序里藏着的细节2.1 冒泡排序从版本演进看优化思路冒泡排序的原理最简单从头开始两两比较相邻元素如果顺序不对就交换一轮下来最大的元素就像气泡一样“浮”到了最后面。重复 n-1 轮就全部有序了。最基础的写法长这样void bubbleSort(vectorint a) { int n a.size(); for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (a[j] a[j1]) { swap(a[j], a[j1]); } } } }但真实场景中我们会加两个优化。第一个优化很自然如果某一轮从头到尾都没发生交换说明数组已经有序了直接退出循环。第二个优化我特别推荐记录每一轮最后一次发生交换的位置这个位置之后的元素已经是有序的下一轮只需要扫到这个位置之前即可。实现起来也不难void bubbleSortOptimized(vectorint a) { int n a.size(); int lastSwap n - 1; while (lastSwap 0) { int currentBorder lastSwap; lastSwap 0; for (int i 0; i currentBorder; i) { if (a[i] a[i1]) { swap(a[i], a[i1]); lastSwap i; } } } }第二个优化的价值在于如果数组大概率接近有序它能大幅减少无意义的扫描。你可能会问既然有更高效的排序学冒泡还有什么意义我的回答是冒泡排序是最容易验证“交换类排序”思想的模型也是理解“最好情况O(n)”这个复杂度的最佳载体——当你写出的冒泡能在一轮扫描后提前退出它处理有序数组的时间就是O(n)这是很多初学者没注意到的点。但平心而论工程里真的不推荐用它除非数据量极小且你需要稳定的简单实现。2.2 选择排序最直观但交换最少的算法选择排序的思路比冒泡更“偷懒”每一轮从待排序区间里找到最小值把它放到区间最前面重复 n-1 轮。它最大的特点是不管数据长什么样比较次数永远是 n(n-1)/2但因为每一轮最多只交换一次总的交换次数是 O(n)这一点在“写入成本极高”的场景下反而有价值。void selectionSort(vectorint a) { int n a.size(); for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (a[j] a[minIdx]) { minIdx j; } } swap(a[i], a[minIdx]); } }选择排序有一个几乎所有教材都会提但初学者经常记错的点它是不稳定的。比如数组是 [5a, 5b, 1]第一轮找到最小值 1和第一个位置的 5a 交换数组变成 [1, 5b, 5a]两个 5 的相对顺序就变了。实际使用中只要涉及多个字段排序稳定性往往很关键所以选择排序在业务代码里出场率不高。不过它的实现太简单了笔试里偶尔会要求写而且它也是理解“原地排序”和“最坏情况与最好情况时间复杂度相同”的绝佳例子。2.3 插入排序近乎有序数据的最强王者插入排序的想法特别像打扑克牌时整理手牌你摸到一张新牌把它插到手里已经排好序的牌堆中。代码实现上我们从第二个元素开始每次把当前元素“抽”出来在它左边的有序区间里找到正确位置然后插入进去。void insertionSort(vectorint a) { int n a.size(); for (int i 1; i n; i) { int key a[i]; int j i - 1; while (j 0 a[j] key) { a[j1] a[j]; --j; } a[j1] key; } }插入排序最迷人的地方是它的自适应能力如果数组已经基本有序内部 while 循环几乎不会执行整体退化到接近 O(n)。这个特性让它在实际工程里成了“万金油配角”——排序库的底层经常在处理小规模数据时切换到插入排序比如数据量小于16个左右时插入排序实际比快排还快原因在于它没有递归调用、也没有额外的分区操作常数项极小。我见过很多人在写插入排序时犯一个低级错误把a[j] key写成a[j] key。这会导致相同元素的相对顺序发生改变破坏稳定性。虽然插入排序本身是稳定的但一旦你把变成它就不稳定了。面试官如果问“你能让插入排序不稳定吗”答案就是改这个比较符号。这个小细节最能体现一个人是不是真的理解了稳定性的本质。3. 进阶高效排序快速排序与归并排序——分治思想的正反面3.1 快速排序平均最快的比较排序但细节决定成败快速排序是实践中最常用的比较排序算法它的核心思想是选一个基准元素pivot把数组分成小于基准和大于基准的两部分然后递归地对左右两部分继续排序。关键在于分区partition这一步我给出一个经典的原地分区实现int partition(vectorint a, int l, int r) { int pivot a[l]; int i l 1, j r; while (true) { while (i j a[i] pivot) i; while (i j a[j] pivot) --j; if (i j) break; swap(a[i], a[j]); } swap(a[l], a[j]); return j; } void quickSort(vectorint a, int l, int r) { if (l r) return; int p partition(a, l, r); quickSort(a, l, p - 1); quickSort(a, p 1, r); }这个实现里我故意选了最简单的方式固定取左端元素作为 pivot。这样写很好理解但有个致命问题如果数组已经有序每轮分区选到的都是最小值或最大值左右两边极不平衡递归深度会退化成 O(n)整体复杂度劣化成 O(n²)。这也解释了为什么网上有“快速排序在有序数组上非常慢”的说法。工程上的解法有两个。一是随机选取 pivot从根源上避免“总选到最值”的极端情况。二是“三数取中”取左端、右端、中间三个元素的中值作为 pivot比纯随机更稳定。在进入递归前还可以加一道优化当区间长度小于某个阈值时改用插入排序。我在自己的代码里一般是阈值取15左右实测对性能提升很明显。如果数据量极大递归调用可能会导致栈溢出这时可以把递归改成显式栈用循环模拟递归过程也就是常见的非递归快速排序写法。这里还要提醒一个面试高频考点快排的分区写法有两种流派一种是上面这种双侧扫描法Hoare 变体另一种是单侧扫描的 Lomuto 分区法。Lomuto 实现起来更短但交换次数多Hoare 分区更高效但边界条件容易写错。我强烈建议你把两种都练熟这样面试官无论怎么追问都能接住。3.2 归并排序稳定而可控的分治方案归并排序走的是“先分后合”的路线把数组从中间切开递归地把左右两半排好序然后把两个有序子数组合并成一个。它最大的优势有两点一是时间复杂度稳定在 O(n log n)不管数据分布如何二是稳定因为合并时遇到相等元素我们总是先取左半边的元素。void merge(vectorint a, int l, int mid, int r) { vectorint tmp(r - l 1); int i l, j mid 1, k 0; while (i mid j r) { tmp[k] (a[i] a[j]) ? a[i] : a[j]; } while (i mid) tmp[k] a[i]; while (j r) tmp[k] a[j]; for (int t 0; t (int)tmp.size(); t) { a[l t] tmp[t]; } } void mergeSort(vectorint a, int l, int r) { if (l r) return; int mid l (r - l) / 2; mergeSort(a, l, mid); mergeSort(a, mid 1, r); if (a[mid] a[mid1]) { merge(a, l, mid, r); } }在我这个实现里加了一个小优化只有当a[mid] a[mid1]时才执行 merge。因为如果左半最大值已经小于右半最小值说明两边已经整体有序不需要合并这样可以省掉很多无用功。另一个常见的工程优化是提前分配好一个全局辅助数组避免每次 merge 都重新分配内存。这个优化在性能敏感场景下收益很明显毕竟频繁的动态内存分配是很大的开销。归并排序还有一个重要身份它是外部排序的基础。所谓外部排序是指数据量大到内存装不下必须放在磁盘上处理。此时把大文件切分成长度适中的块每块读入内存排序后写回再把这些有序块两两归并最终生成整个有序文件——这个过程用的核心操作就是 merge。所以别再觉得归并排序没用它在数据库、大数据处理里是不可或缺的底层算法之一。4. 跳跃式插入与树形选择希尔排序和堆排序4.1 希尔排序插入排序的gap跳水式改进希尔排序是插入排序的“威力加强版”。它不再每次都只比较相邻元素而是先按一定间隔 gap 将数组分成若干个子序列对每个子序列做插入排序然后不断缩小 gap直到 gap 等于 1最后做一次标准的插入排序收尾。这样做的目的是让元素一开始就能跨越很远地移动尽早让数组接近有序最后一轮插入排序时移动次数会非常少。void shellSort(vectorint a) { int n a.size(); for (int gap n / 2; gap 0; gap / 2) { for (int i gap; i n; i) { int key a[i]; int j i; while (j gap a[j - gap] key) { a[j] a[j - gap]; j - gap; } a[j] key; } } }这里 gap 的取法用的是最简单的“每次减半”。但我要提醒你增量序列的选择直接决定希尔排序的时间复杂度。Knuth 序列gap gap / 3 1和 Sedgewick 序列在实践中表现更好最坏情况能控制在 O(n^1.5) 以内。如果你是应付笔试写减半版本完全够了如果你要在真实项目里用建议至少换成 Knuth 序列。希尔排序的稳定性问题比选择排序更明显因为元素会跨越 gap 进行交换相等的元素可能被分到不同的子序列里相对顺序天然就无法保证。这在理解上要特别注意。另外希尔排序虽然是插入排序的升级版但它的最好情况复杂度也是 O(n)也就是说处理近似有序的大数组时表现非常好而且不需要额外空间这是它相对归并排序的一个重要优势。4.2 堆排序用完全二叉树玩出稳定输出堆排序的思路稍微抽象一点先把数组整理成一个大顶堆也就是一棵完全二叉树其中每个父节点的值都大于等于它的子节点。堆顶就是全局最大值把它和数组末尾交换最大值归位然后对剩下的部分重新调整成堆再取次大值……如此循环数组从后往前就被排好了。void siftDown(vectorint a, int i, int n) { while (true) { int left 2 * i 1; if (left n) break; int largest left; int right left 1; if (right n a[right] a[left]) { largest right; } if (a[i] a[largest]) break; swap(a[i], a[largest]); i largest; } } void heapSort(vectorint a) { int n a.size(); for (int i n / 2 - 1; i 0; --i) { siftDown(a, i, n); } for (int end n - 1; end 0; --end) { swap(a[0], a[end]); siftDown(a, 0, end); } }很多人不理解为什么建堆的循环只从n/2 - 1开始。因为完全二叉树中叶子节点本身已经满足堆的性质无需调整n/2 - 1正好是最后一个非叶子节点的下标。从它开始往前逐个调用 siftDown就能在 O(n) 时间内完成建堆这个复杂度比很多人直觉的 O(n log n) 要低是个很有意思的数学结论有兴趣可以自己推导一下。堆排序最大的优势是额外空间 O(1)时间稳定在 O(n log n)理论上是个很完美的原地排序算法。但它实际用起来常常比归并和快排慢原因是它访问数组时跳跃性很强缓存命中率不高在大数据量下吃亏。堆排序另外一个身份更出名它是“Top K 问题”的经典解法。比如要在海量数据里找出最大的1000个我们只需要维护一个大小为1000的小顶堆遍历一遍数据堆顶就是当前第1000大的值时间复杂度只有 O(n log k)这个场景下堆的能力无可替代。5. 实战经验调试、测试、什么时候用哪种排序5.1 用四类测试集验证你的排序实现我在手写排序算法时从来不会只拿一个随机数组测一遍就说“搞定”。因为正确性验证需要覆盖不同的数据形态尤其是那些能把算法逼到最坏情况的形态。我建议你至少准备四类测试集随机数组、近乎有序的数组、包含大量重复值的数组、以及小规模数组。随机数组用来验证算法的普适正确性近乎有序的数组专门用来考验快排的退化风险和插入排序的自适应能力大量重复值的数组能暴露稳定性问题和分区不均问题小规模数组则用来验证边界条件比如 n0、n1、n2。测试的正确性判断不能光看最终结果是否有序还需要写一个校验函数检查每个元素是否都还在、是否出现了不该有的值覆盖。我踩过的坑就是归并排序的辅助数组下标没理清导致排序结果“看起来有序但其实少了元素”。另外我强烈建议你在学习阶段给算法加上“计数器”。比如在比较和交换的地方各加一个全局计数变量跑同一组数据观察不同算法的比较次数和交换次数。你会发现快排和归并的比较次数比冒泡少一到两个数量级这种直观感受比背任何结论都要深刻。5.2 常见bug与排查技巧实录排序算法代码量不大但该出的毛病一个都不少。我把这些年见到的典型问题和排查思路整理成了一个速查表症状常见原因排查与修复建议插入排序结果乱序内层 while 退出后位置赋错或比较符号写成了检查a[j1] key是否在正确位置保证稳定性快速排序在有序数组上极慢固定取左端为 pivot导致分区极端失衡改用随机 pivot 或三数取中面试时主动讲出这个风险点快速排序递归栈溢出数据量大且 pivot 选择不当递归深度接近 n设置最小阈值切换插入排序或改非递归栈实现归并排序结果丢失元素merge 时辅助数组长度或下标计算错误打印每轮 merge 前后的数组重点检查r - l 1和回填循环堆排序总是少排一个/堆顶错误建堆起始下标写成了 n/2或 siftDown 边界条件不对确认从n/2 - 1开始建堆检查右孩子是否存在希尔排序最后一轮后仍有错序gap 序列没有最终落到 1确保最后一次循环 gap 等于 1否则无法保证全局有序要特别说下快排栈溢出的问题。在面试里很多人一听到“递归版快排”就默认没问题但数据量达到几十万甚至上百万时系统栈可能扛不住。我的建议是面试写递归版可以但要主动说明生产环境会考虑阈值切换和非递归化这会成为明显的加分项。排查这类问题还有一个通用思路先缩小数据规模复现再打印关键循环中每个变量的变化比瞪着眼睛看代码高效得多。5.3 工程中的选型建议与C sort的隐藏优化看完七个排序的原理你可能会问那到底该用哪个我的实际建议很简单粗暴数据量很小比如小于几十个直接插入排序最省心。数据近乎有序插入排序几乎接近 O(n)。大规模一般场景优先快速排序但要处理好 pivot 选择和退化问题。有稳定性要求用归并排序尤其是多字段排序场景。内存极其紧张堆排序额外空间 O(1)。数据量大到内存装不下归并排序的外排思路。你可能已经发现了真正适合工程生产环境的其实没有一个算法是单独打天下。C 标准库里的std::sort就是一种混合策略快速排序作为主干当递归深度过深时切换堆排序避免最坏情况当区间长度小于一定阈值时切换插入排序利用它的低常数优势。这种混合设计的思路比背住任何一个算法本身都更有价值。还有一点容易被忽略std::stable_sort底层走的是归并排序路线用来保证稳定性。所以在 C 里遇到需要稳定排序的场景直接调stable_sort就是标准答案。Java 的Arrays.sort也类似对基本类型用双轴快速排序对对象类型用 TimSort一种优化归并背后都是同样的道理没有万能算法只有根据场景把多种算法组合起来的工程智慧。最后说个我个人的经验。手写这七个排序时我建议你按“冒泡 → 选择 → 插入 → 希尔 → 归并 → 快排 → 堆”的顺序推进因为后面每一个算法几乎都是前面某个算法的升级版。每学完一个就在纸上画出它的分区或合并过程再对着代码模拟一遍小数组的完整执行。排序算法这东西看得懂和写得对中间隔着很多次调试但只要这个坎迈过去了后面学任何算法都会顺畅得多。真遇到瓶颈时记住一个笨办法把数组缩小到 5 个元素手动模拟每一步的交换哪里卡住哪里就是你理解上的漏洞。