先说一个很多人在面试或写代码时都会遇到的问题提到排序脑子里能冒出冒泡、选择、快排一大堆名字可真到项目里要对一个对象列表按下拉排序、对一串编号名称的字符串做自然排序、或者从海量数据里取TopK的时候反而不知道该用哪个甚至直接Collections.sort一把梭排序结果还不一定对。这篇内容不打算讲教科书上的全部排序算法而是围绕 Java 排序这条主线把工程里真正高频用到的算法、JDK 内置排序的底层原理、对象排序的坑、以及一道典型的 TopK 面试题都串起来配合可以直接复制运行的代码和排查经验帮你把这个熟悉的陌生人彻底搞清楚。无论你是刚学完 Java 基础的自学者还是准备面试的求职者亦或是在项目里被排序折腾过的开发这篇都值得收藏。排序在 Java 里的地位很微妙平时写业务代码一个order by一句sorted()就搞定了好像用不大到可一到面试、一到性能调优、一到数据量上来排序就成了绕不开的硬骨头。我见过太多人能把快速排序背得滚瓜烂熟却写不出一个不栈溢出的递归版本也见过不少人用Comparator排序时踩了int减法溢出或者相等元素次序变化的坑。所以这篇文章会更偏向原理实战避坑而不是枯燥地罗列十种算法的代码。1. 排序算法的核心选择逻辑1.1 先搞清楚你面对的是什么类型的数据在动手写任何排序代码之前我习惯先问自己三件事数据量有多大数据是基本类型还是对象有没有稳定性的要求这三个问题的答案直接决定了算法选型的方向。数据量这一条很多初学的人容易忽略。数据量在几十到几百这个量级时插入排序和冒泡排序的实际运行速度并不会比快排差太多因为它们的常数因子小不会引入递归调用和额外的数组拷贝开销。数据量到了几万、几十万O(n^2)级别的算法就开始肉眼可见地卡顿再往上到百万千万级别不仅要关注时间复杂度还得关注内存占用和数据局部性。HashMap那种哈希思想在这里帮不上忙因为排序要求的输出是一个全局有序序列而哈希只能做等值匹配。基本类型和对象的区别决定了排序的稳定性需求。所谓稳定性是指关键字相等的元素在排序后是否保持原来的相对顺序。举个生活化的例子一个班的学生先按学号排好序再按成绩排序如果用的是稳定排序那么成绩相同的学生依然会按学号从小到大排列如果用不稳定排序成绩相同的同学之间的顺序就可能被打乱。在 Java 里对int[]、long[]这种基本类型数组排序时不要求稳定JDK 使用了快速排序的变种而对Integer[]、String[]、对象数组排序时底层会用归并排序的变种就是为了保证稳定性。第三个问题是有没有稳定性要求这个实际问题比教科书上说的更普遍。你说两个学生成绩相等时谁在前重要吗单看一条记录不重要但在多级排序场景里就很重要了。比如先按部门排序再按员工入职时间排序如果第二层使用的排序算法不稳定那么同一个部门内部员工的时间顺序就可能错乱。所以 Java 在对象排序上默认保证稳定这一点在设计接口时就要心里有数。1.2 复杂度不是唯一标准常数因子和实际场景同样关键很多初学者拿时间复杂度当唯一尺子觉得快排最快所以处处用快排这是误区。时间复杂度的O表示法掩盖了大量细节它描述的是数据规模趋近无穷时的增长趋势而不是某个具体数据量下的真实耗时。快速排序在理想情况下是O(n log n)但它的递归调用、基准值选取、内存中的交换次数都会带来额外开销插入排序虽然最坏是O(n^2)但在几乎有序的数据上可以做到接近O(n)。我给你一个具体的感观。我用随机生成的 1 万条整数做了一次简单测试数据不极端、不算严格基准测试只是观察量级手写的简单插入排序大概耗时几个毫秒手写的经典快速排序固定取中间值为基准也是几个毫秒差距并不悬殊。但当数据量放大到 100 万时快排和归并的优势就彻底拉开了插入排序几乎要等几秒甚至更久。这个现象说明了一个工程经验数据量小的时候别迷信高级算法简单算法的低常数因子可能就是最优解数据量大的时候复杂度级别才是决定性的。这也是为什么 JDK 里会在小数组上退化为插入排序我会在后面的 JDK 排序原理一节详细讲。2. 常用排序算法的 Java 实现与原理拆解2.1 冒泡排序与选择排序教学常客工程弃卒冒泡排序的思路是相邻元素两两比较大的往后移每一轮把当前未排序区间的最大值冒泡到末尾。为什么说它是教学常客因为它直观地展示了比较-交换这个排序的本质是理解排序的第一块敲门砖。但它的交换操作太频繁了最坏情况下要做n(n-1)/2次交换每次交换都是一次数组写操作在现代 CPU 上这种随机内存访问的代价其实很大。选择排序在思路上比冒泡好一点每一轮找到最小值的下标只做一次交换。但它有个致命缺点——无论数据本来就多有序它都要做固定次数的比较O(n^2)的时间复杂度是死的不像插入排序那样可以提前终止。所以工程上几乎看不到这两个算法的影子JDK 再小的数组也不会用冒泡排序。不过面试中还是可能让你手写所以给出一个可运行的冒泡排序优化版本作为参考经典的冒泡排序在此基础上加了swapped标志位如果一轮下来没有任何交换说明序列已经有序可以提前跳出public static void bubbleSort(int[] arr) { if (arr null || arr.length 2) { return; } boolean swapped; for (int i 0; i arr.length - 1; i) { swapped false; for (int j 0; j arr.length - 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; } } }我面试候选人的时候如果让他写冒泡排序我最想看到的就是这个swapped优化和循环边界arr.length - 1 - i。前者考察对最好情况的理解后者考察对循环不变量的把握。很多人会把内层循环写成j arr.length - 1虽然结果一般也正确但多做了很多无用比较说明对每轮确定一个最大值、无需再参与比较这一点理解不到位。2.2 插入排序小数据量场景下的隐形王者如果说冒泡和选择是教学工具那插入排序就是第一个真正有工程价值的排序。它的思路和整理扑克牌一样从第二个元素开始逐个把它插入到前面已经有序的序列中。代码写起来极其简洁public static void insertionSort(int[] arr) { if (arr null || arr.length 2) { return; } for (int i 1; i arr.length; i) { int current arr[i]; int j i - 1; while (j 0 arr[j] current) { arr[j 1] arr[j]; j--; } arr[j 1] current; } }这个算法最漂亮的地方在于它的自适应能力当输入序列几乎有序时内层循环往往比较一两次就退出整体时间复杂度接近O(n)。这个特性被 JDK 的DualPivotQuicksort和TimSort都利用上了它们会在小数组或局部有序的子数组上调用插入排序。我自己在项目里对取最近历史数据按时间倒序这种场景做过测试数据量基本是一天内几百条用插入排序处理比引入一个完整排序框架要轻量得多。插入排序的另一个优势是稳定。它只在arr[j] current时移动元素相等时不动所以相同元素的相对位置不会改变。这点比选择排序好选择排序在交换时可能把相等的元素往前跳破坏稳定性。2.3 希尔排序插入排序的进阶版一种值得了解的中间方案希尔排序是插入排序的改进它把序列按一定增量分组对每组做插入排序然后逐步缩小增量直到增量为 1 时做一次完整的插入排序。这个思路的精髓在于增量大的时候元素可以跳跃式移动快速消除大量逆序对增量小的时候序列已经基本有序插入排序接近O(n)。所以希尔排序在中等规模数据上往往能跑到接近O(n log n)的水平而且不需要额外的内存空间。下面是一个常见的实现增量序列使用 Knuth 提出的h h * 3 1public static void shellSort(int[] arr) { if (arr null || arr.length 2) { return; } int h 1; while (h arr.length / 3) { h h * 3 1; } while (h 1) { for (int i h; i arr.length; i) { int current arr[i]; int j i; while (j h arr[j - h] current) { arr[j] arr[j - h]; j - h; } arr[j] current; } h h / 3; } }我在实际项目里很少单独用希尔排序因为 JDK 现有排序已经足够好。但如果你在某些嵌入式环境或者内存极受限的场景里写 Java不希望引入额外空间希尔排序会是一个不错的折中方案。它的不稳定是一个注意点因为分组插入时相等的元素可能被分到不同的组跳跃移动导致相对顺序改变。2.4 快速排序工程最常用的分治算法快排在大多数情况下是排序的首选尤其在基本类型排序上。它的思想是分治选一个基准值pivot把数组分成小于基准值和大于基准值的两部分再递归对两部分排序。关键操作是partition分区这一步让基准值落在最终位置上。我给出一个最常用的挖坑填数版实现这个方法在面试里写起来不容易出错public static void quickSort(int[] arr, int left, int right) { if (left right) { return; } int pivot arr[left]; int i left; int j right; while (i j) { while (i j arr[j] pivot) { j--; } if (i j) { arr[i] arr[j]; i; } while (i j arr[i] pivot) { i; } if (i j) { arr[j] arr[i]; j--; } } arr[i] pivot; quickSort(arr, left, i - 1); quickSort(arr, i 1, right); }注意这个实现里两个内层while循环都加了和的条件这是有讲究的。如果写成和等于基准值的元素会被不断地左右交换虽然结果不错但会引入大量无意义的交换而且如果所有元素都相等复杂度会退化到O(n^2)。用和可以让等于基准值的元素被分到某一侧减少了交换次数。但是快排有两个工程隐患。第一个是基准值选择如果每次选第一个或最后一个元素作为基准当数据本身有序或倒序时分区极度不平衡递归深度接近n时间复杂度退化为O(n^2)递归调用还可能抛出StackOverflowError。常见的优化方法有三个随机选取基准值、取首中尾三个元素的中位数作为基准值、在递归深度过深时转为堆排序。JDK 的DualPivotQuicksort在数组较大时会采样数据来评估有序程度并选择合适的策略。第二个隐患是稳定性标准快排是典型的不稳定排序。所以在 Java 里对int[]这类基本类型数组默认用快排没关系但对对象数组如果直接调用Arrays.sort底层会自动切换成归并排序来保证稳定性。2.5 归并排序稳定性的代表多级排序的基石归并排序的思路也很明了把数组从中间分成左右两半分别排序再合并两个有序数组。它需要O(n)的额外空间来存放合并结果但换来的是O(n log n)的最坏时间复杂度以及稳定性。public static void mergeSort(int[] arr, int left, int right) { if (left right) { return; } int mid (left right) 1; mergeSort(arr, left, mid); mergeSort(arr, mid 1, right); merge(arr, left, mid, right); } private static void merge(int[] arr, int left, int mid, int right) { int[] temp new int[right - left 1]; int i left; int j mid 1; int 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) 1是一个值得留意的细节。很多人写成(left right) / 2当left right很大时可能发生整数溢出变成负数 1是无符号右移一位能避免这个问题。虽然在普通业务场景很难遇到那么大的数组但这个习惯养成了面试时会加分。归并排序在 Java 中的位置非常特殊JDK 对对象数组排序默认用的就是TimSort而TimSort本身是归并排序的改良版。另外我在处理多级排序需求时也喜欢用归并排序的思想先把数据按次要关键字分组排序再按主要关键字做稳定归并。这样可以保证最终顺序中主要关键字相同的记录内部依然保持次要关键字的顺序。2.6 堆排序原地排序和 TopK 问题的利器堆排序基于二叉堆结构思路分两步先用siftDown操作构建最大堆然后反复把堆顶元素和堆尾元素交换再调整堆。它最大的优势是空间复杂度O(1)不需要额外数组排序过程完全原地完成而且最坏时间复杂度也是O(n log n)不像快排那样存在退化风险。public static void heapSort(int[] arr) { if (arr null || arr.length 2) { return; } int n arr.length; // 从最后一个非叶子节点开始构建最大堆 for (int i n / 2 - 1; i 0; i--) { siftDown(arr, i, n); } // 逐个把堆顶最大值交换到末尾 for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; siftDown(arr, 0, i); } } private static void siftDown(int[] arr, int i, int n) { int parent i; int child 2 * parent 1; while (child n) { if (child 1 n arr[child 1] arr[child]) { child; } if (arr[child] arr[parent]) { int tmp arr[parent]; arr[parent] arr[child]; arr[child] tmp; parent child; child 2 * parent 1; } else { break; } } }实际工程里很少用堆排序去排一个完整数组因为虽然时间和空间都理想但它的数据访问模式是跳跃式的对 CPU 缓存不友好常数因子比快排和归并都大。堆排序真正的舞台是海量数据 TopK 问题数据量大到无法全部载入内存时维护一个大小为 K 的最小堆遍历数据流每次遇到比堆顶大的元素就替换并调整堆最终堆里留下的就是最大的 K 个元素。这个场景在搜索推荐、日志分析、排行榜系统里非常常见后面的实战部分我会给出一个完整的代码示例。2.7 算法对比速查表下面这个表格是我在实际准备面试和写技术方案时常用的总结整理成一目了然的形式算法平均时间复杂度最坏时间复杂度空间复杂度稳定性推荐场景冒泡排序O(n^2)O(n^2)O(1)稳定教学演示选择排序O(n^2)O(n^2)O(1)不稳定教学演示插入排序O(n^2)O(n^2)O(1)稳定小规模或基本有序数据希尔排序O(n log^2 n)O(n^2)O(1)不稳定中等规模、空间受限快速排序O(n log n)O(n^2)O(log n)不稳定基本类型大数组排序归并排序O(n log n)O(n log n)O(n)稳定对象排序、多级排序堆排序O(n log n)O(n log n)O(1)不稳定TopK、空间受限表格里的稳定性一列面试时几乎必问。能清晰说出插入和归并稳定选择、快排、堆排序不稳定是基本功更进一步要能解释为什么稳定排序的判断标准本质上是看相等元素的相对顺序是否在排序过程中可能被交换或跨越。3. JDK 内置排序的原理与高效使用3.1 Arrays.sort 的底层策略双基准快排与 TimSort很多 Java 开发者天天用Arrays.sort却不知道它对不同类型数组采用了完全不同的排序策略。我在排查一个线上性能问题时仔细翻过 JDK 源码Arrays.sort对基本类型数组和对象数组的处理有两条路径。对int[]、long[]、double[]这类基本类型数组JDK 使用的是DualPivotQuicksort双基准快速排序。这个算法选取两个基准值把数组分成三部分比单基准快排减少了递归深度和比较次数。源码里还有一个非常重要的细节当数组长度小于某个阈值例如 47时直接使用插入排序当数组长度较大时会先检查数据的有序性——如果检测到数组已经基本有序会使用一种更适应有序数据的排序策略。这就是为什么你明明调用同一个Arrays.sort对不同形态的数据实际运行的算法是不同的。对对象数组JDK 使用的是TimSort简化版叫ComparableTimSort。TimSort是一种结合了插入排序和归并排序的混合算法它在数据局部有序时能发挥出接近O(n)的时间复杂度。核心做法是扫描数组找出天然有序的run分段然后用归并排序把各个 run 合并。这个算法的最大优势是稳定保证相同元素的相对顺序不变。所以你知道了这个区别就能理解为什么对基本类型排序比对象排序快基本类型不需要额外空间做归并合并也不需要维持稳定性。面试里常问的一个隐性考点就是为什么 Java 的Arrays.sort对int[]和Integer[]用的是不同算法 答案的要点就是稳定性和性能的权衡。int[]是值类型不需要稳定Integer[]是对象相等对象的前后顺序可能承载业务含义所以必须稳定。3.2 Comparator 与 Comparable自定义排序的正确姿势Arrays.sort能够默认排序依赖的是元素自身实现Comparable接口。比如String、Integer都实现了Comparable所以可以直接排序。但当你要按对象的某个属性排序或者按多个字段组合排序时就要显式提供Comparator。Comparable和Comparator的区别我经常用这个类比解释Comparable是对象自己知道自己怎么排序相当于一个人自己清楚自己的优先级规则Comparator是外部给出一套排序规则相当于站在外部的人决定两种对象谁该排在前面。前者写在实体类里只能有一种排序逻辑后者可以写多个互不影响更灵活。看一下实际用法一个订单类按金额倒序、再按创建时间正序排序ListOrder orders orderService.list(); orders.sort(Comparator.comparing(Order::getAmount) .reversed() .thenComparing(Order::getCreateTime));这里有个隐藏的坑reversed()只会反转前一个比较器后续的thenComparing部分还是按升序。如果你想全部倒序需要对每个字段单独写比较器再组合。我踩过这个坑当时想按金额和创建时间都倒序直接这样写了结果创建时间变成了升序跟产品期望正好相反。正确的写法是orders.sort(Comparator.comparing(Order::getAmount) .thenComparing(Order::getCreateTime) .reversed());注意reversed()放在链式调用的最外层反转的是整个组合后的比较器。另外提醒一点Comparator.comparing的 JDK 版本差异要注意Comparator链式 API 在 Java 8 之后才全面可用老项目升级时可能会有编译问题。3.3 parallelSort 与 Stream 排序的经验之谈JDK 8 引入的Arrays.parallelSort是一个容易被忽视但很实用的方法。当数组足够大默认阈值大约是 8192 个元素时它会把数组切分成几个子数组用ForkJoin框架并行排序再合并结果。如果在多核机器上处理百万级数组性能提升很明显。但我要提醒一句并行排序不一定总是更快。它要付出线程池调度、任务拆分和结果合并的代价数据量小时反而可能比普通排序更慢。我在一个数据分析项目里对 500 万条整数排序parallelSort确实比普通sort快了不少大概有 1.5 到 2 倍的速度提升。但对几千条数据的列表两者差距几乎可以忽略甚至parallelSort还可能因为线程开销而略慢。所以我的建议是数据量至少上百万再考虑用parallelSort业务代码里还是老老实实用普通sort就好。Java 8 的Stream.sorted()也很常用它底层依赖对象数组的Arrays.sort所以对并行的parallelStream().sorted()尤其要注意并行流的sorted()会把所有元素收集到数组里排序完再重新组装成流所以内存占用比普通流更大。在写大列表排序时如果内存敏感我建议用传统方式先拿到列表再调用list.sort(comparator)而不是在流中间做排序。3.4 字符串排序与自然排序的细节热搜词里特别提到了字符串排序和字母数字组合的排序这个在工程里出现频率其实很高。比如文件资源管理器里A1.jpg,A2.jpg, ...,A10.jpg如果按字典序排A10 会排在 A2 前面这是字符串逐字符比较的结果。很多人第一次接触发现排错了其实不是代码错了而是字典序和自然序的差异。Java 的String.compareTo按char的 Unicode 编码值逐个比较字符。1的编码是 492是 50所以A10与A2比较时第一个字符都是A然后比较第二个字符1小于2于是A10排在前面。如果这不是你想要的顺序就需要自定义一个自然排序比较器。我在一个资产管理项目里处理楼栋-楼层-房间号排序时写过一个简易版核心逻辑是拆分字母段和数字段数字段按数值比较public class NaturalOrderComparator implements ComparatorString { Override public int compare(String o1, String o2) { if (o1 null || o2 null) { return o1 null ? (o2 null ? 0 : -1) : 1; } int i 0; int j 0; while (i o1.length() j o2.length()) { char c1 o1.charAt(i); char c2 o2.charAt(j); if (Character.isDigit(c1) Character.isDigit(c2)) { int numStart1 i; while (i o1.length() Character.isDigit(o1.charAt(i))) { i; } int numStart2 j; while (j o2.length() Character.isDigit(o2.charAt(j))) { j; } int len1 i - numStart1; int len2 j - numStart2; // 去掉前导零后先比较长度再比较字典序避免溢出 String s1 stripLeadingZeros(o1.substring(numStart1, i)); String s2 stripLeadingZeros(o2.substring(numStart2, j)); if (s1.length() ! s2.length()) { return s1.length() - s2.length(); } int cmp s1.compareTo(s2); if (cmp ! 0) { return cmp; } // 数字相同但位数不同时带更多前导零的排前面 if (len1 ! len2) { return len1 - len2; } } else { char lower1 Character.toLowerCase(c1); char lower2 Character.toLowerCase(c2); if (lower1 ! lower2) { return lower1 - lower2; } i; j; } } return o1.length() - o2.length(); } private String stripLeadingZeros(String s) { int firstNonZero 0; while (firstNonZero s.length() - 1 s.charAt(firstNonZero) 0) { firstNonZero; } return s.substring(firstNonZero); } }为什么数字部分要先用去除前导零后的字符串比较长度因为转成int比较在位数较多时可能溢出比如 999999999999 已经超过int范围了。用字符串先比长度再比字典序是一种安全又不至于过于复杂的做法。当然如果你的数字范围确定在int或long内直接解析成数值比较更简单这个比较器是根据我的实际场景折中取舍后的方案。如果项目里对自然排序要求很高可以考虑引入现成的库比如commons-lang3里的ComparableComparator配合自定义规则或者干脆在后端计算好排序字段再让数据库排序不要把复杂逻辑全压在一个比较器上。不过引入外部库之前先想清楚你的数字格式是否规则不规则时外部库也一样需要调节器。3.5 中文排序的处理经验字符串排序里还有一个很多人忽略的场景中文排序。Java 默认的String.compareTo是按 Unicode 编码排序的汉字的 Unicode 编码区间和拼音顺序无关所以直接对中文列表排序得到的结果既不是按拼音也不是按部首而是一个看起来随机的顺序因为它实际是按汉字在 Unicode 表中的码位排列的。如果业务要求按拼音排序需要自己收集可靠的拼音映射库。我参与过一个通讯录项目当时的方案是先为联系人记录拼音首字母作为独立字段存储在数据库里排序时直接ORDER BY pinyin_field。这个方案的好处是排序开销集中在写入阶段读取排序时性能好而且不需要在每次查询时都做拼音转换。缺点是数据更新时要重新生成拼音字段。如果不想存字段也可以在 Java 内存里用成熟的拼音库将汉字转成拼音后再比较但这样会消耗额外CPU并且对大数据量排序不友好。总而言之建议在字段设计阶段就预留拼音列这比一切口胡的运行时转换方案都可靠得多。4. 工程实战排序在项目中的落地4.1 点击表头排序的接口设计热搜词里点击表头排序、