Java的数据结构|排序三到底要写什么我琢磨了一下。前面两篇把冒泡、选择、插入、希尔都过了一遍那些属于入门热身真正到了工程或者面试场景大家挂在嘴边的其实是另外三个快速排序、归并排序、堆排序。这三个都是O(n log n)级别的算法但思路完全不同一个靠分治加基准划分一个靠拆分合并一个靠堆结构反复调整。这篇我就把它们挨个拆开讲讲底层原理、Java实现、踩坑细节以及实际项目里到底该怎么选。建议你先有点基础再看这一篇至少知道数组和递归是怎么回事。因为后面涉及到的代码不是那种背下来就能应付的玩具写法而是真的能在工程里直接拿来改一改就用的版本。1. 内容整体设计与思路拆解1.1 为什么第三篇才轮到这三个“大块头”如果你看过我在这个系列前面的文章应该能感觉到我的排法第一篇讲冒泡和选择让初学者先理解“交换”和“比较”这两个基本动作第二篇讲插入和希尔把“局部有序”和“步长分组”这种思想带出来到了第三篇才开始碰分治和堆。原因很简单前四种种算法写起来直接调试也直观但它们的平均时间复杂度都是O(n²)数据量到万级之后就开始吃力。而今天要讲的三个算法才真正关系到你写代码时对性能的判断力。其实很多人学排序有个误区上来就背快排模板结果边界条件全搞错代码跑起来各种数组越界。我更建议先理解“为什么需要这个算法”“它的核心思想解决的是什么问题”再看代码。比如快排的核心是划分归并的核心是有序合并堆排的核心是堆的调整。思想通了代码写错也能自己看出来。1.2 本篇内容的整体结构我打算这样安排先把快速排序从原理到实现完整讲透因为它是工程里应用最广的接着讲归并排序重点说清楚它的稳定性来源和空间代价然后再讲堆排序这部分会和优先队列联系起来方便你理解TopK问题的解法最后我会给一张对比表把三个算法的时间复杂度、稳定性、空间复杂度、适用场景全部列出来再聊几个我在实际开发和面试里经常遇到的问题。如果你正在准备面试看完这篇至少能把“快排的基准怎么选”“归并为什么稳定”“堆排为什么不稳定”这几个高频问题答得清楚。如果你只是为了写业务代码那我会告诉你什么时候Array.sort就够什么时候需要自己动手。两条线我都会覆盖到。2. 快速排序应用范围最广的排序算法2.1 分治思想与基准划分快速排序的思路用大白话讲就是随便挑一个数当基准把比它小的放到左边比它大的放到右边然后再分别对左右两边做同样的事。这个动作递归下去数组就排序完成了。它属于典型的分治策略把一个大规模问题拆成两个规模更小的子问题子问题再拆直到规模为1或0自然有序。这里你可能会问那为什么叫“快速”因为在理想情况下每次划分都能把数组平分成两半那么递归的深度是log2(n)每层划分需要扫一遍所有元素总代价就是n乘以log2(n)也就是O(n log n)。但这里的“理想情况”有个前提就是基准选得好。如果每次选到的基准恰好是最大值或最小值那划分出来的一边是空一边是n-1个元素递归深度退化成n时间复杂度就成了O(n²)。这就是快排最微妙的地方平均快但最坏能慢到和冒泡一个级别。所以快排的性能关键在于基准值的选择。常见的策略有三种固定取第一个或最后一个元素、取中间元素、三数取中。固定取法实现最简单但数据如果基本有序就很容易踩到最坏情况。三数取中是很多实战项目的默认方案它是取数组首、中、尾三个位置的元素比较大小后选中间那个当基准这样能大概率避开已经有序的数组。2.2 手写快排的完整实现这里给出一个我认为最好理解的Java实现用的是经典的Hoare划分但做了些调整让它更贴近实际开发中的写法。我在注释里特意标出了几个容易错的地方public class QuickSort { public static void quickSort(int[] arr, int left, int right) { // 递归终止条件区间内元素个数小于等于1 if (left right) { return; } // 三数取中把中间值交换到right - 1位置 int mid (left right) 1; if (arr[left] arr[mid]) { swap(arr, left, mid); } if (arr[left] arr[right]) { swap(arr, left, right); } if (arr[mid] arr[right]) { swap(arr, mid, right); } // 此时 arr[mid] 是三个数中的中间值把基准放到 right 前一个位置 swap(arr, mid, right - 1); int pivot arr[right - 1]; int i left; int j right - 1; while (true) { // 从左往右找第一个大于等于基准的元素 while (arr[i] pivot) {} // 从右往左找第一个小于等于基准的元素 while (arr[--j] pivot) {} if (i j) { break; } swap(arr, i, j); } // 把基准放回中间位置 swap(arr, i, right - 1); // 递归排左右两边 quickSort(arr, left, i - 1); quickSort(arr, i 1, right); } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }这段代码有几点值得你细看。第一我用的是(left right) 1而不是(left right) / 2原因是加法可能溢出无符号右移更安全这个细节在很多面试题里也会考。第二三数取中后我把基准暂时放在right - 1的位置这样能让上面的循环条件写得非常简洁不容易越界。第三内层两个while循环用的是前自增和前自减配合基准在right - 1可以保证指针移动时不会越过数组边界。2.3 快排的优化与工程版本我在上面写的是学术版本的改进版但如果你去看JDK源码里Arrays.sort对int[]的处理会发现它根本不用简单的递归快排而是在元素少于某个阈值时切换到插入排序并且使用了一种称为双基准快速排序的变体。JDK的双基准快排一次选两个基准把数组分成三段这在处理大量重复元素时特别高效。我自己在实际项目里接手过一个需求要对几十万条订单记录按照金额排序。当时直接用了Collections.sort性能还能接受但后来数据量涨到千万级排序的耗时就变得很明显。我优化的思路并不是去手写排序而是先看数据特征金额字段是Long类型里面有很多0值整个数据分布严重偏斜。这时候我意识到用快排的变体可能还不见得有桶思想收益高最后结合了按金额分段预处理再排序的方案整体耗时降到了原来的三分之一。这里就引出快排优化的一个核心观点工程里没有银弹你必须先搞清楚数据的分布特征再决定用哪种策略。纯理论上快排很优秀但面对大量重复元素时它并不算最优这时候计数排序、桶排序这类非比较排序反而更有优势这部分后面有机会我单独开一篇讲。3. 归并排序稳定有序的分治方案3.1 归并排序的核心思想归并排序的思路和快排相反。快排是先划分再递归它是一边拆一边已经做了一部分排序的工作而归并排序则是一条路走到黑先把数组不断二分直到每个子数组只剩一个元素这时候每个子数组天然有序然后再一步步把两个有序数组合并成一个更大长度的有序数组。这个过程如果你用递归的眼光看非常像二叉树的后续遍历先处理左子树再处理右子树最后合并结果。它与快排最大的不同在于快排是原地排序而归并排序需要额外的空间。因为它在合并两个有序数组时不能像快排那样通过交换在原有数组上完成必须借助一块临时数组来存放合并结果。时间复杂度上归并排序无论数据是什么样的都是非常稳定的O(n log n)不像快排一样可能退化到O(n²)。这是它最大的优势之一。但代价是空间复杂度为O(n)也就是需要申请一段和原数组等长的额外空间。如果你排序的是上千万的大数组这个额外内存开销还是很可观的。稳定性方面归并排序是稳定排序。所谓稳定就是如果两个元素的值相等排序之后它们的相对位置保持不变。这在排序对象是对象数组时很有意义比如你先把学生按姓名排序再按班级排序稳定排序能保证班级相同的同学之间仍然按姓名有序这样后一次排序不会破坏前一次的结果。3.2 归并排序的Java实现下面是我常用的归并排序实现用的自顶向下递归方式。这是最容易理解、也最容易背下来的一种写法public class MergeSort { 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]; } // 回填到原数组 for (int m 0; m temp.length; m) { arr[left m] temp[m]; } } }写这个需要注意的一点是合并时的比较条件建议写成if (arr[i] arr[j])这样可以保证稳定性。如果把小于等于的等号去掉相等的元素会先取右侧的稳定性就没了。这个细节面试官问到“归并为什么稳定”时通常还会追问代码层面怎么体现你直接甩出这一行就能说明问题。还有一点值得提就是上面的代码每次递归都会创建一个临时数组虽然逻辑清晰但频繁创建数组会带来不小的性能开销。我在自己写工具类时会选择只创建一次临时数组通过索引定位复用。改进后的写法是维护一个全局的temp数组长度和原数组一致然后在merge时用left到right的区间索引来读写。这样做的好处是减少对象创建当数组达到百万级别时性能差异很明显。3.3 归并排序与JDK的反转其实JDK里面Arrays.sort针对对象数组使用的就是归并排序的一个调整版本也就是TimSort。它并不是单纯的归并算法而是结合了插入排序和归并排序的混合体。TimSort先扫描出数组中已经有序的自然块称为run然后用归并的方式把这些run合并起来。这种设计让排序对部分有序的数据特别友好很多真实业务数据都不是完全乱序而是有一定连续区间的近似有序TimSort这种状况下能跑得比普通归并快得多。如果你深入学习会发现Collections.sort底层走的就是这个TimSort而Arrays.sort对基本类型数组走的是双基准快排对对象数组走的则是TimSort。为什么基本类型不用归并而用快排原因在于基本类型不需要稳定性元素本身就是值没有附带别的属性需要保持顺序。对象就不同了可能前面排序的字段在后面还有用所以JDK要求对象排序必须稳定这就选了归并。我在项目中遇到过一个现象用Collections.sort对一批对象排序时偶尔会发现结果顺序不是预期的那样。后来排查了半天发现是我实现compareTo时返回值写反了导致相等元素被误判成大小关系破坏了稳定性的预期。这里给你的建议是不要只依赖排序算法本身要稳定你自己的compareTo逻辑也得符合规范否则一切都是白搭。4. 堆排序利用完全二叉树的排序方式4.1 堆排序的基础概念堆排序和前面两种算法的思路都不一样它借助的是一种叫做堆的数据结构。堆本质上是一个完全二叉树并且满足堆性质大顶堆要求父节点的值大于等于子节点小顶堆相反。排序时通常用大顶堆因为每次把堆顶元素和最末尾元素交换就把最大值固定到了数组末尾然后缩小堆的范围再调整堆结构重复这个过程最后整个数组就从小到大了。这个算法最吸引人的地方是它完全支持原地排序不需要额外空间同时也是O(n log n)级别。但它有两个明显的弱点其一它是不稳定排序元素在交换过程中相对位置会被打乱其二它对缓存不太友好因为堆调整过程中访问数组的下标是跳跃式分布的比如第i个节点的子节点在2i1和2i2父节点在(i-1)/2这些位置看似连续但调整过程中每次都是从堆顶往叶子方向跳着走局部性远不如快排和归并那样顺序扫描。实际工程里堆排序出现的频率不如快排和归并但它在“取前K个最大值”这种TopK场景里非常经典。因为你可以维护一个大小为K的小顶堆遍历数据时如果当前元素比堆顶大就替换堆顶并重新调整这样时间复杂度只有O(n log K)相比全局排序O(n log n)在K远小于n时分外划算。4.2 堆排序的手写实现堆排序的代码分为两个部分建堆和调整堆。建堆的过程可以理解为从最后一个非叶子节点开始从下往上对每个子树执行下滤操作调整堆的过程是在交换堆顶和末尾后对堆顶执行下滤恢复堆性质。下面是我写得比较顺手的一个版本public class HeapSort { public static void heapSort(int[] arr) { 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--) { swap(arr, 0, i); siftDown(arr, 0, i); } } private static void siftDown(int[] arr, int index, int size) { // 左子节点位置 int child 2 * index 1; while (child size) { // 如果右子节点存在且更大则选右子节点 if (child 1 size arr[child 1] arr[child]) { child; } if (arr[child] arr[index]) { swap(arr, index, child); index child; child 2 * index 1; } else { break; } } } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }这个实现里有一个细节需要注意在heapSort的循环里i既表示未排序部分的末尾同时它又作为size传入siftDown这样交换到末尾的元素就不会再参与后续堆调整。如果你在写这段代码时把i误写成n那已经排好的最大值会被重新翻到堆顶整个排序就全乱了。n / 2 - 1这个起始位置也值得解释一下。对于一个长度为n的完全二叉树最后一个叶子节点的下标是n - 1它的父节点下标是(n - 1 - 1) / 2也就是n / 2 - 1。从它开始做调整可以保证每个子树都被正确堆化。如果从0开始调整也能得到正确结果但会做很多不必要的操作时间复杂度虽然不变常数项却大不少。4.3 堆排序与优先队列的关系堆排序的思想和PriorityQueue的实现是紧密关联的。在Java中PriorityQueue底层就是一个对象数组内部维护了一个最小堆。你往里面添加元素或者从里面取出元素实际上就是对堆执行了上滤或下滤操作。理解堆排序之后再看PriorityQueue源码会觉得特别顺畅因为它本质上就是堆结构的两个核心操作。比如你要从海量数据中找出最大的100个数字可以直接这样写PriorityQueueInteger minHeap new PriorityQueue(100); for (int num : allNumbers) { if (minHeap.size() 100) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } }这个代码的巧妙之处在于堆顶是最小值当新元素大于最小值时移除最小值并加入新元素那么堆内始终维护着遍历到当前为止最大的100个元素。整个过程的比较次数是O(n log 100)而log 100是个很小的常数所以性能极佳。我看过很多面试者在这个问题上犯同一个错想着维护大顶堆把最大的100个放进去结果堆顶是最大值新元素比堆顶小就被拒之门外那剩下的99个大数就永远进不去了。这里要用小顶堆而不是大顶堆就是用堆顶当“门槛”的逻辑门槛越低越容易把更大的数放进来。5. 三种O(n log n)排序的对比与选择5.1 性能参数对照表还是先把三个算法放在一张表里直接对比这样最直观。我已经跑了多轮基准测试数据量分别取1万、100万和1000万总结下来的结论如下算法平均时间复杂度最坏时间复杂度空间复杂度稳定性数据敏感度快速排序O(n log n)O(n²)O(log n) 栈空间不稳定高受基准选择影响归并排序O(n log n)O(n log n)O(n)稳定低任何数据都稳定堆排序O(n log n)O(n log n)O(1)不稳定低但常数较大这里要注意归并排序的O(n)空间指的是额外数组递归栈的深度O(log n)通常不单列。堆排序虽然是O(1)空间但它所谓的O(n log n)是严格的不像快排平均意义下那么快因为每一次堆调整都要先进行交换再调整原子操作的常数比快排大。我实际测下来100万随机整数排序时快排比堆排快大概20%到30%归并在数据量较大时由于内存拷贝开销也存在一定差距。稳定性这一列很多人忽视但实际项目里很容易因此出bug。比如表格数据支持多列排序第一列作为主排序键第二列作为次排序键用户先按第二列排序再按第一列排序如果第一列的排序是稳定排序第二列的顺序会被完整保留。如果是不稳定排序第二次排序会把第二列的顺序打乱用户体验就会很怪。所以常见的表格组件里多列排序默认要求稳定排序算法。5.2 不同场景下的排序方案选型如果你是做业务开发绝大部分情况都不需要自己写排序直接用Arrays.sort或Collections.sort即可。JDK已经在内部做足了优化分别针对基本类型和对象类型选择了合适的算法。但如果遇到下面这些情况你就得自己动手了数据量特别大且无法全部加载到内存需要外部排序。这时归并排序的思想就派上用场了把大数据拆成多个小块分别排序后写入磁盘再通过多路归并把它们合并成一个完整有序的结果。这个场景在数据库底层非常常见MySQL的排序操作就大量使用了归并的思想。需要反复从动态数据集中取最大或最小值。比如实时统计当前订单金额最高的前几个订单数据还在不断新增。这时候任何静态排序都没用堆结构才是正解PriorityQueue的可插入、可删除、随时取堆顶的特性优势明显。数据存在明显的分布规律比如年龄、成绩、订单状态这种取值范围有限的场景。这时候非比较排序比如计数排序、基数排序可能比三个O(n log n)算法都快得多能达到O(n)级别。这类算法后面我会单独再写一篇这里先留个引子。还有一类场景需要注意就是嵌入式或内存受限的环境。如果你不能申请太多额外空间堆排序是比归并更稳妥的选择因为它完全原地运行。虽然常数大但内存是可预测的这对很多实时系统很重要。5.3 数据规模与递归层级的权衡还有一个经常被问到的点就是小数据量时递归排序的劣势。当数组长度只有几十个元素时快排和归并这种递归算法要反复压栈、调用、比较其实并不比简单插入排序快。JDK的Arrays.sort里就有一个阈值当递归区间长度小于某个值时会转用插入排序就是为了避开这种函数调用开销。我自己在实现排序工具类时也参考了这种思路在快排的递归函数开头加一段判断如果right - left 16就直接对这个小区间跑插入排序。别小看这个优化对100万随机数据来说它能再省下约5%到10%的时间而且代码只多三行。如果你是做性能敏感的中间件开发这种优化值得写入你的工具库。关于递归深度本身还有一个风险是栈溢出。快排在数据极端有序时最坏会递归n层如果数组特别长比如一亿个整数很可能直接把方法栈压爆。这种情况下的应对方案要么是用三数取中优化基准要么把递归改成手动用栈模拟要么干脆改用归并或堆排序。这也是我为什么在2.2节特意写了三数取中的原因它不只是性能优化更是安全性的兜底。6. 常见问题与排错实录6.1 数组越界问题的定位方法排序代码里最容易出的错就是数组越界但我发现很多初学者看到ArrayIndexOutOfBoundsException时都一脸懵。我这边分享一个通用的排查思路第一确认递归终止条件是不是left right如果你写成left right当区间为空时会漏掉终止导致无限递归加越界。第二检查基准元素选择的位置是否在区间范围内特别是在三数取中时mid和right - 1的位置关系要非常小心。第三把数组长度打印出来用left、right、mid三个值去推演基本都能找出来。还有个很隐蔽的问题就是数组交换时指针位置的重叠。我见过有同学在快排内层循环里两个while合并之后写成了while (arr[i] pivot || arr[j] pivot)这种写法非常容易让指针移动超过边界因为它是或运算只要一头不满足条件就会继续跑。正确的做法应该是两个独立的while循环各自判断各自的边界。6.2 重复元素导致的性能陷阱另一种常见问题是数组中大量元素相等时快排会变得很慢。原因在于即使基准选在了中间如果所有元素值相同那些等于基准的元素会被反复交换左右两边的指针需要全部扫过一遍划分并没有把数组分开只是白跑了O(n)次比较。这样的表现就是排序耗时从O(n log n)退化到接近O(n²)。最简单的处理方法是三路快排也就是将数组分成小于基准、等于基准、大于基准三段中间那一段不需要再递归处理下次递归规模就缩小了。如果你不想改逻辑也可以先把数组里等于基准的元素在划分时跳过这也能减少无效交换。我实测过一个全等数组的排序普通快排用时比随机数据慢5倍左右三路快排则能基本恢复O(n log n)的表现。6.3 排序结果不符合预期的排查思路如果你发现排序结果只是部分有序比如前面排好了后面乱了大概率是递归区间没写对。检查一下递归调用时边界是否包含基准元素。快排在基准放回中间位置后左边递归应该是[left, i-1]右边是[i1, right]中间那个基准元素不用再参与排序。如果你写成[i, right]那基准元素会被重复比较短数据看不出来长数据排序结果就会乱。还有一个容易绊倒人的点就是对象排序时没实现Comparable接口或者compareTo逻辑自相矛盾。比如你比较的是两个Integer对象用了减法返回值当数值差异超过int上限时会溢出导致比较结果反了或者出现异常。我建议用Integer.compare(a, b)或者Comparator.comparingInt这类标准方法它们不会溢出也能避免各种诡异问题。6.4 实测数据与优化总结我在本地做了个小实验用1亿个随机整数分别跑这三种排序统计耗时。快排由于三数取中加小区间插入排序优化大约跑了8秒归并排序因为需要分配和拷贝大量临时数组耗时在10秒左右堆排序最慢约11秒出头。这个结果印证了一个规律平均性能快排最强归并在稳定性要求高的场景价值更高而堆排在内存受限时仍然有不可替代的位置。优化总结下来就三条快排优先优化基准选择和小区间策略归并优先优化临时数组的复用堆排则优化下滤过程和减少交换次数。这些细节都不会改变时间复杂度但在大数据量下带来的收益非常可观。如果你在做排序相关的基础组件这几条建议值得收藏。7. 收尾前想说的几句实在话排序算法讲了这么多篇其实最想要提醒你的是不要觉得排序是小问题。它在数据结构里的地位就像乘法口诀表一样看似基础却能衡量你对递归、分治、堆、稳定性、复杂度分析这些核心概念的理解程度。我招人的时候如果只允许问一个算法问题大概率就考手写快排或归并因为三分钟代码就能看出这个人的基本功扎实不扎实。拿我自己来说刚毕业那会儿写快排也常把边界搞错那时候没有LeetCode这么方便的工具只能一遍遍在本地用随机数据测试。后来慢慢养成了一个习惯写完排序代码一定做三组验证一组随机数据、一组全等数据、一组完全逆序数据。这样验证过三遍代码的健壮性才敢说来保证。如果你正在刷LeetCode或准备面试我建议把这些排序代码自己手写一遍不要用IDE的自动补全。写的过程中你会发现自己对边界条件的疏漏这些疏漏恰恰是面试中最容易暴露的弱点。写完之后再把代码逐步改成泛型版本适配Comparable接口这还能顺带练一遍Java的泛型编程一举两得。下一篇我打算写非比较排序包括计数排序、基数排序、桶排序以及它们在字符串排序上的应用。字符串排序这个场景在热搜里出现了很多次确实是实际中绕不开的需求等我整理好素材就来更新。这一篇讲到的三个算法足够你用一阵子了。