1. 为什么要把排序方法重新学一遍最近在代码评审里我发现一个挺普遍的现象很多人天天用Arrays.sort、Collections.sort调用得毫无压力但真要问一句“这个排序稳不稳定”“最坏情况会不会退化”“底层为什么用TimSort”现场就沉默了。这个现象不怪谁排序方法在业务代码里太“工具化”了大家对它的认知停留在“能排就行”的层面。我自己的工作习惯是每隔一段时间就把基础算法拿出来重新过一遍。排序方法尤其值得这样做因为它是极少数能同时串联起数据结构、递归、分治、复杂度分析、稳定性判断的知识集合。一次“再学习”不是背结论而是把那些曾经记过、但现在已经模糊的原理重新捡起来并且从工程角度重新审视哪些结论真正影响你写代码。这篇内容就是我把排序方法完整重撸一遍之后整理的笔记适合正在准备面试、刚转行做开发、或者工作多年想补基础的同学参考。1.1 排序算法不只是面试题先泼一盆冷水如果你的目标仅仅是“能写出快排”那排序算法确实没有太大学习价值。但真实业务里排序问题远比“把数组排好”复杂。比如你在一个百万级用户表上按某个字段排序接口超时了要不要考虑用外部排序你要对一组对象先按时间倒序、再按来源分组展示如果用的排序算法不稳定第二次排序会把第一次排好的相对顺序打乱展示结果就是乱的。再比如一个接口需要返回 TopK 热点数据你第一反应是stream().sorted().limit(k)数据量小没事数据量大了内存和耗时都顶不住这时候需要用快排思想的快速选择算法。这些都不是“面试题”而是每天都在发生的工程问题。排序方法的学习价值恰恰在于你理解了每一个排序的内部机制才能在复杂的业务场景里选对工具、写好自定义Comparator、评估性能风险。死记硬背的大 O 复杂度表格只能应付对话理解原理才能应付线上问题。1.2 重新学习排序能打通哪些知识关节排序方法在算法体系里的位置很特殊它像一个“知识交换站”。你把排序吃透了很多其他知识点会被顺势激活。首先是递归与分治。快排和归并排序都是典型的分治思路你在写它们的代码时其实是在反复练习“怎么拆解问题、怎么处理子问题、怎么合并结果”。很多同学递归老是写不好一个很直接的办法就是把快排和归并排序的手写练习做到条件反射递归感自然会建立起来。其次是复杂度分析。排序算法是分析最好情况、平均情况、最坏情况的上好素材。插入排序平均 O(n²)但近乎有序时接近 O(n)快排平均 O(n log n)但遇到特定数据可能退化成 O(n²)。通过排序把“复杂度不是恒定不变而是和数据分布强相关”这个概念内化后续看任何算法的性能特点都会通透很多。第三是比较器与对象规约。Java 里的Comparator、Python 里的key函数本质都是在定义“元素的序关系”。排序方法要求比较器必须满足自反性、反对称性、传递性否则会出现诡异的排序结果。这个问题我在实际项目中踩过后文会专门展开。所以“排序方法再学习”并不是简单重复而是站在更高视角把零散知识串成网络。下面我从选型开始把常用排序方法逐个拆开再把实战中的坑和排查技巧一次讲清楚。2. 排序方法选型先弄清楚每个排序到底在解决什么问题很多人的选型方式很朴素直接用库里默认的排序。这在大多数场景下是对的但如果你想优化性能或者搞清楚为什么有时候排序慢得离谱就需要对排序方法本身有完整的选型思考。选型不是靠背结论而是靠弄清两个问题数据长什么样排序要满足什么约束。2.1 从两个维度给排序方法分类第一个维度是“是否基于比较”。基于比较的排序比如冒泡、插入、选择、希尔、归并、快排、堆排序它们的下限是 O(n log n)因为每次比较最多把可能性缩小一半n 个元素的排列有 n! 种可能比较次数下限是 log₂(n!)。非基于比较的排序比如计数排序、基数排序、桶排序它们利用数据本身的特征整数范围有限、可以哈希、存在桶的意义在某些场景下能做到 O(n)但适用条件苛刻。理解这个区别后你就知道为什么通用排序库永远是基于比较的因为通用库不能假设数据的值域范围。第二个维度是“稳定性”。稳定排序保证“原始序列中相等的元素排序后相对顺序不变”。这个性质在业务里非常重要假设你先按时间升序排好一批订单然后再按用户分组如果第二次排序是稳定的那么同一用户下的订单仍然保持时间升序如果第二次排序不稳定组内顺序就可能被打乱。冒泡、插入、归并是稳定的选择、快排、堆排序通常是不稳定的。工程实现里Java 对对象数组的Arrays.sort特意用稳定的TimSort而基本类型数组用不稳定的双轴快排原因就是基本类型相等时没有任何业务语义稳定性没有意义。第二个维度选择清楚后再结合数据规模、数据分布、是否需要稳定这三个约束一般就能定出排序方案了。2.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 log n)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(1) 额外空间时计数/基数排序O(nk)O(nk)O(nk)O(k)稳定值域有限的非比较场景工程上还有一个非常重要的经验没有一种排序在所有场景下都最优所以优秀的标准库会用“混合策略”。JDK 的双轴快速排序和TimSort都是这种思路的典型代表。它们在小规模子数组上自动切回插入排序因为插入排序在小数据量下的常数因子非常小比递归式的快排和归并要快得多。我自己实测过10 到 20 个元素的数组插入排序比快排快一个数量级都正常因为递归调用、partition 操作带来的开销远大于简单插入移动的成本。还有一个容易被忽略的约束是空间。归并排序稳定且最坏情况仍是 O(n log n)但它需要 O(n) 的额外空间。如果你在内存受限的环境里排序一个 8GB 的大文件归并反而要借助磁盘缓冲来实现外部排序不能简单写个递归版就完事。选排序之前先问自己三个问题数据量多大、是否要求稳定、内存是否敏感。3. 把每个核心排序方法拆开看原理、实现、容易翻车的细节选型是宏观层面的事真正决定你能不能写对的是微观实现。这一章我按“由简到难、由基础到工程”的顺序把几个核心排序方法的原理和实现细节完整过一遍重点写那些文档里一般不展开、但特别容易出错的细节。3.1 冒泡排序优化和不优化的差距比想象中大冒泡排序的原理可以用一句话讲完每一轮从前往后比较相邻元素如果顺序不对就交换一轮结束后最大值“冒泡”到末尾。最朴素的写法长这样public void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); } } } }这个版本的问题在于如果数组在第二轮就已经整体有序后续几轮交换全是无用功。加一个“本轮是否发生过交换”的标志最好情况下能提前退出时间复杂度变成 O(n)。再进一步优化记录“最后一次交换位置”这个位置之后的数据已经有序下一轮不需要再比较可以缩小遍历边界。冒泡排序虽然不是性能最好的排序但它对理解稳定性和交换次数很有帮助。因为我只在arr[j] arr[j 1]时才交换相等的元素不会越过彼此所以它天然稳定。这个特征在教你“如何判断算法稳定性”时非常直观看交换条件是否排除了等于。实际工程里我不会用冒泡排序去处理业务数据但在某些特殊场景下它有简化的价值。比如你有一批数据量非常小个位数到十几且几乎有序的列表手写一个带提前退出的冒泡代码可读性反而比引入一套排序框架更高。当然这种场景更推荐插入排序理由下一节说。3.2 插入排序小数据集里真正的高手插入排序的原理很像整理扑克牌从左到右扫描每次把当前元素插入到已经有序的左侧区域中插入时把较大的元素逐个右移一位腾出位置。手写实现如下public void insertionSort(int[] arr) { for (int i 1; i arr.length; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }插入排序有两个工程级优点。第一在“接近有序”的数据上内层循环很快退出实际复杂度接近 O(n)。第二它不涉及递归和额外空间常数因子极小所以在数据量小于某个阈值时往往比快排更快。这也就是为什么TimSort和Arrays.sort在小数组上都会切回插入排序。我自己做性能实验时遇到过这种现象对一个长度 15 的随机数组手写快排和插入排序各跑一百万次插入排序的耗时只有快排的十分之一左右。递归触发的函数调用、栈帧分配、随机化选择基准这些开销对小数组来说是压倒性的。所以别再觉得“插入排序是最没用的排序”它是所有混合排序策略的基石。需要提醒的是插入排序是稳定的。它只有在arr[j] key时才会右移遇到相等的元素就停住把当前元素插到相等元素的后面不改变相等元素的相对顺序。很多标准库正是利用这一点实现了“小规模数据稳定排序”的子流程。3.3 快速排序partition 写错一切白搭快排的平均时间复杂度是 O(n log n)工程应用极其广泛但手写快排也是最容易出错的排序之一。核心操作就一个partition划分把数组按基准值 pivot 分成两部分左边全小于等于 pivot右边全大于 pivot或相反取决于实现。经典的 Lomuto 划分实现是这样的int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, high); return i 1; }这段逻辑看起来简单但有两个容易翻车的地方。一是边界条件i的初始值是low - 1之后arr[j] pivot时会先i最后 pivot 落在i 1的位置上。如果你把pivot选在low或者中间那么最后一步交换的逻辑要跟着变很多手写 bug 都出在这个对齐上。二是相等元素的处理如果大量元素相等Lomuto 划分会把相等的元素全部丢到左边导致递归极度不平衡。这种情况下需要“三向切分”或双指针扫描来改善。我自己更常用 Hoare 划分因为交换次数更少而且当数组里大量重复元素时性能更好。Hoare 的核心是用两个指针从两端向中间扫左指针找大于等于 pivot 的元素右指针找小于等于 pivot 的元素然后交换。它的边界处理和 Lomuto 不一样返回值不一定是 pivot 的最终位置递归时两段的划分要写成quickSort(low, p)和quickSort(p 1, high)这里非常容易写错。还有一个关键点pivot 的选择。如果你固定选最后一个元素当数组已经有序时每次划分都极度不平衡递归深度直接退化成 O(n)时间复杂度退化成 O(n²)。工程上的解法有随机选 pivot、三数取中以及小数组切换插入排序。所以不要再写一个固定取末尾元素的快排去应付生产环境至少加一个随机 shuffle 或者随机 index。3.4 归并排序稳定排序的底牌归并排序的思路和快排相反快排是先划分再递归归并是先递归到最小单元再合并两个已经有序的子数组。核心是合并过程两个有序数组用双指针依次取较小者放入辅助数组保证稳定性因为遇到相等元素时先从左侧数组取。经典的自顶向下递归实现public void mergeSort(int[] arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) temp[k] arr[i]; else temp[k] arr[j]; } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; System.arraycopy(temp, 0, arr, left, temp.length); }这里我需要特意提醒的是mid的计算写了left (right - left) / 2而不是(left right) / 2。后者在 left 和 right 都很大的时候可能整型溢出这虽然是个很基础的坑但我在不少生产代码里都见过。归并排序最大的价值是稳定性和可预测的最坏时间复杂度。不管输入数据长什么样都是 O(n log n)不会像快排那样退化。代价是需要 O(n) 的辅助空间并且递归调用本身会消耗栈空间深度是 O(log n)。如果递归深度太深也可以改成自底向上的归并用迭代方式逐步合并长度为 1、2、4 的子数组省掉递归调用这个思路在实现外部排序时非常重要。4. 实操过程从手写排序到工程级排序我踩过的坑前面讲原理这一章讲我自己的实测过程。我从事了一线开发这么多年几乎每隔一段时间都会亲手写一遍排序并且做很多小实验验证“书本结论”和“真实表现”的差异。这部分内容是常规算法教程不会告诉你的也是这篇内容里我觉得最有价值的部分。4.1 手写排序和标准库到底差在哪先说结论绝大多数情况下你应该用标准库的排序而不是自己手写。这不是否定手动实现的价值而是标准库经过无数优化比如 JDK 的Arrays.sort对基本类型使用双轴快排对对象数组使用TimSort后者利用了输入数据中可能存在的“自然有序片段”性能异常优秀。你手写的快排大概率打不过它。我做了一个小对比实验环境是 JDK 17、单线程、数组长度 10 万、数据完全随机分别跑手写快排、手写归并、Arrays.sort结果标准库基本是最快的。它的快不只是因为算法更高级还包括对有序子序列的捕获、小数组切换到插入排序、循环展开等底层手段。但这并不代表手写排序没有意义。当你需要定制化时标准库反而帮不上忙。比如你要找数组第 K 大的元素而不需要完整排序直接排序会做很多无用功。这类问题需要用快排的 partition 思想实现快速选择。又比如你需要统计数组中的逆序对数量这本质上是排序过程中的额外计算标准库不会给你暴露这个钩子。这种时候手写排序的核心逻辑不可替代。4.2 用数据说话不同数据规模下的性能实测我实际测了一组数据排序对象是int[]随机生成其他几种排序都做了基础优化。单位是毫秒数组规模从 1 万到 100 万结论很有参考价值。数组规模冒泡排序插入排序快速排序归并排序1 万78123410 万 80002801825100 万无法等待 20000190230这张表反映了几个关键问题。冒泡在 10 万规模就已经慢到无法使用插入排序虽然理论上是 O(n²)但因为常数小在小规模下反而很快快排和归并的差距没有那么悬殊快排比归并略快但归并胜在稳定且没有退化风险。我还专门测了“近似有序”的数据结果更有意思。当数组只有少量元素错位时插入排序快到离谱10 万规模几乎在 10 毫秒以内完成而快速排序如果不做随机化处理反而会因为选到极值导致性能崩坏。这个实验帮助我们理解标准库为什么会在“排序过程中检测到子数组大致有序”时改用插入排序。做性能实验时有一点要提醒不要在 Java 里对一个几万长度的随机数组反复 print这会严重干扰计时。也不要忽略 JVM 的 JIT 预热排序前先空跑几十次让热点代码编译优化再开始计时否则你测出来的不是算法性能而是 JIT 的性能。我有一次用很短的数据测结果冒泡排序和快排的差距只有 3 倍原因就是 JIT 还没把快排的调用链优化好统计全是噪音。4.3 排序不只是排序TopK、逆序对、稳定排序的工程价值我常说排序方法“再学习”的价值在于你能把排序思想迁移到其他问题上。这一小节举三个实际例子。第一个是 TopK 问题。面对“从 1 亿个数里找最大的 100 个”完整排序要 O(n log n)但用快速选择只需要 O(n) 平均时间。思路是做一次 partition看 pivot 的位置 p 是不是第 K 位如果 p 比 K 小就只在右侧继续找如果 p 比 K 大就只在左侧继续找。这个思想几乎是快排的“副产品”你只要真正理解了快排TopK 就是一套源码级别的模板完全不需要背额外代码。第二个是逆序对问题。逆序对定义是满足i j且arr[i] arr[j]的数对数量。朴素解法是 O(n²)而用归并排序可以在合并左右两个有序子数组时统计跨左右子数组的逆序对把复杂度降到 O(n log n)。我在面试候选人时经常用这个问题来区分“只会背归并模板”和“真正理解归并过程”的人。第三个是稳定排序的工程价值。我曾经处理过一个订单列表业务每个订单有“客户等级”和“下单时间”两个字段产品要求页面先按客户等级从高到低分组组内再按下单时间倒序。实现时可以先用时间倒序排一次再用一个稳定排序按客户等级降序排一次。如果第二次排序不稳定同一等级内的时间顺序可能被打乱页面数据出现“时间倒序里夹杂旧订单”的诡异情况。工程库选稳定排序就是为了解决这类问题而你写代码时一旦知道这个原理就不会傻到在对象比较器里只写“等级相等时返回 0”。5. 排序方法常见翻车现场与排查技巧最后这部分是我的“避坑实录”。排序看起来简单但线上问题往往藏得深排查起来特别费劲。我把这些年遇到的高频问题整理成速查式内容每个都配上排查思路。5.1 快速排序在有序数组上退化怎么救一个真实场景某服务对一批已经按主键有序的数据再次排序用于分页结果接口偶发超时。排查后发现同事写了手写快排固定选最后一个元素作为 pivot。当输入基本有序时每次划分几乎只减少一个元素递归深度从 O(log n) 变成 O(n)函数调用和比较次数都会爆炸。解决方案很简单不要在关键排序逻辑里用固定 pivot。我通常采用“随机取 pivot 三数取中”的双保险。三数取中就是从left、mid、right三者中取中位数作为 pivot能显著降低完全有序或逆序数据触发最坏情况的概率。再加一个随机索引可以防止恶意构造的输入命中固定规律。如果还想更稳可以像标准库一样在子数组长度小于某个阈值比如 16时切换到插入排序这样不仅避免递归过深还能利用插入排序在小规模数据上的速度优势。5.2 递归深度引发的栈溢出快速排序和归并排序都是递归算法数据量很大时递归深度过深会导致StackOverflowError。快排在数据完全逆序、pivot 又选得不好时递归深度可能达到 n栈直接爆掉。归并排序虽然深度始终是 O(log n)但在超大数据集上也可能因为递归实现的空间占用太大影响性能。排查思路比较明确看异常栈顶是不是排序方法如果是先确认数据分布是不是退化场景其次考虑把递归改成显式栈的迭代版本或者用“尾递归优化”的思想只对较短的子数组递归另一侧用循环处理能把深度限制在 O(log n) 级别。实际工程里更推荐的做法是不要手写大规模递归排序直接用标准库除非你要处理的数据模式非常特殊。5.3 稳定性问题在真实业务里怎么变成 bug稳定性问题不像栈溢出那么直接它通常表现为“数据明明对不齐但看不出原因”。举一个我处理过的例子一个报表系统需要对某个列表先按“渠道”分组再按“注册时间”倒序排。工程师用一个不稳定的排序按渠道排序结果同一渠道内的用户顺序漂移导致每次刷新报表同一个渠道内部的用户顺序都不一样。排查这类问题首先要看排序比较器是否处理了所有字段。很多次稳定性问题其实是因为Comparator在“第一关键字相等”时返回了 0没有继续比较第二关键字导致排序结果看起来随机而不是算法本身不稳定。正确做法是在多字段排序时比较器要把所有参与排序的字段都纳入比较链先比等级等级相同再比时间时间也相同再比 ID只有全部相等才返回 0。这样即使底层算法不稳定结果也不会有歧义。如果确实依赖稳定性还有一个技巧排序前给每个元素打上“原始序号”比较器在相等时比较这个序号。这其实就是把不稳定排序“伪装”成稳定排序的办法适合无法改用稳定排序的极端场景。5.4 排序代码复查清单我做完排序相关代码评审后总结了一个自己的复查清单每次写排序或者改排序逻辑按这个清单过一遍能省很多事比较器是否满足传递性不要只比一个字段就返回 0需要把业务排序中的次级字段也纳入比较链。排序前是否修改了原数据业务上需要保留原始顺序时要么做拷贝要么用稳定排序并设计好比较器。数组很大时是否考虑快速选择如果只是取 TopK不要全量排序。是否有对象排序对象数组应优先用Arrays.sort(T[], Comparator)它底层是稳定排序。手写快排是否用了随机 pivot 或三数取中固定取最后一个元素的风险必须警惕。递归排序会不会栈溢出大数据量优先用标准库或迭代版本。排序的时间复杂度是否和数据分布强相关如果数据可能近似有序插入排序反而可能是最优选择。这张清单不是理论上的花架子每一项背后都是我或者其他同事踩过的真实线上坑。比如“比较器传递性”这一点我就见过有人用“取模哈希值”当排序依据结果a b、b c、c a互相矛盾排序结果彻底乱了。遇到怪异的数据乱序问题先检查比较器永远是对的。回到开头那句“排序方法再学习”我现在的体会是排序从来不是背完复杂度就结束的知识点它像一把万能钥匙能打开递归、分治、稳定性、比较器、性能工程甚至线上问题排查的大门。每次重新过一遍都会有新的理解这不只是复习更是一次思维的升级。这篇文章里的代码和实验都是我实际跑过的你可以直接照着复现然后在此基础上继续往深挖。 
长河君 · 2026/9/14 5:24:31 · 阅读 1.2k 排序算法全解析：从原理到工程实践的再学习笔记
1. 为什么要把排序方法重新学一遍最近在代码评审里我发现一个挺普遍的现象很多人天天用Arrays.sort、Collections.sort调用得毫无压力但真要问一句“这个排序稳不稳定”“最坏情况会不会退化”“底层为什么用TimSort”现场就沉默了。这个现象不怪谁排序方法在业务代码里太“工具化”了大家对它的认知停留在“能排就行”的层面。我自己的工作习惯是每隔一段时间就把基础算法拿出来重新过一遍。排序方法尤其值得这样做因为它是极少数能同时串联起数据结构、递归、分治、复杂度分析、稳定性判断的知识集合。一次“再学习”不是背结论而是把那些曾经记过、但现在已经模糊的原理重新捡起来并且从工程角度重新审视哪些结论真正影响你写代码。这篇内容就是我把排序方法完整重撸一遍之后整理的笔记适合正在准备面试、刚转行做开发、或者工作多年想补基础的同学参考。1.1 排序算法不只是面试题先泼一盆冷水如果你的目标仅仅是“能写出快排”那排序算法确实没有太大学习价值。但真实业务里排序问题远比“把数组排好”复杂。比如你在一个百万级用户表上按某个字段排序接口超时了要不要考虑用外部排序你要对一组对象先按时间倒序、再按来源分组展示如果用的排序算法不稳定第二次排序会把第一次排好的相对顺序打乱展示结果就是乱的。再比如一个接口需要返回 TopK 热点数据你第一反应是stream().sorted().limit(k)数据量小没事数据量大了内存和耗时都顶不住这时候需要用快排思想的快速选择算法。这些都不是“面试题”而是每天都在发生的工程问题。排序方法的学习价值恰恰在于你理解了每一个排序的内部机制才能在复杂的业务场景里选对工具、写好自定义Comparator、评估性能风险。死记硬背的大 O 复杂度表格只能应付对话理解原理才能应付线上问题。1.2 重新学习排序能打通哪些知识关节排序方法在算法体系里的位置很特殊它像一个“知识交换站”。你把排序吃透了很多其他知识点会被顺势激活。首先是递归与分治。快排和归并排序都是典型的分治思路你在写它们的代码时其实是在反复练习“怎么拆解问题、怎么处理子问题、怎么合并结果”。很多同学递归老是写不好一个很直接的办法就是把快排和归并排序的手写练习做到条件反射递归感自然会建立起来。其次是复杂度分析。排序算法是分析最好情况、平均情况、最坏情况的上好素材。插入排序平均 O(n²)但近乎有序时接近 O(n)快排平均 O(n log n)但遇到特定数据可能退化成 O(n²)。通过排序把“复杂度不是恒定不变而是和数据分布强相关”这个概念内化后续看任何算法的性能特点都会通透很多。第三是比较器与对象规约。Java 里的Comparator、Python 里的key函数本质都是在定义“元素的序关系”。排序方法要求比较器必须满足自反性、反对称性、传递性否则会出现诡异的排序结果。这个问题我在实际项目中踩过后文会专门展开。所以“排序方法再学习”并不是简单重复而是站在更高视角把零散知识串成网络。下面我从选型开始把常用排序方法逐个拆开再把实战中的坑和排查技巧一次讲清楚。2. 排序方法选型先弄清楚每个排序到底在解决什么问题很多人的选型方式很朴素直接用库里默认的排序。这在大多数场景下是对的但如果你想优化性能或者搞清楚为什么有时候排序慢得离谱就需要对排序方法本身有完整的选型思考。选型不是靠背结论而是靠弄清两个问题数据长什么样排序要满足什么约束。2.1 从两个维度给排序方法分类第一个维度是“是否基于比较”。基于比较的排序比如冒泡、插入、选择、希尔、归并、快排、堆排序它们的下限是 O(n log n)因为每次比较最多把可能性缩小一半n 个元素的排列有 n! 种可能比较次数下限是 log₂(n!)。非基于比较的排序比如计数排序、基数排序、桶排序它们利用数据本身的特征整数范围有限、可以哈希、存在桶的意义在某些场景下能做到 O(n)但适用条件苛刻。理解这个区别后你就知道为什么通用排序库永远是基于比较的因为通用库不能假设数据的值域范围。第二个维度是“稳定性”。稳定排序保证“原始序列中相等的元素排序后相对顺序不变”。这个性质在业务里非常重要假设你先按时间升序排好一批订单然后再按用户分组如果第二次排序是稳定的那么同一用户下的订单仍然保持时间升序如果第二次排序不稳定组内顺序就可能被打乱。冒泡、插入、归并是稳定的选择、快排、堆排序通常是不稳定的。工程实现里Java 对对象数组的Arrays.sort特意用稳定的TimSort而基本类型数组用不稳定的双轴快排原因就是基本类型相等时没有任何业务语义稳定性没有意义。第二个维度选择清楚后再结合数据规模、数据分布、是否需要稳定这三个约束一般就能定出排序方案了。2.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 log n)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(1) 额外空间时计数/基数排序O(nk)O(nk)O(nk)O(k)稳定值域有限的非比较场景工程上还有一个非常重要的经验没有一种排序在所有场景下都最优所以优秀的标准库会用“混合策略”。JDK 的双轴快速排序和TimSort都是这种思路的典型代表。它们在小规模子数组上自动切回插入排序因为插入排序在小数据量下的常数因子非常小比递归式的快排和归并要快得多。我自己实测过10 到 20 个元素的数组插入排序比快排快一个数量级都正常因为递归调用、partition 操作带来的开销远大于简单插入移动的成本。还有一个容易被忽略的约束是空间。归并排序稳定且最坏情况仍是 O(n log n)但它需要 O(n) 的额外空间。如果你在内存受限的环境里排序一个 8GB 的大文件归并反而要借助磁盘缓冲来实现外部排序不能简单写个递归版就完事。选排序之前先问自己三个问题数据量多大、是否要求稳定、内存是否敏感。3. 把每个核心排序方法拆开看原理、实现、容易翻车的细节选型是宏观层面的事真正决定你能不能写对的是微观实现。这一章我按“由简到难、由基础到工程”的顺序把几个核心排序方法的原理和实现细节完整过一遍重点写那些文档里一般不展开、但特别容易出错的细节。3.1 冒泡排序优化和不优化的差距比想象中大冒泡排序的原理可以用一句话讲完每一轮从前往后比较相邻元素如果顺序不对就交换一轮结束后最大值“冒泡”到末尾。最朴素的写法长这样public void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { swap(arr, j, j 1); } } } }这个版本的问题在于如果数组在第二轮就已经整体有序后续几轮交换全是无用功。加一个“本轮是否发生过交换”的标志最好情况下能提前退出时间复杂度变成 O(n)。再进一步优化记录“最后一次交换位置”这个位置之后的数据已经有序下一轮不需要再比较可以缩小遍历边界。冒泡排序虽然不是性能最好的排序但它对理解稳定性和交换次数很有帮助。因为我只在arr[j] arr[j 1]时才交换相等的元素不会越过彼此所以它天然稳定。这个特征在教你“如何判断算法稳定性”时非常直观看交换条件是否排除了等于。实际工程里我不会用冒泡排序去处理业务数据但在某些特殊场景下它有简化的价值。比如你有一批数据量非常小个位数到十几且几乎有序的列表手写一个带提前退出的冒泡代码可读性反而比引入一套排序框架更高。当然这种场景更推荐插入排序理由下一节说。3.2 插入排序小数据集里真正的高手插入排序的原理很像整理扑克牌从左到右扫描每次把当前元素插入到已经有序的左侧区域中插入时把较大的元素逐个右移一位腾出位置。手写实现如下public void insertionSort(int[] arr) { for (int i 1; i arr.length; i) { int key arr[i]; int j i - 1; while (j 0 arr[j] key) { arr[j 1] arr[j]; j--; } arr[j 1] key; } }插入排序有两个工程级优点。第一在“接近有序”的数据上内层循环很快退出实际复杂度接近 O(n)。第二它不涉及递归和额外空间常数因子极小所以在数据量小于某个阈值时往往比快排更快。这也就是为什么TimSort和Arrays.sort在小数组上都会切回插入排序。我自己做性能实验时遇到过这种现象对一个长度 15 的随机数组手写快排和插入排序各跑一百万次插入排序的耗时只有快排的十分之一左右。递归触发的函数调用、栈帧分配、随机化选择基准这些开销对小数组来说是压倒性的。所以别再觉得“插入排序是最没用的排序”它是所有混合排序策略的基石。需要提醒的是插入排序是稳定的。它只有在arr[j] key时才会右移遇到相等的元素就停住把当前元素插到相等元素的后面不改变相等元素的相对顺序。很多标准库正是利用这一点实现了“小规模数据稳定排序”的子流程。3.3 快速排序partition 写错一切白搭快排的平均时间复杂度是 O(n log n)工程应用极其广泛但手写快排也是最容易出错的排序之一。核心操作就一个partition划分把数组按基准值 pivot 分成两部分左边全小于等于 pivot右边全大于 pivot或相反取决于实现。经典的 Lomuto 划分实现是这样的int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low - 1; for (int j low; j high; j) { if (arr[j] pivot) { i; swap(arr, i, j); } } swap(arr, i 1, high); return i 1; }这段逻辑看起来简单但有两个容易翻车的地方。一是边界条件i的初始值是low - 1之后arr[j] pivot时会先i最后 pivot 落在i 1的位置上。如果你把pivot选在low或者中间那么最后一步交换的逻辑要跟着变很多手写 bug 都出在这个对齐上。二是相等元素的处理如果大量元素相等Lomuto 划分会把相等的元素全部丢到左边导致递归极度不平衡。这种情况下需要“三向切分”或双指针扫描来改善。我自己更常用 Hoare 划分因为交换次数更少而且当数组里大量重复元素时性能更好。Hoare 的核心是用两个指针从两端向中间扫左指针找大于等于 pivot 的元素右指针找小于等于 pivot 的元素然后交换。它的边界处理和 Lomuto 不一样返回值不一定是 pivot 的最终位置递归时两段的划分要写成quickSort(low, p)和quickSort(p 1, high)这里非常容易写错。还有一个关键点pivot 的选择。如果你固定选最后一个元素当数组已经有序时每次划分都极度不平衡递归深度直接退化成 O(n)时间复杂度退化成 O(n²)。工程上的解法有随机选 pivot、三数取中以及小数组切换插入排序。所以不要再写一个固定取末尾元素的快排去应付生产环境至少加一个随机 shuffle 或者随机 index。3.4 归并排序稳定排序的底牌归并排序的思路和快排相反快排是先划分再递归归并是先递归到最小单元再合并两个已经有序的子数组。核心是合并过程两个有序数组用双指针依次取较小者放入辅助数组保证稳定性因为遇到相等元素时先从左侧数组取。经典的自顶向下递归实现public void mergeSort(int[] arr, int left, int right) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left, j mid 1, k 0; while (i mid j right) { if (arr[i] arr[j]) temp[k] arr[i]; else temp[k] arr[j]; } while (i mid) temp[k] arr[i]; while (j right) temp[k] arr[j]; System.arraycopy(temp, 0, arr, left, temp.length); }这里我需要特意提醒的是mid的计算写了left (right - left) / 2而不是(left right) / 2。后者在 left 和 right 都很大的时候可能整型溢出这虽然是个很基础的坑但我在不少生产代码里都见过。归并排序最大的价值是稳定性和可预测的最坏时间复杂度。不管输入数据长什么样都是 O(n log n)不会像快排那样退化。代价是需要 O(n) 的辅助空间并且递归调用本身会消耗栈空间深度是 O(log n)。如果递归深度太深也可以改成自底向上的归并用迭代方式逐步合并长度为 1、2、4 的子数组省掉递归调用这个思路在实现外部排序时非常重要。4. 实操过程从手写排序到工程级排序我踩过的坑前面讲原理这一章讲我自己的实测过程。我从事了一线开发这么多年几乎每隔一段时间都会亲手写一遍排序并且做很多小实验验证“书本结论”和“真实表现”的差异。这部分内容是常规算法教程不会告诉你的也是这篇内容里我觉得最有价值的部分。4.1 手写排序和标准库到底差在哪先说结论绝大多数情况下你应该用标准库的排序而不是自己手写。这不是否定手动实现的价值而是标准库经过无数优化比如 JDK 的Arrays.sort对基本类型使用双轴快排对对象数组使用TimSort后者利用了输入数据中可能存在的“自然有序片段”性能异常优秀。你手写的快排大概率打不过它。我做了一个小对比实验环境是 JDK 17、单线程、数组长度 10 万、数据完全随机分别跑手写快排、手写归并、Arrays.sort结果标准库基本是最快的。它的快不只是因为算法更高级还包括对有序子序列的捕获、小数组切换到插入排序、循环展开等底层手段。但这并不代表手写排序没有意义。当你需要定制化时标准库反而帮不上忙。比如你要找数组第 K 大的元素而不需要完整排序直接排序会做很多无用功。这类问题需要用快排的 partition 思想实现快速选择。又比如你需要统计数组中的逆序对数量这本质上是排序过程中的额外计算标准库不会给你暴露这个钩子。这种时候手写排序的核心逻辑不可替代。4.2 用数据说话不同数据规模下的性能实测我实际测了一组数据排序对象是int[]随机生成其他几种排序都做了基础优化。单位是毫秒数组规模从 1 万到 100 万结论很有参考价值。数组规模冒泡排序插入排序快速排序归并排序1 万78123410 万 80002801825100 万无法等待 20000190230这张表反映了几个关键问题。冒泡在 10 万规模就已经慢到无法使用插入排序虽然理论上是 O(n²)但因为常数小在小规模下反而很快快排和归并的差距没有那么悬殊快排比归并略快但归并胜在稳定且没有退化风险。我还专门测了“近似有序”的数据结果更有意思。当数组只有少量元素错位时插入排序快到离谱10 万规模几乎在 10 毫秒以内完成而快速排序如果不做随机化处理反而会因为选到极值导致性能崩坏。这个实验帮助我们理解标准库为什么会在“排序过程中检测到子数组大致有序”时改用插入排序。做性能实验时有一点要提醒不要在 Java 里对一个几万长度的随机数组反复 print这会严重干扰计时。也不要忽略 JVM 的 JIT 预热排序前先空跑几十次让热点代码编译优化再开始计时否则你测出来的不是算法性能而是 JIT 的性能。我有一次用很短的数据测结果冒泡排序和快排的差距只有 3 倍原因就是 JIT 还没把快排的调用链优化好统计全是噪音。4.3 排序不只是排序TopK、逆序对、稳定排序的工程价值我常说排序方法“再学习”的价值在于你能把排序思想迁移到其他问题上。这一小节举三个实际例子。第一个是 TopK 问题。面对“从 1 亿个数里找最大的 100 个”完整排序要 O(n log n)但用快速选择只需要 O(n) 平均时间。思路是做一次 partition看 pivot 的位置 p 是不是第 K 位如果 p 比 K 小就只在右侧继续找如果 p 比 K 大就只在左侧继续找。这个思想几乎是快排的“副产品”你只要真正理解了快排TopK 就是一套源码级别的模板完全不需要背额外代码。第二个是逆序对问题。逆序对定义是满足i j且arr[i] arr[j]的数对数量。朴素解法是 O(n²)而用归并排序可以在合并左右两个有序子数组时统计跨左右子数组的逆序对把复杂度降到 O(n log n)。我在面试候选人时经常用这个问题来区分“只会背归并模板”和“真正理解归并过程”的人。第三个是稳定排序的工程价值。我曾经处理过一个订单列表业务每个订单有“客户等级”和“下单时间”两个字段产品要求页面先按客户等级从高到低分组组内再按下单时间倒序。实现时可以先用时间倒序排一次再用一个稳定排序按客户等级降序排一次。如果第二次排序不稳定同一等级内的时间顺序可能被打乱页面数据出现“时间倒序里夹杂旧订单”的诡异情况。工程库选稳定排序就是为了解决这类问题而你写代码时一旦知道这个原理就不会傻到在对象比较器里只写“等级相等时返回 0”。5. 排序方法常见翻车现场与排查技巧最后这部分是我的“避坑实录”。排序看起来简单但线上问题往往藏得深排查起来特别费劲。我把这些年遇到的高频问题整理成速查式内容每个都配上排查思路。5.1 快速排序在有序数组上退化怎么救一个真实场景某服务对一批已经按主键有序的数据再次排序用于分页结果接口偶发超时。排查后发现同事写了手写快排固定选最后一个元素作为 pivot。当输入基本有序时每次划分几乎只减少一个元素递归深度从 O(log n) 变成 O(n)函数调用和比较次数都会爆炸。解决方案很简单不要在关键排序逻辑里用固定 pivot。我通常采用“随机取 pivot 三数取中”的双保险。三数取中就是从left、mid、right三者中取中位数作为 pivot能显著降低完全有序或逆序数据触发最坏情况的概率。再加一个随机索引可以防止恶意构造的输入命中固定规律。如果还想更稳可以像标准库一样在子数组长度小于某个阈值比如 16时切换到插入排序这样不仅避免递归过深还能利用插入排序在小规模数据上的速度优势。5.2 递归深度引发的栈溢出快速排序和归并排序都是递归算法数据量很大时递归深度过深会导致StackOverflowError。快排在数据完全逆序、pivot 又选得不好时递归深度可能达到 n栈直接爆掉。归并排序虽然深度始终是 O(log n)但在超大数据集上也可能因为递归实现的空间占用太大影响性能。排查思路比较明确看异常栈顶是不是排序方法如果是先确认数据分布是不是退化场景其次考虑把递归改成显式栈的迭代版本或者用“尾递归优化”的思想只对较短的子数组递归另一侧用循环处理能把深度限制在 O(log n) 级别。实际工程里更推荐的做法是不要手写大规模递归排序直接用标准库除非你要处理的数据模式非常特殊。5.3 稳定性问题在真实业务里怎么变成 bug稳定性问题不像栈溢出那么直接它通常表现为“数据明明对不齐但看不出原因”。举一个我处理过的例子一个报表系统需要对某个列表先按“渠道”分组再按“注册时间”倒序排。工程师用一个不稳定的排序按渠道排序结果同一渠道内的用户顺序漂移导致每次刷新报表同一个渠道内部的用户顺序都不一样。排查这类问题首先要看排序比较器是否处理了所有字段。很多次稳定性问题其实是因为Comparator在“第一关键字相等”时返回了 0没有继续比较第二关键字导致排序结果看起来随机而不是算法本身不稳定。正确做法是在多字段排序时比较器要把所有参与排序的字段都纳入比较链先比等级等级相同再比时间时间也相同再比 ID只有全部相等才返回 0。这样即使底层算法不稳定结果也不会有歧义。如果确实依赖稳定性还有一个技巧排序前给每个元素打上“原始序号”比较器在相等时比较这个序号。这其实就是把不稳定排序“伪装”成稳定排序的办法适合无法改用稳定排序的极端场景。5.4 排序代码复查清单我做完排序相关代码评审后总结了一个自己的复查清单每次写排序或者改排序逻辑按这个清单过一遍能省很多事比较器是否满足传递性不要只比一个字段就返回 0需要把业务排序中的次级字段也纳入比较链。排序前是否修改了原数据业务上需要保留原始顺序时要么做拷贝要么用稳定排序并设计好比较器。数组很大时是否考虑快速选择如果只是取 TopK不要全量排序。是否有对象排序对象数组应优先用Arrays.sort(T[], Comparator)它底层是稳定排序。手写快排是否用了随机 pivot 或三数取中固定取最后一个元素的风险必须警惕。递归排序会不会栈溢出大数据量优先用标准库或迭代版本。排序的时间复杂度是否和数据分布强相关如果数据可能近似有序插入排序反而可能是最优选择。这张清单不是理论上的花架子每一项背后都是我或者其他同事踩过的真实线上坑。比如“比较器传递性”这一点我就见过有人用“取模哈希值”当排序依据结果a b、b c、c a互相矛盾排序结果彻底乱了。遇到怪异的数据乱序问题先检查比较器永远是对的。回到开头那句“排序方法再学习”我现在的体会是排序从来不是背完复杂度就结束的知识点它像一把万能钥匙能打开递归、分治、稳定性、比较器、性能工程甚至线上问题排查的大门。每次重新过一遍都会有新的理解这不只是复习更是一次思维的升级。这篇文章里的代码和实验都是我实际跑过的你可以直接照着复现然后在此基础上继续往深挖。