讲排序之前先问个问题你写的Java程序里排序是直接调Arrays.sort还是Collections.sort如果是那你有没有想过JDK底层到底做了什么我见过不少开发者业务代码写得挺溜一问到排序就说不就是调个API嘛结果线上出现排序对不上、稳定性不对、性能莫名爆炸的时候只能干瞪眼。这篇就围绕排序Java这个主题把JDK内置排序的底层原理、手写排序算法的关键点、性能对比和实战坑位一次性讲清楚适合刚接触Java想弄懂排序原理的人也适合写了好几年业务代码但没系统梳理过排序底层的同学。1. 排序需求从哪来先想清楚你要排什么1.1 排序在业务里最常见的四种形态很多人聊排序就是背八股文但其实真实业务里的排序需求远不止让数组从小到大这么简单。我归纳了四类最常见的使用场景。第一类是列表展示类排序比如订单列表按创建时间倒序、商品列表按价格升序、报表按销售额降序这类排序强调稳定因为同时间或同价格的记录如果能保持原有顺序用户会更舒服也方便二次翻页。第二类是排行榜和TopK场景比如热销榜、积分榜通常只关心前N个不关心全局顺序这时候堆排序反而是更好的选择。第三类是去重和分组场景比如先排序再相邻比较去重或者按某个字段排序后做区间聚合这类操作依赖排序的正确性输出。第四类是二分查找的前提数据必须先排序才能用Arrays.binarySearch或Collections.binarySearch否则结果毫无意义。1.2 动手排序前先回答三个问题别急着写代码先问自己三个问题数据量有多大数据分布是什么样排序稳定性是否有要求我来解释一下为什么这三个问题这么关键。数据量决定算法选型几千条和几百万条的排序策略完全不同前者可能插入排序就够后者必须考虑O(nlogn)级别算法。数据分布决定性能表现一段几乎有序的数据用快速排序可能退化用插入排序或JDK的TimSort反而飞快而一组大量重复的数据则要考虑三路快排的思路否则稳定性无从谈起。稳定性决定字段顺序如果你要按多个字段依次排序且后面字段的排序不能打乱前面字段的顺序那必须选稳定排序。1.3 稳定性这个东西什么时候必须较真稳定性这个概念很多教程一笔带过但我发现它在真实项目里吃亏的人特别多。所谓稳定排序指的是相等元素在排序后保持原始相对顺序。Java的归并排序和插入排序是稳定的快速排序和堆排序是不稳定的。举个例子一个对象既有主分类ID又有分数。你想先按主分类分组再按分数排序。如果直接按分数排分类就没了如果先按分类排再按分数排不稳定排序会把第一次排好的分类顺序打乱结果就是同一分类下的记录在展示时顺序混乱。正确做法是用Comparator先按分类再按分数进行链式排序这样一次排序就搞定而且依赖的就是稳定性的保证。2. JDK内置排序别重复造轮子但你要知道轮子怎么转的2.1 Arrays.sort一套API两套实现Arrays.sort看起来是个简单调用但底层其实分了两条路。对于int[]、long[]、double[]这类基本类型数组JDK使用的是双轴快速排序Dual-Pivot Quicksort它的平均时间复杂度是O(nlogn)最坏情况经过优化后也可以控制到O(nlogn)级别优点是不需要额外开辟内存。对于Integer[]、String[]或任意对象数组JDK用的是TimSort这是一种结合了归并排序和插入排序的混合算法它的优势在数据部分有序时特别明显最坏也是O(nlogn)。为什么基本类型和对象类型要分开处理核心原因是稳定性。基本类型数组排序时相等的值没有区分度破坏稳定性无所谓但对象数组排序时两个对象即使比较字段相等它们在语义上依然是不同对象稳定排序能保证这些对象的原始顺序不被破坏。所以JDK选择了稳定排序方案来保障对象排序的正确性。2.2 Collections.sort 和 List.sort本质上还是走数组这条路Collections.sort在老版本的JDK里是直接转成数组排完再写回列表的新版本JDK则大多通过List.sort接口调用底层也是把列表元素转成数组后执行TimSort。我经常看到有人在这两个API之间纠结说实话它们的排序规则和性能表现基本一致选哪个主要看你的代码风格和JDK版本。还有一种情况要特别注意LinkedList这类链表的排序效率问题。虽然Collections.sort也能对链表排序但它需要把链表元素搬移到数组中再排序再回填这个搬移过程有额外的开销。如果你频繁对一个大链表排序建议换成ArrayList能省下不少时间。2.3 Stream.sorted函数式排序的坑现在很多人喜欢用stream().sorted()排序比如list.stream().sorted(Comparator.comparing(User::getAge)).collect(Collectors.toList())。这种写法的好处是代码非常简洁但有一个隐藏的问题sorted是一个有状态中间操作它不会像map那样逐条处理而是在流管道遇到终止操作时把整个流的数据收集到临时数组里排一次序然后再继续后续操作这意味着如果流后面还有大段处理逻辑数据会在排序时被整体缓冲。如果只是排序一次性能开销其实可以接受但如果在大数据量、高并发场景里频繁使用stream().sorted()就要注意评估内存分配和对象流转的开销。我个人的习惯是简单列表排序用List.sort或Arrays.sort追求代码可读性且数据量可控时才用Stream.sorted。2.4 并行排序不是所有数据都适合多线程JDK8开始提供了Arrays.parallelSort它会根据数据量判断是否通过ForkJoin公共池并行处理。好消息是基本类型数组的并行排序效果通常不错因为并行切分、归并的开销能被多核算力覆盖。坏消息是对象数组的并行排序使用TimSort的并行版本它需要更多临时数组和合并操作在数据量不够大时线程切换和等待开销反而可能超过收益。我实测过几十万条基本类型数组parallelSort能看得出优势但同样的数据量如果是对象数组收益就没那么明显。更稳妥的做法是数据量小于几万条直接串行排序几十万条以上再尝试并行并且要注意ForkJoin公共池是被整个JVM共享的如果其他业务也在用并行流公共池一旦拥挤排序任务可能被拖得很惨。3. 手写排序算法核心是理解比较与交换3.1 冒泡、选择、插入傻瓜三兄弟但有用很多人觉得冒泡排序毫无实用价值其实不然。冒泡排序的优势是原地排序 实现简单但它的交换次数太多大数据量基本没法用。选择排序每次选最小值放到前面比较次数固定但交换次数少适合交换代价高的场景。插入排序则是最被低估的简单排序它在数据基本有序时时间复杂度可以逼近O(n)而且稳定、原地、实现简单JDK的TimSort在数据量小到一定程度时就是切成插入排序来收尾的。下面是三个排序的极简Java实现建议你手敲一遍// 冒泡排序相邻逆序则交换每轮把最大值冒到最后 public static void bubbleSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { boolean swapped false; for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped true; } } if (!swapped) break; // 没发生交换说明已经有序提前结束 } } // 选择排序每轮选择最小值的下标然后交换 public static void selectionSort(int[] arr) { int n arr.length; for (int i 0; i n - 1; i) { int minIdx i; for (int j i 1; j n; j) { if (arr[j] arr[minIdx]) minIdx j; } if (minIdx ! i) { int tmp arr[i]; arr[i] arr[minIdx]; arr[minIdx] tmp; } } } // 插入排序新元素不断向左移动到正确位置 public static void insertionSort(int[] arr) { int n arr.length; for (int i 1; i n; i) { int cur arr[i]; int j i - 1; while (j 0 arr[j] cur) { arr[j 1] arr[j]; j--; } arr[j 1] cur; } }3.2 快速排序性能强但别踩它的退化陷阱快速排序的分治思想很直观选一个基准数把小于基准的放左边大于基准的放右边然后递归处理左右两边。理想情况下每次划分都能平分数组时间复杂度O(nlogn)。但如果你每次选的基准都是最小值或最大值比如对已经有序的数组用固定的取第一个元素当基准策略那么快速排序会退化到O(n^2)这是我见过最容易翻车的地方。解决思路有两个一是三数取中取首、中、尾三个元素的中位数当基准大幅降低退化概率二是当递归划分后区间足够小改用插入排序收尾这也是很多工业级快排实现的做法。下面是一个带三数取中的快速排序示例public static void quickSort(int[] arr, int left, int right) { if (left right) return; if (right - left 16) { insertionSort(arr, left, right); // 小区间插排收尾 return; } int pivot medianOfThree(arr, left, right); // 三数取中 int i left, j right; while (i j) { while (arr[i] pivot) i; while (arr[j] pivot) j--; if (i j) { int tmp arr[i]; arr[i] arr[j]; arr[j] tmp; i; j--; } } quickSort(arr, left, j); quickSort(arr, i, right); }这里要注意快排不稳定。如果业务场景要求相同字段的对象保持原顺序就不要选快排。3.3 归并排序稳字当头空间换稳定归并排序的思路是先把数组不断对半分分到只剩一个元素再两两合并合并时逐个比较小大。它的时间复杂度稳定在O(nlogn)是稳定排序但代价是需要O(n)的额外空间来存储临时数组。在Java里TimSort本身就是归并排序的优化变体它加入了探测有序区间的能力如果数据天然存在连续上升或下降的片段它可以利用这些片段直接合并减少排序工作量。手写归并排序时最容易被忽略的是临时数组的复用如果每一次递归都新建临时数组GC压力会非常大。正确做法是在外层创建一个长度等于原数组的临时数组递归时复用只通过起始位置来区分区间。3.4 堆排序和TopK只关心前几个的时候别全排序堆排序利用二叉堆反复取出最大或最小元素来排序时间复杂度O(nlogn)而且原地排序不需要额外空间。它不稳定所以不适合需要保留相对顺序的场景。但堆排序在一个场景里特别有用TopK问题。比如一个100万条数据的列表你要找最大的10个。很多人直接全排序再取前10个这当然简单但时间复杂度和全排序一样浪费在大量不必要的小元素排序上。用堆的思路只需要维护一个大小为K的小顶堆遍历一遍数据比堆顶大就替换并调整堆整体时间复杂度O(nlogK)当K远小于n时收益非常明显。Java里可以直接用PriorityQueue实现public static ListInteger topK(int[] arr, int k) { PriorityQueueInteger heap new PriorityQueue(k); // 小顶堆 for (int v : arr) { if (heap.size() k) { heap.offer(v); } else if (v heap.peek()) { heap.poll(); heap.offer(v); } } return new ArrayList(heap); }4. 性能实测与关键参数选择4.1 不同数据规模下内置排序和手写排序的差距我拿一个模拟项目X做过一轮简单测试分别对一万、十万、一百万条随机整数排序对比Arrays.sort、手写快排、手写插入排序。结果一点都不意外一万条时手写快排和内置排序差别不大插入排序明显慢十万条时内置排序最快手写快排次之插入排序已经可以用惨不忍睹来形容一百万条时内置排序依然保持最优手写快排偶尔能追平但插入排序直接好几分钟出不了结果。这个结果说明一件事JDK内置排序已经针对大量场景做了精细优化不要轻易重复造轮子。你手写排序的价值在于理解原理以及在特殊场景下做定制而不是日常替代JDK。4.2 数据特性对排序的影响有序、逆序、重复值同样是十万条数据如果它本身几乎有序插入排序或TimSort走的是探测有序区间的捷径实际运行时间可能只有随机数据的几十分之一。反观快速排序如果基准选不好几乎有序的数据反而成了最坏情况退化成O(n^2)。大量重复值也是一个隐蔽的坑。快排在遇到全相等的数组时经典的单向划分会导致性能严重退化。解决办法是三路快排把数组严格分成小于、等于、大于基准的三块这样递归时中间段不必再处理。4.3 Comparator的写法三行代码可能让你丢线上数据手写Comparator是排序里Bug率最高的区域没有之一。第一个常见错误是返回值越界return a - b看起来很简洁但如果a是一个很大的正数b是一个很小的负数两者相减会溢出导致比较结果和你的预期完全相反。第二个常见错误是违反比较器的传递性。如果你想让null值排最后写成优先把null顶到最后其余按年龄升序但落到代码里分支顺序写错就可能出现A比B小、B比C小、但C比A小这种荒唐的比较关系JVM会直接抛出IllegalArgumentException: Comparison method violates its general contract!。正确的写法是用Integer.compare、Long.compare或者Comparator.comparing这类链式API让JDK帮你处理边界和组合逻辑// 推荐链式组合语义清晰不会溢出 list.sort(Comparator.comparing(User::getAge) .thenComparing(User::getName, Comparator.nullsLast(String::compareTo)));4.4 内存和GC归并排序临时数组的开销怎么估算TimSort和归并排序都需要额外的临时数组。假设你有一个包含10万个字符串对象的列表每个字符串平均占一点内存排序时JDK会再分配一块能放下这10万个引用的临时数组。如果元素本身是大对象临时数组只多占用引用空间这通常比复制元素自身的开销小得多。但如果你自己实现排序每次递归都新建数组那就麻烦了。比如对100万条数据归并排序如果递归里频繁分配临时数组JVM的Minor GC次数会肉眼可见地飙升。我建议所有手写归并排序都尽量复用同一个临时数组用System.arraycopy做片段拷贝既快又省。5. 常见问题与排查技巧实录5.1 Comparison method violates its general contract! 解决方案这是Comparator最经典的报错几乎每个用自写比较器的项目都会遇到一次。触发原因基本都是三个比较器不满足自反性、反对称性或传递性。典型场景就是某个字段可能为null你在compare里做了多层判断某个分支直接return 1或return -1导致两个元素互相比较时出现矛盾。排查技巧是写一个随机数据循环调用Collections.sort反复排序几十次每次都检查排序结果中相邻元素是否满足比较器的定义。如果比较器有传递性问题这种模糊测试能很快暴露。另外升级到新版本JDK后同样代码可能突然报这个异常因为JDK底层切换到了新的排序实现比如从快排切到TimSort对比较器的一致性校验更严格此时不要急着降级JDK先修比较器。5.2 对象排序和基本类型排序的区别为什么包装类型反而慢int[]排序直接操作连续内存缓存友好Integer[]排序不仅每次比较要拆箱还要交换引用访问模式更分散。我做过一个测试百万级数据排序Integer[]的耗时比int[]明显增加。如果性能敏感优先用基本类型数组。如果必须用对象可以考虑减少无意义的对象创建或者用并行排序做一些补偿。5.3 排序后再二分查找别忘了先排序也别自己写二分二分查找的思路很简单但自己手写容易写错边界。Java提供了Arrays.binarySearch和Collections.binarySearch前提是数据必须已经按相同比较规则排好序。我见过一个线上事故某同学先用Comparator.comparing(User::getAge)排序后面又用Comparator.comparing(User::getAge).thenComparing(User::getName)去二分查找结果不用想匹配率惨不忍睹。这里有一条铁律排序用的Comparator和查找用的Comparator必须是同一个。如果你要按年龄二分查找姓名排序时也要年龄 - 姓名链式排好才能保证查找逻辑成立。5.4 Comparable和Comparator用错了会连累TreeSet和TreeMap让自定义类实现Comparable接口还是单独写Comparator我的建议是如果这个类有天然的业务排序字段比如订单号、创建时间就实现Comparable如果同一个类在不同场景有不同排序规则字段A按时间排字段B按分数排那就提供多个Comparator。还有一个特别隐蔽的问题TreeSet和TreeMap判断元素是否相等完全依赖比较器返回0而不是equals方法。如果你实现了Comparable但compareTo只比较了业务排序字段而equals比较了全部字段就会出现两个对象业务字段相同但内容不同TreeSet却认为是同一个元素的Bug。所以compareTo和equals的语义要保持一致尤其做数据去重时要格外小心。5.5 不要在Comparator里做重活写Comparator时有些人偷懒直接在compare方法里解析日期字符串、调用远程接口或者做复杂计算。比如Comparator.comparing(s - parse(s.getTimeStr()))表面看没问题但排序过程中compare会被调用大量次数字符串日期每次都被重复解析性能会雪崩。正确做法是排序前先做一次预处理把比较需要的排序键提取成基本类型或简单对象比如把时间字符串预先解析成long时间戳缓存到临时对象里再基于long排序。我在实际业务里做过一次优化同样十万条数据解析日期字符串后排序从原来的一秒多降到几十毫秒差别非常大。最后再分享一点个人的实操体会我踩过不少排序的坑最深的感触是排序不是一个调API的动作而是一个贯穿数据结构、算法复杂度、内存模型和业务语义的系统问题。你不仅要会写Arrays.sort还要知道为什么对象数组要用稳定排序为什么Comparator不能随便写为什么复杂比较逻辑要提前提取排序键。把这些底层逻辑吃透之后再看任何排序问题你都能快速定位——是选型问题、数据分布问题还是比较器逻辑问题。写代码时多留心一眼Comparator的边界和稳定性排序这口饭就端稳了。