1. 从排序二接续先把你容易搞混的基础概念补齐1.1 相等元素的相对顺序笔试和业务里都容易忽略这个系列写到这里大部分经典排序算法都已经过了一遍但每次聊排序总有几个前置概念如果不先定准后面看源码、写比较器、刷题都会反复踩坑。第一个就是“相等元素排序后是否还能保持原来的先后位置”。说得直白一点假设你有一个学生列表先按学号排好再按成绩排序如果第二次排序时成绩相同的学生还保持第一次排序后的顺序那么最后得到的名单就是“先按成绩、再按学号”的复合排序。如果你用的排序算法不具备这个性质第二次排序会把学号信息打乱最后名单就只按成绩排序了。很多初学者容易在这里想当然既然都是排序结果看起来都一样顺序有什么所谓但在实际业务里比如订单先按时间入队、再按优先级处理或者报表里先按部门分组、再按金额排序这种“分阶段排序”非常依赖上述性质。判断一个排序能不能用除了时间复杂度和空间复杂度还需要把这一条纳入评估。插入排序、归并排序这类算法天然可以做到这种保留效果而快速排序如果换成分区写法就很难保证选择和堆排序更是普遍不能保证。这个差异不是玄学而是由算法实现过程中元素移动方式直接决定的。1.2 为什么基于比较的排序很难突破 O(n log n)另一个基础问题是复杂度下界。很多读者会问快速排序平均复杂度是 O(n log n)是否有更快的基于比较的通用排序理论上没有。原因在于“比较”这个操作本身的决策能力有限。每次比较只能产生“大于”或“小于”两种结果二选一所以 n 个元素的所有可能排列是 n! 种排序过程就像是一棵决策树要进行足够多的比较才能把唯一正确的排列确定下来。log2(n!) 的数量级就是 n log n。简记一下任何一次只比较两个元素的排序算法在最坏情况下至少要经过约 n log n 次比较否则无法区分所有可能的输入顺序。这不是说 O(n) 排序不存在。下界的前提是“只能通过元素之间的比较来决定顺序”如果你跳出这个限制比如利用元素取值范围、借助哈希桶、按位拆分处理就能设计出线性时间的排序方案也就是后面要说的计数排序、桶排序和基数排序。所以以后看排序题先条件反射一下输入是普通对象只能靠比较器排序那就老老实实按 O(n log n) 设计如果输入是有限范围内的整数或者可以拆分成固定位数的记录那就可以考虑非比较路线。2. JDK 里藏着的排序真相Arrays.sort 和 Collections.sort2.1 Object[] 和基本类型数组走的是完全不同的两套实现实际开发里我们绝大多数情况不会手写排序而是直接调 JDK 的方法。但很多老手也未必清楚Arrays.sort 背后其实是两套完全不同的逻辑。对 int、long、double 这些基本类型数组现代 JDK 用的是 DualPivotQuicksort也就是双基准快速排序的改良版默认按升序调整并且新版本里还加入了局部插入排序、计数排序等混合优化。它对基本类型的处理非常激进内存局部性好在数据量大且无序时表现很强。但它不保证保留相等元素的相对顺序因为基本类型本来也看不出“原始次序”排序结果里相等的值都是一样的没必要保留。对 Object[] 数组情况就不一样了。Arrays.sort(Object[]) 以及 Collections.sort 底层依赖的是 TimSort这是一种合并排序的优化版本它的核心思路是把数组里已经有序的连续片段识别出来称为 run再用归并方式把这些 run 拼接成完整有序序列。TimSort 一个很大的优势是能利用输入数据中已有的有序程度对部分有序数据速度非常快同时也能够保留相等元素的相对顺序。所以如果排序对象是引用类型而且后续还需要保持某种原始录入顺序使用默认排序可以得到这种保序效果。2.2 流式排序和 List.sort 的区别也要知道除了 Arrays日常用得多的还有 Stream.sorted 和 List.sort。Stream.sorted() 会把元素收集到数组后走同样的 TimSort所以它的行为基本等同于 Arrays.sort(Object[])但它消费的是流对象有额外装箱和分配成本。如果数据规模很小这点开销无所谓如果数据量大直接先把 List 转成基本类型数组再排序会更划算。List.sort 则是有趣的在 ArrayList 上它会调用 Arrays.sort而在 LinkedList 上会先把链表转成数组排序再把数组写回链表。很多人在 LinkedList 上直接调用 sort 会觉得慢其实慢的不是排序算法而是链表本身随机访问差JDK 内部帮你做了数组转换只是转换过程也有开销。我在项目里经常建议凡是需要多次排序或者排序后还要做二分查找的集合优先使用 ArrayList 而不是 LinkedList。排序算法依赖随机访问ArrayList 在内存里连续存储缓存命中率高排序性能往往能比 LinkedList 快一个数量级。这也是“数据结构”和“算法”真正结合的地方不是算法不行而是你选的数据结构放大了算法的劣势。2.3 自定义 Comparator 时最容易犯的三个错调用 Arrays.sort 传入自定义 Comparator是面试和工作中都很常见的写法但这里很容易翻车。第一个错误是直接用减法返回差值比如 (a, b) - a.val - b.val。当 a.val 和 b.val 一个接近 Integer.MAX_VALUE另一个接近 Integer.MIN_VALUE 时减法结果会溢出返回一个完全错误的正负号导致排序结果稀奇古怪。正确做法是用 Integer.compare 或 Comparator.comparingInt 包一层。第二个错误是忽略相等元素的处理导致排序方法抛出 “Comparison method violates its general contract” 异常。这个错误背后的原因是你的比较器不具备正确的自反性、对称性和传递性。比如说比较 A 和 B 时返回 0比较 B 和 C 时返回 0但比较 A 和 C 时却返回正数TimSort 内部检测到这种矛盾就会直接抛异常。解决方法是把比较逻辑拆成多个字段逐级定义规则保证所有比较结果都能自洽。第三个错误是返回布尔值而不是 int。有人写 (a, b) - a.score b.score这在 Java 里根本无法通过编译因为 lambda 需要的是 int 返回值。如果使用 boolean 比较方法必须用三元表达式包装成 1、0、-1。这三个坑看起来都很基础但它们几乎覆盖了我见过的八成排序报错场景。3. 线性时间排序算法在 Java 里的落地3.1 计数排序范围小、数据密时的必杀技计数排序的思路一句话就能说清楚如果待排序元素是取值范围有限的整数先统计每个值出现多少次再根据统计结果把元素放回正确位置。比如要对年龄排序年龄范围是 0 到 150那只需要一个长度为 151 的计数数组遍历一次原数组得到每个年龄的人数再按顺序回填整个排序就是 O(n k)k 是取值范围。这个复杂度里没有 log n所以比任何比较排序都快但它要求数据是整数且取值范围不能太大。我在竞赛和笔试环境里见过不少误用计数排序的案例。典型错误是题目给了一个 10 万长度的数组每个数却高达 10 的 9 次方然后贸然开一个 10 亿长度的计数数组直接内存溢出。正确做法是先看 value 的分布只有当 max - min 在可接受范围内时才用。实操时可以加一个偏移处理先找到最小值和最大值然后把每个数减去最小值再计数这样能进一步缩小数组长度。比如元素范围是 1000 到 2000计数数组长度只需要 1001。下面给一个可以直接跑的模板注意最后回填时要遍历计数数组而不是遍历原数组这样得到的序列才是升序public static void countingSort(int[] arr) { if (arr.length 1) return; int min arr[0], max arr[0]; for (int v : arr) { if (v min) min v; if (v max) max v; } int[] count new int[max - min 1]; for (int v : arr) { count[v - min]; } int idx 0; for (int i 0; i count.length; i) { while (count[i] 0) { arr[idx] i min; count[i]--; } } }这个模板省略了稳定性处理也就是说相等元素不会严格保持原顺序。如果业务里要求保留同一分数学生的原始次序需要在回填阶段改成“累加计数 从后往前放置”的标准写法这一步是计数排序进阶的关键建议自己手动推演一遍。3.2 桶排序给数据分堆堆内再排序桶排序可以理解为计数排序的一般化扩展。计数排序的每个“桶”只存一个值桶排序的每个“桶”则存储一个区间范围内的多个元素先把元素按区间分到不同桶再对每个桶内部排序。如果数据分布均匀每个桶里的元素数量差不多整体复杂度可以接近 O(n)。如果数据分布极端某个桶里装了几乎所有元素那桶内排序又退化成 O(n log n)所以桶排序的性能对数据分布非常敏感。实际工程里桶排序通常配合一个“桶内阈值”来控制。桶太多会浪费空间桶太少起不到分流作用。一个常用经验是桶数量取 n 的平方根或者根据具体数据取值范围把桶容量控制在 50 到 100 个元素以内。桶内排序可以用插入排序因为桶内元素少插入排序在小规模数据上的常数优势明显。这也是工程实践中的经典组合分布式桶 小范围插入排序。3.3 基数排序按位拆分的降维打击基数排序处理的是“单个关键字比较困难但拆成多个小关键字后比较容易”的数据。以十进制整数为例可以把整数拆成个位、十位、百位每次只按一位来排序。排序顺序通常从最低有效位到最高有效位用稳定的计数排序作为子过程。重点就在这里如果每轮子排序不能保持相等元素相对顺序那么高位的优先级就会覆盖低位的排序结果整个算法就失效了。在 Java 里写一个非负整数基数排序可以先确定最大值算出它的位数然后按位取数字。核心代码如下public static void radixSort(int[] arr) { if (arr.length 1) return; int max 0; for (int v : arr) max Math.max(max, v); for (int exp 1; max / exp 0; exp * 10) { countingSortByDigit(arr, exp); } } private static void countingSortByDigit(int[] arr, int exp) { int[] output new int[arr.length]; int[] count new int[10]; for (int v : arr) { count[(v / exp) % 10]; } for (int i 1; i 10; i) { count[i] count[i - 1]; } for (int i arr.length - 1; i 0; i--) { int digit (arr[i] / exp) % 10; output[count[digit] - 1] arr[i]; count[digit]--; } System.arraycopy(output, 0, arr, 0, arr.length); }从最低位开始、每一轮用稳定方式放置元素这两条是基数排序正确性的关键缺一不可。很多人套模板时忽略了对负数、字符串长度的处理导致输出错位。实际用的时候可以先处理符号位或者把负数统一加一个偏移量再排序。4. 把排序和数据结构结合堆排序、双端队列与外部排序4.1 用 PriorityQueue 实现堆排序的工程姿势堆排序在教科书里通常要求手写一个堆但在 Java 开发中更常见的做法是利用 PriorityQueue。它本质上是一个最小堆往队列里逐个加入元素再依次弹出就能得到升序序列。这个操作的时间复杂度是 O(n log n)空间复杂度是 O(n)优点是代码极其简洁而且不需要手写堆的上浮下沉逻辑。它在挑选前 k 个最大或最小元素时非常合适。如果你需要从海量数据里取最大的 10 个维护一个小顶堆堆顶是当前最小的候选每次来一个新元素只要比堆顶大就替换堆顶并调整整个过程只需要 O(n log k)而不是把全部数据完整排序。这属于数据结构辅助排序的典型场景。需要注意的是PriorityQueue 迭代顺序不等于堆序或者有序序列必须连续 poll 才能得到有序输出。很多新手在这里踩坑以为 foreach 遍历 PriorityQueue 得到的就是有序列表结果发现顺序完全不对。4.2 双端队列在分块排序中的妙用双端队列本身不是排序结构但它能很好地配合桶排序和基数排序落地。以基数排序为例每一轮按当前位分到 10 个桶如果使用普通数组桶需要反复扩容和搬移如果使用双端队列可以从队尾入队收集元素再按桶编号从队头依次取出天然形成一个稳定的流水线。整个过程不需要频繁移动元素数据进出顺序完全可控。我在实现一些自定义排序组件时曾经用双端队列模拟“双头归并”。具体思路是两个已排序的队列每次比较队首元素把较小的一个出队放到结果队列尾部直到其中一个队列为空再把另一个队列剩余元素整体搬到结果队尾。这个操作思路和归并排序一致但在流式数据、实时排行场景里比数组归并更容易实现因为你不需要一次性知道数据总长度。LinkedBlockingDeque 还能在多线程场景下作为生产者消费者之间的缓冲多个线程生产不同区间数据消费线程按排序规则取最小值这种模式也常被称为“多路归并的流式版本”。4.3 内存装不下时外部排序是怎么工作的当数据量大到内存放不下比如要对几十 GB 的日志文件按时间排序就必须走外部排序。外部排序的基本单位是“归并片段”先把大文件切分成多个小块每块可以完全读入内存在内存里排好序后写回磁盘形成多个有序的小文件。然后在内存允许的条件下同时打开多个有序文件每个文件读出一小段到缓冲区不断比较缓冲区里的最小值写入最终输出。这个过程叫多路归并。为什么这里要单独提外部排序因为它和普通排序最大的区别是 I/O 操作代价远高于内存比较。普通排序优化目标是减少比较次数外部排序优化目标变成了减少磁盘读写次数。现实解决方案里常见的手段包括用更大的缓冲区降低随机 I/O、对每个归并片段做压缩、利用 SSD 的顺序读写特性合理布局临时文件。如果理解不了可以把外部排序想象成合并多个已经按日期排好的打卡记录表格每次只从每张表格里撕一小块出来比大小撕得越整齐来回跑柜台取数据的次数就越少。5. 从面试和题型视角看排序的底层考点5.1 拿到排序题先判断这是“伪排序”还是“真排序”很多排序相关题目看起来在考排序实际上并不是要你写一个排序函数。比如“找到数组中第 k 大的元素”目标值可以通过快速选择、最小堆或二叉搜索树解决不需要完整排序。又比如“合并多个有序链表”考点是归并逻辑和堆的维护。再比如“判断是否存在重复元素”可以先排序再扫描也可以直接放 HashSet。刷题时如果看到排序先反问一句完整排序是必要操作吗有没有更轻量的解法这样可以避免在最简单的题上浪费时间。反之有些题目是典型的“真排序”比如给定一个字符串数组要求按照字典序排列或者给定一堆区间要求按开始位置排序再合并区间。这种时候不要自己造轮子利用 JDK 提供的稳定排序和自定义比较器即可重点在比较器规则要写对。5.2 序列升序题不能只会每次重新排最近在 OJ 平台看到一道很典型的题大意是小杨有一个包含 n 个正整数的序列 a计划对序列进行多次升序排序可能不同轮次只对某个区间排序。这种题一方面考基础排序实现另一方面考“多轮处理”时的效率意识。如果每轮都重新构造一个子数组并调用完整排序复杂度很容易超限。合理做法是按查询频率来选策略。如果只是单次全排序调用 Arrays.sort 就是最优解。如果是多次前缀或区间排序可以考虑维护一个有序版本或者用 TreeMap 分段统计每次输出时按有序 key 遍历。比如区间反复求第几个最小值最实用的方案是先把序列整体排序再通过二分定位区间边界。也就是说排序未必只发生一次你先找到一个平衡点让多次查询共用一次排序结果这才是出题人真正想考的“数据结构与算法结合”的能力。5.3 从蓝桥杯到面试题几个提效小习惯每次讲排序刷题我都会强调几个代码层面的习惯。第一优先使用基本类型数组而不是包装类数组避免自动装箱和拆箱。比如 List 排序会比 int[] 慢不少数据量超过十万时尤其明显。第二用原始数组存储中间结果避免在循环里加班 String 拼接或重复复制片段。第三自定义比较器时尽量提取字段值到局部变量不要在 compare 方法里每次都读取同一个对象的多个字段虽然功能一致但性能会受影响。还有一个很多人容易忽略的细节在循环里频繁调用 Collections.sort 或者 Arrays.sort 时如果每次排序的数据量都很小比如个位数规模的子数组直接手写插入排序可能比调用库函数更快。JDK 底层对微型数组也会做优化但经过一层方法调用和对象封装后常数开销可能超过插入排序本身。这种“数据量只有几个时别用重型工具”的意识不仅适用排序也适用于很多“看起来高大上”的方案。6. 排序实战里的常见问题与避坑笔记6.1 比较器违反契约一看到就想骂人的异常“Comparison method violates its general contract” 是个非常典型的排序运行时报错。场景通常是你要按照某个自定义规则排序对象但规则本身自相矛盾。举个例子如果比较规则是某个字段为 null 时返回 -1非 null 时按大小比较那么当两个对象都为 null 时可能出现 A 小于 B、B 小于 A 同时成立的情况。TimSort 扫描过程中发现这种不一致就会直接报错。排查这个问题建议先把比较器规则写在纸上逐条检查自反性、对称性和传递性。自反性指 A 和 A 比较必须返回 0对称性指 compare(A, B) 和 compare(B, A) 的符号互反传递性指如果 A 排在 B 前、B 排在 C 前那么 A 必须排在 C 前。null 值处理是重灾区最简单的方式是优先用 Comparator.nullsFirst 或 nullsLast 包装一层不要自己在规则里散落地判断。一旦怀疑比较器有问题先用一个几十条的小样本数据排序不像大规模数据那样难以追踪。6.2 整型溢出、重复值和正负号反转排序比较器里用 a.value - b.value 已经说过会造成溢出这里给一个具体例子a.value Integer.MAX_VALUEb.value -1a - b 会直接越过 int 边界变成负数结果导致大的值反而被排到前面。这种 bug 在随机数据里可能只偶尔出现线上环境数据一旦够大排序结果就可能悄然错误。最稳妥的做法是每次比较都用 Integer.compare或者包装成 Comparator.comparingInt。重复值也同样容易出问题。有些自定义排序在值相等时没有返回 0而是返回一个微小的正数或负数这在大部分数据下很难察觉但会让排序结果的不确定性极大。如果后续依赖稳定排队顺序这类潜在错误会带来数据错乱。我在本地测试时习惯特意构造一批完全相等的对象列表跑一次排序再把结果和原顺序对照看是否保持了原有次序。6.3 简单基准测试库函数什么时候不如手写我不止一次被问到“为什么我手写的快排跑不过 Arrays.sort”原因很简单JDK 的排序集合了大量针对不同数据规模、不同有序程度的优化还有 JIT 编译器对高频热点的优化个人手写版很难全面赶上。那什么时候手写反而有优势多数是数据结构特殊、比较标准特殊或者需要同时完成多个操作时比如数组本身就是链表结构排序必须原地搬指针这时手写归并会更容易控制链接关系。做基准测试时我一般固定数据规模和随机类型预热几轮后再计时。测试结果会出现一个明显规律基本类型数组排序性能普遍远好于对象数组排序而对象数组排序中无自定义比较器又要好于有自定义逻辑的比较器。原因在于比较器的调用需要额外执行虚拟方法分派性能损耗很大。因此排序类项目里如果可以做“先提取字段到基本类型数组排序后再关联回对象”的方案常常能换来明显的速度提升。这个优化思路不比研究排序算法本身复杂但在项目里产生的影响却非常直接。最后说一个我自己的习惯每次接到排序需求我先花五分钟搞清楚三个问题——数据是什么类型、数据规模大概多大、排序后需不需要保留原有先后顺序。回答完这三个问题再选算法和工具往往能回避大多数后续排查。这个习惯帮我少踩了很多坑建议你也试试。