排序算法写了快十年在各种项目里用过的排序实现少说也有几十种但每次遇到需要手写排序的场景还是会有人问我“排序到底要怎么学才扎实”这问题看起来基础真要回答得深入并不容易。这篇是这个系列第三篇前面聊过基础排序和希尔排序的思路这篇把归并、快排、堆排这三个进阶排序算法彻底讲透同时把非比较排序的适用边界和工程中的真实取舍也一并说清楚。如果你是准备面试的开发者或者正在业务系统里优化数据排序性能这篇应该能帮你省下不少摸索时间。我写技术文章有个习惯光讲原理不给代码是耍流氓光给代码不讲为什么还是耍流氓。所以每个算法都按照“直觉理解 - 实现细节 - 复杂度分析 - 容易踩的坑”这个顺序来展开最后再用一个真实的调试案例把这些点串起来。1. 归并排序递归拆分的稳定之选归并排序的思路一句话就能说清把一个数组分成两半分别排好再合并起来。但这句话背后藏着两个非常关键的设计决策搞懂它们你就真正理解了归并排序。1.1 归并排序的核心机制第一个决策是“拆到什么时候停”。标准实现是当子数组长度为1时自然有序递归天然终止。你可以把这个过程想象成一场淘汰赛先把32个人分成16组两两比赛胜者晋级再两两对决最终决出冠军。整个过程是自下而上的每一层的合并操作只处理有序的子序列所以合并时才能做到线性扫描。第二个决策是“合并时怎么做到稳定”。我见过很多人写归并排序时合并逻辑是这样的两个子数组从头开始比较谁小谁先进临时数组如果相等就取左边子数组的元素。这一步就是稳定性的全部秘密——只有严格做到“相等时先取左侧”才能保证相同元素的原始相对顺序不被破坏。你的业务如果在排序后还需要保留原始插入顺序归并排序这个特性就值回票价了。这里给出一个递归实现的标准写法注释里包含了关键边界条件的说明void merge_sort(int arr[], int left, int right) { if (left right) return; int mid left (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid 1, right); merge(arr, left, mid, right); } void merge(int arr[], int left, int mid, int right) { int len right - left 1; int *tmp (int *)malloc(len * sizeof(int)); int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) tmp[k] arr[i]; else tmp[k] arr[j]; } while (i mid) tmp[k] arr[i]; while (j right) tmp[k] arr[j]; for (int p 0; p len; p) arr[left p] tmp[p]; free(tmp); }注意求中点的写法mid left (right - left) / 2而不是(left right) / 2。后者在极端情况下可能溢出面试官很爱在这个点上埋坑。1.2 归并排序的时间复杂度递归形式的复杂度可以用主定理直接推出递推式是 T(n) 2T(n/2) O(n)解得 T(n) O(n log n)。这里的 n log n 是所有基于比较的排序算法理论上能达到的最优级别归并排序是最容易理解、最不容易写错的一个。但“最优复杂度”不等于“最优性能”。归并排序需要一个等长的临时数组空间复杂度是 O(n)。如果一个系统里数据量是几十万级别这还能接受如果数据量上千万内存占用就会成为现实问题。我在实际项目中遇到过这种情况明明排序本身很快但 GC 压力因为临时数组的频繁分配和释放上来了最后不得不换成其他策略。后面讲工程选择的时候会展开说。1.3 归并排序的复杂度深度解析再说一下为什么归并排序的复杂度稳定地是 O(n log n)。每层归并都会完整地扫描一遍所有元素这是 O(n)递归树有多少层数组每次折半所以层数是 log n 层。把“每层的扫描代价”和“层的数量”相乘就是 O(n log n)。这个复杂度没有最好和最坏之分——无论数据是已经排好序的还是完全逆序的归并排序都老老实实地执行同样的比较和搬运。这个特性既是优点也是缺点。优点是可预测不会像快排在某种特定输入下退化到 O(n²)缺点是它不会因为数据本身有序就“偷懒”。如果你的业务场景中很大一部分数据是接近有序的那归并排序可能并不是最优选择好的插入排序或优化的快速排序会表现更佳。1.4 非递归实现的注意点递归实现虽然好写但存在一个实际问题递归深度是 log n在数据量特别大的时候函数调用栈的深度会让人心里没底——虽然理论上 log n 已经很浅了但在一些调用栈空间受限的环境里还是建议用非递归版本。非递归实现的思路是自底向上合并先把数组看成 n 个长度为1的有序子数组第一轮两两合并成长度为2的子数组第二轮合并成长度为4的子数组直到整体有序。层数同样是 log n。我不建议在正式项目里用一个会爆栈的递归实现尤其当你无法控制数组规模上限时非递归版本更稳妥。void merge_sort_iterative(int arr[], int n) { int *tmp (int *)malloc(n * sizeof(int)); for (int width 1; width n; width * 2) { for (int left 0; left n; left width * 2) { int mid left width - 1; int right (left width * 2 - 1) (n - 1) ? (left width * 2 - 1) : (n - 1); if (mid right) merge(arr, left, mid, right); } } free(tmp); }唯一需要仔细处理的是末尾子数组长度不足的情况也就是right不能超过 n-1。这个 bug 是我当年自测时才发现的第一次写的时候直接在right处越界了。遇到这种细节问题最好的排查方式就是对长度为 3、5、7 这种非 2 的整数次幂的数组做一轮测试。2. 快速排序工程实现里的双刃剑如果要我选一个“面试最常考、工程最常用、但写对最不容易”的排序算法快速排序当之无愧。它的核心思想是分治但每个环节都有值得琢磨的细节。2.1 快速排序的核心机制快排的流程是选一个基准值pivot把数组分为左右两半左边都小于等于基准右边都大于等于基准然后递归排序左右两半。关键在于分区partition这一步——它决定了整个算法的效率和稳定性。你可能会想这和归并排序都是分治区别在哪归并排序是“先拆后合”拆分是天然的合并才是重头戏快排反过来“合并”是天然完成的因为左右两边排好后中间自然就是基准值的位置不需要额外的合并操作重头戏放在了怎么把数组按基准拆成两部分。2.2 快排的挖坑填充与函数解析单边循环和双边循环是实现分区的两种主流方式。单边循环思路简洁可读性好双边循环则通过两个指针从两端向中间扫。这里把双边循环的挖坑写法详细拆解一下因为它隐藏了很多边界陷阱。int partition(int arr[], int low, int high) { int pivot arr[low]; int i low; int j high; while (i ! j) { // 从右往左找小于 pivot 的值 while (i j arr[j] pivot) j--; if (i j) arr[i] arr[j]; // 从左往右找大于 pivot 的值 while (i j arr[i] pivot) i; if (i j) arr[j] arr[i]; } arr[i] pivot; return i; }三个关键细节值得高度关注第一基准值的选择。这里我直接用arr[low]做基准。如果原始数据是已排序的每次取arr[low]会导致分区极端不平衡递归深度变成 n复杂度退化为 O(n²)。为了避免这种情况通常会采用三数取中取左端、右端、中点三个数中的中间值作为基准或者随机选择基准值。工程实现中三数取中效果更稳因为它同时避免了随机数生成器带来的不可预测性。第二扫描顺序不能乱。上面代码里必须是先从右往左再从左往右。原因在于基准值已经被保存在 pivot 变量里arr[low]这个位置相当于一个“坑”。如果先从左往右扫就会把大于基准的值填入这个坑但此时还没从右边找到小于基准的值来填新坑逻辑就乱了。很多初学者在这个细节上栽过跟头。第三循环条件里必须带上i j。arr[j] pivot这个条件在遇到所有元素都大于基准时会一路走到数组末尾没有i j的保护就会越界。这不是理论风险而是实际写代码时最常见的 bug 来源。2.3 快排的复杂度深度解析快排的平均时间复杂度是 O(n log n)最坏情况 O(n²)空间复杂度是 O(log n)递归栈深度。为什么平均复杂度是 O(n log n)?每次分区操作扫描整个子数组是 O(n)分区结果理想的情况下数组对半分递归深度是 log n相乘就是 O(n log n)。最坏情况什么时候发生每次分区都极度不平衡比如一个子数组为空另一个子数组长度是 n-1。这种情况下递推式变成 T(n) T(n-1) O(n)解出来就是 O(n²)。三数取中策略并不能消灭最坏情况它只是让最坏情况更难出现。如果有人刻意构造数据让三数取中失效那就得靠随机化基准来兜底——我在安全相关的排序场景里见过这种对抗性输入不可不防。2.4 荷兰国旗问题与三路分区标准的双边循环分区把所有等于基准的值都放在某一侧这导致大量重复元素时分区效率下降。比如一个全部都是同一个数字的数组用标准快排每次分区都只能减少一个元素退化成 O(n²)。我实际测试过全等数组在十万级别时标准快排的表现直接让人失去耐心。解决思路是三路分区小于基准的放左边等于基准的放中间大于基准的放右边。这样一次分区就能把大量相等的元素都放在正确位置递归时只需要处理小于和大于两侧的子数组。这就是 Dijkstra 提出荷兰国旗问题的经典解法。三路快排在处理重复数据时优势明显但在数据几乎不重复时因为多了一次比较判断性能略低于普通快排。所以正统的工程选择是递归进入子数组时先判断数据规模规模小用插入排序数据中大量重复用三路快排普通场景用三数取中优化的标准快排。从语言标准库的角度看许多编程语言内置排序的实现都不是某一种排序算法而是一个混合策略。3. 堆排序不依赖递归的原地排序思路堆排序在面试题中出镜率极高但实际写起来的问题也多。很多人搞不定堆的调整逻辑反复调试就是不对。它和归并、快排最大的区别在于不依赖递归也不需要额外的大块内存——是一种原地排序算法。3.1 堆排序的核心机制堆排序依赖的数据结构是二叉堆。我们可以把数组看成一个完全二叉树下标为 i 的节点左孩子是 2i1右孩子是 2i2父节点是 (i-1)/2。堆排序分两个阶段先建堆再逐个取出堆顶元素。建堆的目标是让整个数组满足堆的性质每个父节点都大于等于它的子节点大顶堆。建堆不需要从根节点开始而要从最后一个非叶子节点开始向前依次做下沉调整。原因是叶子节点没有子节点天然满足堆的性质。最后一个非叶子节点的下标是 n/2 - 1。下沉操作是堆排序的灵魂把当前节点和它两个子节点中最大的比较如果父节点小于某个子节点就交换然后继续向下调整直到满足堆性质。这个操作本身就是 O(log n)因为树的高度是 log n。3.2 堆排序的实现细节void sift_down(int arr[], int start, int end) { int parent start; int child 2 * parent 1; while (child end) { // 选出两个子节点中较大的 if (child 1 end arr[child] arr[child 1]) child; // 父节点如果已大于子节点则无需调整 if (arr[parent] arr[child]) break; // 交换父节点和较大子节点 int tmp arr[parent]; arr[parent] arr[child]; arr[child] tmp; parent child; child 2 * parent 1; } } void heap_sort(int arr[], int n) { // 建堆从最后一个非叶子节点开始下沉 for (int i n / 2 - 1; i 0; i--) sift_down(arr, i, n - 1); // 排序把堆顶最大值交换到末尾缩小堆范围后重新下沉 for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; sift_down(arr, 0, i - 1); } }两个边界条件要特别小心。第一个是child 1 end的判断确保右孩子存在再比较第二个是交换后parent child必须继续向下走如果漏掉这行下沉过程就会提前终止恢复的堆性质不完整。这两个 bug 我在初学阶段都踩过后来排查出来的方式是在纸上画出数组对应的二叉树用具体的交换过程逐步核对。3.3 堆排序的复杂度深度解析堆排序的时间复杂度是 O(n log n)这包含两个部分建堆是 O(n)排序阶段执行 n-1 次下沉操作、每次下沉 O(log n)所以总复杂度是 O(n log n)。建堆为什么是 O(n)因为树越低层的节点数量越多但它们需要下沉的高度越短。具体的计算可以用“所有节点下沉高度总和”来证明结果是 2n 量级也就是 O(n)。空间复杂度方面堆排序是 O(1)完全原地排序。这在内存敏感的系统中有它的独特价值也是它能和快排、归并并称为三大 O(n log n) 排序算法的底气。不过实际性能上堆排序通常比快排慢一个常数因子。原因在于快排的访问模式是顺序的对 CPU 缓存友好堆排序则是在数组中跳跃式访问缓存命中率低。在大数据量排序时这个差异非常可观。3.4 堆排序的适用场景堆排序也有它的闪光场景当你不关心全局有序而只关心最大的 K 个元素时用大小为 K 的小顶堆扫描一遍数据复杂度是 O(n log K)而不是排序完整的 O(n log n)。我处理过的一个日志分析任务需要在几亿条记录中取出 top 100当时就是用一个小顶堆完成的处理时间从分钟级降到了秒级。另一个场景是优先级队列——所有需要动态取最大/最小元素的系统本质都是在维护一个堆。从这个意义上讲掌握堆排序不只是多会一种排序算法而是掌握了一种可复用的数据组织能力。4. 线性时间排序计数排序与桶排序的边界很多人一提到排序脑子里只有 O(n log n) 这件事。但有一类排序算法可以在特定条件下做到 O(nk) 的线性时间复杂度它们不走“比较”这条路。我在这部分要把计数排序和桶排序讲清楚同时强调它们适用的边界条件。4.1 计数排序的核心机制计数排序要求数据是范围有限的整数。思路是统计每个数值出现的次数再根据次数把元素放回原数组。比如要排序的数据值在 0 到 100 之间只需要一个长度 101 的计数数组扫描一遍原数组统计频次然后按顺序把数字逐个放回。这里的关键步骤是“累加计数数组”和“反向放置元素”。累加之后计数数组里每个位置的值表示“小于等于这个值的元素一共有多少个”这样当你从原数组末尾向前扫描时就能直接算出每个元素应该放到的最终位置。反向放置元素是为了保持排序的稳定性——相同值的元素在排序后能维持原有的相对顺序。void counting_sort(int arr[], int n, int max_val) { int *count (int *)calloc(max_val 1, sizeof(int)); int *output (int *)malloc(n * sizeof(int)); for (int i 0; i n; i) count[arr[i]]; for (int i 1; i max_val; i) count[i] count[i - 1]; for (int i n - 1; i 0; i--) { output[count[arr[i]] - 1] arr[i]; count[arr[i]]--; } for (int i 0; i n; i) arr[i] output[i]; free(count); free(output); }注意count[arr[i]] - 1这个下标计算。如果count[arr[i]]是累加后的值它表示“小于等于 arr[i] 的元素总个数”那么最后一个该值应该放在这个总个数减 1 的位置。每放一个元素计数就要减一否则下一个相同值会放到同一个位置。4.2 计数排序的边界条件计数排序最大的限制是“数据范围不能太大”。如果有一亿个数据但范围也是从 0 到一亿那么计数数组本身就要一亿个整数空间开销是 400MB 左右直接不可用。这就是典型的“范围爆炸”问题。所以使用计数排序前一定要估算数据范围。我的经验法则是如果 max_val 和 n 在同一个数量级计数排序的空间开销还能接受如果 max_val 比 n 大一个数量级以上就要考虑使用桶排序或直接放弃线性排序方案。4.3 桶排序把数据分块处理桶排序是计数排序在浮点数场景下的推广把数据均匀地分到若干个桶中每个桶内部单独排序最后把所有桶按顺序合并。比如排序 0 到 1 之间的浮点数可以按十分位分成 10 个桶每个桶内的数据用普通排序算法处理。桶排序的关键在于“数据分布要均匀”。如果数据严重倾斜比如 90% 的数据都落在同一个桶里那么大量数据会集中在一个桶内排序性能退化明显。实际应用中针对数据分布特征动态调整桶的大小和数量是常见的优化手段。我做过一次时间序列数据的排序处理数据点分布非常密集但有周期性波动。当时尝试了固定桶数的方案效果不理想后来改成根据分位数动态划分桶边界排序效率直接提升了一个量级。这说明桶排序不是简单的分桶而是要对数据分布有足够的理解。4.4 基数排序数字位数的魅力基数排序是另一种线性时间排序核心是按位处理先按最低有效位排序再按次低有效位排序直到最高位每次排序都使用稳定的排序算法通常是计数排序。数字位数决定排序轮数每轮都是 O(n)所以总复杂度是 O(dn)其中 d 是数字位数。我在实践中发现基数排序处理固定长度整数比如身份证号、银行卡号、编号时表现非常稳定因为它不依赖数据分布均匀只依赖位数。但如果数据位数差异很大效率就不如计数排序直观。选择合适的线性排序算法本质是在“数据特征”和“资源约束”之间做权衡。5. 稳定性、缓存与极端数据从排序题到工程决策算法题里的排序和工程里的排序差了不止一个“性能调优”的距离。理解这一点才算真正把排序用明白。这部分我从三个在面试和实战中都极其重要的角度切入稳定性为何关键极端输入如何应对以及内置排序函数到底做了什么。5.1 稳定性的业务价值稳定排序不是算法理论的偏执它在真实的业务场景中直接决定结果正确性。最经典的例子是“多关键字排序”你想先按时间排序再按优先级排序如果排序不稳定按优先级排序之后相同优先级的记录内部就可能乱掉时间顺序。我曾处理过一个交易订单列表先按用户分组再按订单时间排序。如果使用的不是稳定排序相同时间戳的订单相对顺序就无法保证从而影响后续对账和一致性检查。在这种场景下我宁可用归并排序牺牲一点性能也不愿用快排冒稳定性的风险。5.2 极端输入对排序性能的影响每种排序算法都有它的“天敌”算法最怕的输入后果快速排序已排序数组 固定取左端基准O(n²)递归深度接近 n插入排序完全逆序数组O(n²)每次插入都要搬移归并排序无复杂度稳定但没有偷懒能力堆排序无复杂度稳定但缓存不友好计数排序值域远大于数据量内存爆炸工程代码必须具备“输入感知能力”。我的做法是写一个排序入口函数先判断数据规模、值域、是否近似有序、是否有大量重复再决定使用哪种算法。对用户来说他感知到的就是一个快得合理的排序接口对我自己来说这避免了很多极端场景下的性能事故。5.3 为什么内置排序函数更快很多开发者觉得内置排序函数就是个黑盒事实上它们几乎都不是单一算法。以常见编程语言的内置排序为例内部按照数据量级和类型做了一个策略矩阵小数组直接用插入排序因为插入排序在小数据规模下的常数因子极小中等规模用快排大规模且要求稳定时切到归并。某些语言还实现了“混排”技术也就是在快排和堆排之间切换以保证最坏情况复杂度不超过 O(n log n)。我推荐的做法是能用内置排序就绝不用手写排序除非你有非常明确的定制需求。比如需要稳定排序但内置排序默认不稳定或者数据分布特殊导致内置排序性能不佳。这时候再考虑自定义排序策略而不是一上来就重复造轮子。5.4 排序策略选型对照这里把主流的排序策略做一个系统性的对照方便你在做技术选型时快速定位算法平均复杂度最坏复杂度空间稳定性适用场景插入排序O(n²)O(n²)O(1)稳定小规模、接近有序归并排序O(n log n)O(n log n)O(n)稳定大规模且要求稳定快速排序O(n log n)O(n²)O(log n)不稳定一般大规模排序三路快排O(n log n)O(n²)O(log n)不稳定大量重复元素堆排序O(n log n)O(n log n)O(1)不稳定内存受限、TopK计数排序O(nk)O(nk)O(k)稳定小范围整数桶排序O(nk)O(n²)O(nk)稳定均匀分布数据基数排序O(dn)O(dn)O(nk)稳定固定位数整数这张表是我多次在项目和技术方案评审中实际用到的每次都能帮团队快速收敛到合适的排序选型上。6. 调试排序代码的通用套路与我的排查实录排序算法代码短小精悍但正因为藏在细节里的陷阱多调试反而比写大型业务代码更磨人。我分享一个自己印象深刻的调试案例和一套通用的验证手段。6.1 一次由“等号”引发的区间错乱之前写一版三路快排处理一个含有大量重复元素的数组时结果总是差几个元素没排到位。我把出错的数据缩小到一个只有 12 个元素的例子在纸上手动推演了一遍才发现问题出在一个等号上// 注意 while 条件中的等号 while (cur right) { if (arr[cur] pivot) { swap(arr, left, cur); } else if (arr[cur] pivot) { swap(arr, cur, right--); } else { cur; } }最初我少写了一个关键的等号导致等于基准值的元素被错误地归入“大于基准”区域后续交换就把数组搅乱了。三路快排的边界条件里cur right这个等号直接决定了“尚未处理区”是否被完整遍历。我最终是靠一个最小可复现数据集定位出来的——这也是我想强调的经验一旦排序结果不对第一反应应该是把数据规模缩小再缩小缩到你能手动模拟的规模然后用纸笔或者打日志的方式逐步追踪。6.2 用随机测试验证排序逻辑排序代码写完光测一两个例子是不够的。我长期使用的验证套路是这样写一个生成随机数组的工具长度覆盖 0、1、2、3、10、100、1000 等边界值同时把几种特殊情况纳入测试矩阵——完全有序的数组、完全逆序的数组、所有元素相等的数组、只有一个元素不同的数组、值域远大于元素个数的数组。接下来把排序结果和系统内置的稳定排序结果做对比长度是否一致、每个位置的值是否一致、相同值的相对顺序是否被破坏需要额外校验稳定性。这套测试流程每次都能在几分钟内发现实现里的隐蔽问题比肉眼读代码高效得多。6.3 排序性能的粗测方法我在选型阶段还会做一次快速的性能粗测生成一个固定长度的随机数组对同一份数据分别跑不同排序算法记录耗时。虽然这只是单机单次的结果但足够用来发现数量级上的差异。比如十万级数据下O(n log n) 算法通常是毫秒级而 O(n²) 算法已经是秒级甚至更差。如果某个排序算法在这个规模下表现出明显异常就该回头排查是不是退化成了 O(n²)。有一点要注意性能测试要跑多次取平均值避免第一次调用时缓存预热、页面调度等因素干扰结果。我在对比快排和堆排时通常至少跑五轮交替测试而不是先跑完快排再跑堆排这样可以抵消环境波动。6.4 从排序代码到系统能力的延伸写完一种排序算法不只是会了一个算法而是掌握了一套验证方法、一套边界思维和一套性能分析手段。我见过不少开发者能把快排代码背得滚瓜烂熟但问他“为什么取中点的算式要减一”“为什么右指针要先走”“为什么相等时要取左侧元素”就答不上来。这些细节不是刁难人的面试题而是真正的工程经验沉淀。我还想多说一句排序算法和系统设计是相通的。分区思想对应着分布式系统的分片和负载均衡归并思想对应着 MapReduce 里的 Merge 阶段堆结构对应着各种优先级调度器。把排序学深一点后面理解很多系统组件都会快得多。7. 排序题的五层进阶路径最后把排序学习的路径整理一下。不是每个人都需要从头到尾掌握每一个细节但知道自己在哪个阶段、下一步往哪走学习效率会高很多。7.1 第一层能写、能讲这一层的要求是能独立写出插入排序、冒泡排序、选择排序、归并排序、快速排序、堆排序的标准实现并能说清每种算法的基本思想和复杂度。很多人卡在这一层就止步了面试时能写出快排但说不好为什么快排一般比归并快。我的建议是每学一个算法用十句话以内的口语描述它讲给没有编程背景的朋友听讲不顺就是还没真正理解。7.2 第二层能分析、能选型这一层的标志是面对一个具体的排序需求能快速判断该用哪个算法、为什么。比如数据接近有序时优先插入排序要求稳定时优先归并排序内存紧张时优先堆排序整数且范围有限时优先计数排序。能够做出合理选型说明你已经不是在背算法而是在用工程思维解决问题。7.3 第三层能优化、能变体这一层的核心能力是理解每个算法的优化空间。比如快排的三数取中和三路分区、归并排序的非递归实现和链表归并、插入排序的二分插入优化、计数排序的累加数组技巧。这些变体不是算法本身但它们是工程中真正提升性能的关键点。7.4 第四层能结合系统设计到达这一层排序不再只是一个独立函数而是一个可以嵌入系统的能力。比如在海量数据场景下外部排序用归并的思路把数据分块读入内存、排序、写回磁盘、最后多路归并在分布式系统中先在各节点局部排序再汇总后全局归并。这些场景是排序算法应用的最高频形态。7.5 第五层能创新这一层的人很少他们能针对新的数据形态设计新的排序方案。比如针对 GPU 的并行归并排序、针对 SSD 的读写友好型排序策略、针对专门硬件指令优化的排序实现。如果你一路走到这里排序对你来说就不再是“会不会”的问题而是“如何做得更快更好”的问题。排序这个主题看起来基础实际上越往深处越能体会到算法设计的精妙和工程实现的权衡。这个系列的第三篇到这里就写完了如果你把归并、快排、堆排和非比较排序这几块都自己动手实现一遍再用测试用例严格验证你的排序功底一定会超过绝大多数同行。下一篇如果继续写我想聊聊外部排序和海量数据的处理思路那会是一个更宏大也更贴近真实系统的话题。 
长河君 · 2026/10/14 16:19:13 · 阅读 1.2k 排序算法进阶：归并、快排、堆排与非比较排序实战解析
排序算法写了快十年在各种项目里用过的排序实现少说也有几十种但每次遇到需要手写排序的场景还是会有人问我“排序到底要怎么学才扎实”这问题看起来基础真要回答得深入并不容易。这篇是这个系列第三篇前面聊过基础排序和希尔排序的思路这篇把归并、快排、堆排这三个进阶排序算法彻底讲透同时把非比较排序的适用边界和工程中的真实取舍也一并说清楚。如果你是准备面试的开发者或者正在业务系统里优化数据排序性能这篇应该能帮你省下不少摸索时间。我写技术文章有个习惯光讲原理不给代码是耍流氓光给代码不讲为什么还是耍流氓。所以每个算法都按照“直觉理解 - 实现细节 - 复杂度分析 - 容易踩的坑”这个顺序来展开最后再用一个真实的调试案例把这些点串起来。1. 归并排序递归拆分的稳定之选归并排序的思路一句话就能说清把一个数组分成两半分别排好再合并起来。但这句话背后藏着两个非常关键的设计决策搞懂它们你就真正理解了归并排序。1.1 归并排序的核心机制第一个决策是“拆到什么时候停”。标准实现是当子数组长度为1时自然有序递归天然终止。你可以把这个过程想象成一场淘汰赛先把32个人分成16组两两比赛胜者晋级再两两对决最终决出冠军。整个过程是自下而上的每一层的合并操作只处理有序的子序列所以合并时才能做到线性扫描。第二个决策是“合并时怎么做到稳定”。我见过很多人写归并排序时合并逻辑是这样的两个子数组从头开始比较谁小谁先进临时数组如果相等就取左边子数组的元素。这一步就是稳定性的全部秘密——只有严格做到“相等时先取左侧”才能保证相同元素的原始相对顺序不被破坏。你的业务如果在排序后还需要保留原始插入顺序归并排序这个特性就值回票价了。这里给出一个递归实现的标准写法注释里包含了关键边界条件的说明void merge_sort(int arr[], int left, int right) { if (left right) return; int mid left (right - left) / 2; merge_sort(arr, left, mid); merge_sort(arr, mid 1, right); merge(arr, left, mid, right); } void merge(int arr[], int left, int mid, int right) { int len right - left 1; int *tmp (int *)malloc(len * sizeof(int)); int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) tmp[k] arr[i]; else tmp[k] arr[j]; } while (i mid) tmp[k] arr[i]; while (j right) tmp[k] arr[j]; for (int p 0; p len; p) arr[left p] tmp[p]; free(tmp); }注意求中点的写法mid left (right - left) / 2而不是(left right) / 2。后者在极端情况下可能溢出面试官很爱在这个点上埋坑。1.2 归并排序的时间复杂度递归形式的复杂度可以用主定理直接推出递推式是 T(n) 2T(n/2) O(n)解得 T(n) O(n log n)。这里的 n log n 是所有基于比较的排序算法理论上能达到的最优级别归并排序是最容易理解、最不容易写错的一个。但“最优复杂度”不等于“最优性能”。归并排序需要一个等长的临时数组空间复杂度是 O(n)。如果一个系统里数据量是几十万级别这还能接受如果数据量上千万内存占用就会成为现实问题。我在实际项目中遇到过这种情况明明排序本身很快但 GC 压力因为临时数组的频繁分配和释放上来了最后不得不换成其他策略。后面讲工程选择的时候会展开说。1.3 归并排序的复杂度深度解析再说一下为什么归并排序的复杂度稳定地是 O(n log n)。每层归并都会完整地扫描一遍所有元素这是 O(n)递归树有多少层数组每次折半所以层数是 log n 层。把“每层的扫描代价”和“层的数量”相乘就是 O(n log n)。这个复杂度没有最好和最坏之分——无论数据是已经排好序的还是完全逆序的归并排序都老老实实地执行同样的比较和搬运。这个特性既是优点也是缺点。优点是可预测不会像快排在某种特定输入下退化到 O(n²)缺点是它不会因为数据本身有序就“偷懒”。如果你的业务场景中很大一部分数据是接近有序的那归并排序可能并不是最优选择好的插入排序或优化的快速排序会表现更佳。1.4 非递归实现的注意点递归实现虽然好写但存在一个实际问题递归深度是 log n在数据量特别大的时候函数调用栈的深度会让人心里没底——虽然理论上 log n 已经很浅了但在一些调用栈空间受限的环境里还是建议用非递归版本。非递归实现的思路是自底向上合并先把数组看成 n 个长度为1的有序子数组第一轮两两合并成长度为2的子数组第二轮合并成长度为4的子数组直到整体有序。层数同样是 log n。我不建议在正式项目里用一个会爆栈的递归实现尤其当你无法控制数组规模上限时非递归版本更稳妥。void merge_sort_iterative(int arr[], int n) { int *tmp (int *)malloc(n * sizeof(int)); for (int width 1; width n; width * 2) { for (int left 0; left n; left width * 2) { int mid left width - 1; int right (left width * 2 - 1) (n - 1) ? (left width * 2 - 1) : (n - 1); if (mid right) merge(arr, left, mid, right); } } free(tmp); }唯一需要仔细处理的是末尾子数组长度不足的情况也就是right不能超过 n-1。这个 bug 是我当年自测时才发现的第一次写的时候直接在right处越界了。遇到这种细节问题最好的排查方式就是对长度为 3、5、7 这种非 2 的整数次幂的数组做一轮测试。2. 快速排序工程实现里的双刃剑如果要我选一个“面试最常考、工程最常用、但写对最不容易”的排序算法快速排序当之无愧。它的核心思想是分治但每个环节都有值得琢磨的细节。2.1 快速排序的核心机制快排的流程是选一个基准值pivot把数组分为左右两半左边都小于等于基准右边都大于等于基准然后递归排序左右两半。关键在于分区partition这一步——它决定了整个算法的效率和稳定性。你可能会想这和归并排序都是分治区别在哪归并排序是“先拆后合”拆分是天然的合并才是重头戏快排反过来“合并”是天然完成的因为左右两边排好后中间自然就是基准值的位置不需要额外的合并操作重头戏放在了怎么把数组按基准拆成两部分。2.2 快排的挖坑填充与函数解析单边循环和双边循环是实现分区的两种主流方式。单边循环思路简洁可读性好双边循环则通过两个指针从两端向中间扫。这里把双边循环的挖坑写法详细拆解一下因为它隐藏了很多边界陷阱。int partition(int arr[], int low, int high) { int pivot arr[low]; int i low; int j high; while (i ! j) { // 从右往左找小于 pivot 的值 while (i j arr[j] pivot) j--; if (i j) arr[i] arr[j]; // 从左往右找大于 pivot 的值 while (i j arr[i] pivot) i; if (i j) arr[j] arr[i]; } arr[i] pivot; return i; }三个关键细节值得高度关注第一基准值的选择。这里我直接用arr[low]做基准。如果原始数据是已排序的每次取arr[low]会导致分区极端不平衡递归深度变成 n复杂度退化为 O(n²)。为了避免这种情况通常会采用三数取中取左端、右端、中点三个数中的中间值作为基准或者随机选择基准值。工程实现中三数取中效果更稳因为它同时避免了随机数生成器带来的不可预测性。第二扫描顺序不能乱。上面代码里必须是先从右往左再从左往右。原因在于基准值已经被保存在 pivot 变量里arr[low]这个位置相当于一个“坑”。如果先从左往右扫就会把大于基准的值填入这个坑但此时还没从右边找到小于基准的值来填新坑逻辑就乱了。很多初学者在这个细节上栽过跟头。第三循环条件里必须带上i j。arr[j] pivot这个条件在遇到所有元素都大于基准时会一路走到数组末尾没有i j的保护就会越界。这不是理论风险而是实际写代码时最常见的 bug 来源。2.3 快排的复杂度深度解析快排的平均时间复杂度是 O(n log n)最坏情况 O(n²)空间复杂度是 O(log n)递归栈深度。为什么平均复杂度是 O(n log n)?每次分区操作扫描整个子数组是 O(n)分区结果理想的情况下数组对半分递归深度是 log n相乘就是 O(n log n)。最坏情况什么时候发生每次分区都极度不平衡比如一个子数组为空另一个子数组长度是 n-1。这种情况下递推式变成 T(n) T(n-1) O(n)解出来就是 O(n²)。三数取中策略并不能消灭最坏情况它只是让最坏情况更难出现。如果有人刻意构造数据让三数取中失效那就得靠随机化基准来兜底——我在安全相关的排序场景里见过这种对抗性输入不可不防。2.4 荷兰国旗问题与三路分区标准的双边循环分区把所有等于基准的值都放在某一侧这导致大量重复元素时分区效率下降。比如一个全部都是同一个数字的数组用标准快排每次分区都只能减少一个元素退化成 O(n²)。我实际测试过全等数组在十万级别时标准快排的表现直接让人失去耐心。解决思路是三路分区小于基准的放左边等于基准的放中间大于基准的放右边。这样一次分区就能把大量相等的元素都放在正确位置递归时只需要处理小于和大于两侧的子数组。这就是 Dijkstra 提出荷兰国旗问题的经典解法。三路快排在处理重复数据时优势明显但在数据几乎不重复时因为多了一次比较判断性能略低于普通快排。所以正统的工程选择是递归进入子数组时先判断数据规模规模小用插入排序数据中大量重复用三路快排普通场景用三数取中优化的标准快排。从语言标准库的角度看许多编程语言内置排序的实现都不是某一种排序算法而是一个混合策略。3. 堆排序不依赖递归的原地排序思路堆排序在面试题中出镜率极高但实际写起来的问题也多。很多人搞不定堆的调整逻辑反复调试就是不对。它和归并、快排最大的区别在于不依赖递归也不需要额外的大块内存——是一种原地排序算法。3.1 堆排序的核心机制堆排序依赖的数据结构是二叉堆。我们可以把数组看成一个完全二叉树下标为 i 的节点左孩子是 2i1右孩子是 2i2父节点是 (i-1)/2。堆排序分两个阶段先建堆再逐个取出堆顶元素。建堆的目标是让整个数组满足堆的性质每个父节点都大于等于它的子节点大顶堆。建堆不需要从根节点开始而要从最后一个非叶子节点开始向前依次做下沉调整。原因是叶子节点没有子节点天然满足堆的性质。最后一个非叶子节点的下标是 n/2 - 1。下沉操作是堆排序的灵魂把当前节点和它两个子节点中最大的比较如果父节点小于某个子节点就交换然后继续向下调整直到满足堆性质。这个操作本身就是 O(log n)因为树的高度是 log n。3.2 堆排序的实现细节void sift_down(int arr[], int start, int end) { int parent start; int child 2 * parent 1; while (child end) { // 选出两个子节点中较大的 if (child 1 end arr[child] arr[child 1]) child; // 父节点如果已大于子节点则无需调整 if (arr[parent] arr[child]) break; // 交换父节点和较大子节点 int tmp arr[parent]; arr[parent] arr[child]; arr[child] tmp; parent child; child 2 * parent 1; } } void heap_sort(int arr[], int n) { // 建堆从最后一个非叶子节点开始下沉 for (int i n / 2 - 1; i 0; i--) sift_down(arr, i, n - 1); // 排序把堆顶最大值交换到末尾缩小堆范围后重新下沉 for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; sift_down(arr, 0, i - 1); } }两个边界条件要特别小心。第一个是child 1 end的判断确保右孩子存在再比较第二个是交换后parent child必须继续向下走如果漏掉这行下沉过程就会提前终止恢复的堆性质不完整。这两个 bug 我在初学阶段都踩过后来排查出来的方式是在纸上画出数组对应的二叉树用具体的交换过程逐步核对。3.3 堆排序的复杂度深度解析堆排序的时间复杂度是 O(n log n)这包含两个部分建堆是 O(n)排序阶段执行 n-1 次下沉操作、每次下沉 O(log n)所以总复杂度是 O(n log n)。建堆为什么是 O(n)因为树越低层的节点数量越多但它们需要下沉的高度越短。具体的计算可以用“所有节点下沉高度总和”来证明结果是 2n 量级也就是 O(n)。空间复杂度方面堆排序是 O(1)完全原地排序。这在内存敏感的系统中有它的独特价值也是它能和快排、归并并称为三大 O(n log n) 排序算法的底气。不过实际性能上堆排序通常比快排慢一个常数因子。原因在于快排的访问模式是顺序的对 CPU 缓存友好堆排序则是在数组中跳跃式访问缓存命中率低。在大数据量排序时这个差异非常可观。3.4 堆排序的适用场景堆排序也有它的闪光场景当你不关心全局有序而只关心最大的 K 个元素时用大小为 K 的小顶堆扫描一遍数据复杂度是 O(n log K)而不是排序完整的 O(n log n)。我处理过的一个日志分析任务需要在几亿条记录中取出 top 100当时就是用一个小顶堆完成的处理时间从分钟级降到了秒级。另一个场景是优先级队列——所有需要动态取最大/最小元素的系统本质都是在维护一个堆。从这个意义上讲掌握堆排序不只是多会一种排序算法而是掌握了一种可复用的数据组织能力。4. 线性时间排序计数排序与桶排序的边界很多人一提到排序脑子里只有 O(n log n) 这件事。但有一类排序算法可以在特定条件下做到 O(nk) 的线性时间复杂度它们不走“比较”这条路。我在这部分要把计数排序和桶排序讲清楚同时强调它们适用的边界条件。4.1 计数排序的核心机制计数排序要求数据是范围有限的整数。思路是统计每个数值出现的次数再根据次数把元素放回原数组。比如要排序的数据值在 0 到 100 之间只需要一个长度 101 的计数数组扫描一遍原数组统计频次然后按顺序把数字逐个放回。这里的关键步骤是“累加计数数组”和“反向放置元素”。累加之后计数数组里每个位置的值表示“小于等于这个值的元素一共有多少个”这样当你从原数组末尾向前扫描时就能直接算出每个元素应该放到的最终位置。反向放置元素是为了保持排序的稳定性——相同值的元素在排序后能维持原有的相对顺序。void counting_sort(int arr[], int n, int max_val) { int *count (int *)calloc(max_val 1, sizeof(int)); int *output (int *)malloc(n * sizeof(int)); for (int i 0; i n; i) count[arr[i]]; for (int i 1; i max_val; i) count[i] count[i - 1]; for (int i n - 1; i 0; i--) { output[count[arr[i]] - 1] arr[i]; count[arr[i]]--; } for (int i 0; i n; i) arr[i] output[i]; free(count); free(output); }注意count[arr[i]] - 1这个下标计算。如果count[arr[i]]是累加后的值它表示“小于等于 arr[i] 的元素总个数”那么最后一个该值应该放在这个总个数减 1 的位置。每放一个元素计数就要减一否则下一个相同值会放到同一个位置。4.2 计数排序的边界条件计数排序最大的限制是“数据范围不能太大”。如果有一亿个数据但范围也是从 0 到一亿那么计数数组本身就要一亿个整数空间开销是 400MB 左右直接不可用。这就是典型的“范围爆炸”问题。所以使用计数排序前一定要估算数据范围。我的经验法则是如果 max_val 和 n 在同一个数量级计数排序的空间开销还能接受如果 max_val 比 n 大一个数量级以上就要考虑使用桶排序或直接放弃线性排序方案。4.3 桶排序把数据分块处理桶排序是计数排序在浮点数场景下的推广把数据均匀地分到若干个桶中每个桶内部单独排序最后把所有桶按顺序合并。比如排序 0 到 1 之间的浮点数可以按十分位分成 10 个桶每个桶内的数据用普通排序算法处理。桶排序的关键在于“数据分布要均匀”。如果数据严重倾斜比如 90% 的数据都落在同一个桶里那么大量数据会集中在一个桶内排序性能退化明显。实际应用中针对数据分布特征动态调整桶的大小和数量是常见的优化手段。我做过一次时间序列数据的排序处理数据点分布非常密集但有周期性波动。当时尝试了固定桶数的方案效果不理想后来改成根据分位数动态划分桶边界排序效率直接提升了一个量级。这说明桶排序不是简单的分桶而是要对数据分布有足够的理解。4.4 基数排序数字位数的魅力基数排序是另一种线性时间排序核心是按位处理先按最低有效位排序再按次低有效位排序直到最高位每次排序都使用稳定的排序算法通常是计数排序。数字位数决定排序轮数每轮都是 O(n)所以总复杂度是 O(dn)其中 d 是数字位数。我在实践中发现基数排序处理固定长度整数比如身份证号、银行卡号、编号时表现非常稳定因为它不依赖数据分布均匀只依赖位数。但如果数据位数差异很大效率就不如计数排序直观。选择合适的线性排序算法本质是在“数据特征”和“资源约束”之间做权衡。5. 稳定性、缓存与极端数据从排序题到工程决策算法题里的排序和工程里的排序差了不止一个“性能调优”的距离。理解这一点才算真正把排序用明白。这部分我从三个在面试和实战中都极其重要的角度切入稳定性为何关键极端输入如何应对以及内置排序函数到底做了什么。5.1 稳定性的业务价值稳定排序不是算法理论的偏执它在真实的业务场景中直接决定结果正确性。最经典的例子是“多关键字排序”你想先按时间排序再按优先级排序如果排序不稳定按优先级排序之后相同优先级的记录内部就可能乱掉时间顺序。我曾处理过一个交易订单列表先按用户分组再按订单时间排序。如果使用的不是稳定排序相同时间戳的订单相对顺序就无法保证从而影响后续对账和一致性检查。在这种场景下我宁可用归并排序牺牲一点性能也不愿用快排冒稳定性的风险。5.2 极端输入对排序性能的影响每种排序算法都有它的“天敌”算法最怕的输入后果快速排序已排序数组 固定取左端基准O(n²)递归深度接近 n插入排序完全逆序数组O(n²)每次插入都要搬移归并排序无复杂度稳定但没有偷懒能力堆排序无复杂度稳定但缓存不友好计数排序值域远大于数据量内存爆炸工程代码必须具备“输入感知能力”。我的做法是写一个排序入口函数先判断数据规模、值域、是否近似有序、是否有大量重复再决定使用哪种算法。对用户来说他感知到的就是一个快得合理的排序接口对我自己来说这避免了很多极端场景下的性能事故。5.3 为什么内置排序函数更快很多开发者觉得内置排序函数就是个黑盒事实上它们几乎都不是单一算法。以常见编程语言的内置排序为例内部按照数据量级和类型做了一个策略矩阵小数组直接用插入排序因为插入排序在小数据规模下的常数因子极小中等规模用快排大规模且要求稳定时切到归并。某些语言还实现了“混排”技术也就是在快排和堆排之间切换以保证最坏情况复杂度不超过 O(n log n)。我推荐的做法是能用内置排序就绝不用手写排序除非你有非常明确的定制需求。比如需要稳定排序但内置排序默认不稳定或者数据分布特殊导致内置排序性能不佳。这时候再考虑自定义排序策略而不是一上来就重复造轮子。5.4 排序策略选型对照这里把主流的排序策略做一个系统性的对照方便你在做技术选型时快速定位算法平均复杂度最坏复杂度空间稳定性适用场景插入排序O(n²)O(n²)O(1)稳定小规模、接近有序归并排序O(n log n)O(n log n)O(n)稳定大规模且要求稳定快速排序O(n log n)O(n²)O(log n)不稳定一般大规模排序三路快排O(n log n)O(n²)O(log n)不稳定大量重复元素堆排序O(n log n)O(n log n)O(1)不稳定内存受限、TopK计数排序O(nk)O(nk)O(k)稳定小范围整数桶排序O(nk)O(n²)O(nk)稳定均匀分布数据基数排序O(dn)O(dn)O(nk)稳定固定位数整数这张表是我多次在项目和技术方案评审中实际用到的每次都能帮团队快速收敛到合适的排序选型上。6. 调试排序代码的通用套路与我的排查实录排序算法代码短小精悍但正因为藏在细节里的陷阱多调试反而比写大型业务代码更磨人。我分享一个自己印象深刻的调试案例和一套通用的验证手段。6.1 一次由“等号”引发的区间错乱之前写一版三路快排处理一个含有大量重复元素的数组时结果总是差几个元素没排到位。我把出错的数据缩小到一个只有 12 个元素的例子在纸上手动推演了一遍才发现问题出在一个等号上// 注意 while 条件中的等号 while (cur right) { if (arr[cur] pivot) { swap(arr, left, cur); } else if (arr[cur] pivot) { swap(arr, cur, right--); } else { cur; } }最初我少写了一个关键的等号导致等于基准值的元素被错误地归入“大于基准”区域后续交换就把数组搅乱了。三路快排的边界条件里cur right这个等号直接决定了“尚未处理区”是否被完整遍历。我最终是靠一个最小可复现数据集定位出来的——这也是我想强调的经验一旦排序结果不对第一反应应该是把数据规模缩小再缩小缩到你能手动模拟的规模然后用纸笔或者打日志的方式逐步追踪。6.2 用随机测试验证排序逻辑排序代码写完光测一两个例子是不够的。我长期使用的验证套路是这样写一个生成随机数组的工具长度覆盖 0、1、2、3、10、100、1000 等边界值同时把几种特殊情况纳入测试矩阵——完全有序的数组、完全逆序的数组、所有元素相等的数组、只有一个元素不同的数组、值域远大于元素个数的数组。接下来把排序结果和系统内置的稳定排序结果做对比长度是否一致、每个位置的值是否一致、相同值的相对顺序是否被破坏需要额外校验稳定性。这套测试流程每次都能在几分钟内发现实现里的隐蔽问题比肉眼读代码高效得多。6.3 排序性能的粗测方法我在选型阶段还会做一次快速的性能粗测生成一个固定长度的随机数组对同一份数据分别跑不同排序算法记录耗时。虽然这只是单机单次的结果但足够用来发现数量级上的差异。比如十万级数据下O(n log n) 算法通常是毫秒级而 O(n²) 算法已经是秒级甚至更差。如果某个排序算法在这个规模下表现出明显异常就该回头排查是不是退化成了 O(n²)。有一点要注意性能测试要跑多次取平均值避免第一次调用时缓存预热、页面调度等因素干扰结果。我在对比快排和堆排时通常至少跑五轮交替测试而不是先跑完快排再跑堆排这样可以抵消环境波动。6.4 从排序代码到系统能力的延伸写完一种排序算法不只是会了一个算法而是掌握了一套验证方法、一套边界思维和一套性能分析手段。我见过不少开发者能把快排代码背得滚瓜烂熟但问他“为什么取中点的算式要减一”“为什么右指针要先走”“为什么相等时要取左侧元素”就答不上来。这些细节不是刁难人的面试题而是真正的工程经验沉淀。我还想多说一句排序算法和系统设计是相通的。分区思想对应着分布式系统的分片和负载均衡归并思想对应着 MapReduce 里的 Merge 阶段堆结构对应着各种优先级调度器。把排序学深一点后面理解很多系统组件都会快得多。7. 排序题的五层进阶路径最后把排序学习的路径整理一下。不是每个人都需要从头到尾掌握每一个细节但知道自己在哪个阶段、下一步往哪走学习效率会高很多。7.1 第一层能写、能讲这一层的要求是能独立写出插入排序、冒泡排序、选择排序、归并排序、快速排序、堆排序的标准实现并能说清每种算法的基本思想和复杂度。很多人卡在这一层就止步了面试时能写出快排但说不好为什么快排一般比归并快。我的建议是每学一个算法用十句话以内的口语描述它讲给没有编程背景的朋友听讲不顺就是还没真正理解。7.2 第二层能分析、能选型这一层的标志是面对一个具体的排序需求能快速判断该用哪个算法、为什么。比如数据接近有序时优先插入排序要求稳定时优先归并排序内存紧张时优先堆排序整数且范围有限时优先计数排序。能够做出合理选型说明你已经不是在背算法而是在用工程思维解决问题。7.3 第三层能优化、能变体这一层的核心能力是理解每个算法的优化空间。比如快排的三数取中和三路分区、归并排序的非递归实现和链表归并、插入排序的二分插入优化、计数排序的累加数组技巧。这些变体不是算法本身但它们是工程中真正提升性能的关键点。7.4 第四层能结合系统设计到达这一层排序不再只是一个独立函数而是一个可以嵌入系统的能力。比如在海量数据场景下外部排序用归并的思路把数据分块读入内存、排序、写回磁盘、最后多路归并在分布式系统中先在各节点局部排序再汇总后全局归并。这些场景是排序算法应用的最高频形态。7.5 第五层能创新这一层的人很少他们能针对新的数据形态设计新的排序方案。比如针对 GPU 的并行归并排序、针对 SSD 的读写友好型排序策略、针对专门硬件指令优化的排序实现。如果你一路走到这里排序对你来说就不再是“会不会”的问题而是“如何做得更快更好”的问题。排序这个主题看起来基础实际上越往深处越能体会到算法设计的精妙和工程实现的权衡。这个系列的第三篇到这里就写完了如果你把归并、快排、堆排和非比较排序这几块都自己动手实现一遍再用测试用例严格验证你的排序功底一定会超过绝大多数同行。下一篇如果继续写我想聊聊外部排序和海量数据的处理思路那会是一个更宏大也更贴近真实系统的话题。