排序算法这块内容我前前后后讲过不下十遍每次讲到后半段——也就是归并、快排、堆排、计数、桶排、基数排这几个——总有人问我这些算法到底怎么选为什么面试老爱问快排和归并的区别堆排明明时间复杂度也是O(nlogn)为什么实际项目里用得少这些问题光看代码是看不出来的得把每个算法的“脾气”摸透。这篇就接着上篇的内容把剩下这六个经典排序算法从原理到Java实现再到实际选型完整地捋一遍。不管你是正在准备面试还是想在实际项目里选一个靠谱的排序方案又或者只是想把算法基础打扎实下面这些内容应该都能帮到你。1. 归并排序分治思想最标准的教科书案例归并排序是我个人认为最能体现“分治”思想的排序算法。它的逻辑非常干净把数组一分为二左右两边分别排好序然后把两个有序数组合并成一个更大的有序数组。递归下去直到子数组只有一个元素——单个元素天然有序这就是递归的终止条件。1.1 分治的拆解逻辑与递归树理解归并排序关键是理解它的递归树。假设数组有8个元素第一层拆成两个4元素子数组第二层拆成四个2元素子数组第三层拆成八个1元素子数组。然后从底层往上合并1合1变22合2变44合4变8。整个过程是一棵满二叉树树的高度是log₂n每一层的合并操作总共要遍历n个元素所以总时间复杂度是O(nlogn)。这个O(nlogn)是稳定的——不管输入数据长什么样归并排序都是这个复杂度。这一点和快速排序不同快排在最坏情况下会退化到O(n²)。归并排序的代价是需要额外的O(n)空间来存放合并时的临时数组这是它最大的“缺点”也是很多内存敏感场景下不选它的原因。1.2 Java实现中的临时数组复用技巧先看标准实现public class MergeSort { public static void sort(int[] arr) { if (arr null || arr.length 2) return; int[] temp new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); } private static void mergeSort(int[] arr, int left, int right, int[] temp) { if (left right) return; int mid left (right - left) / 2; mergeSort(arr, left, mid, temp); mergeSort(arr, mid 1, right, temp); merge(arr, left, mid, right, temp); } private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i left, j mid 1, k left; 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, left, arr, left, right - left 1); } }这段代码里有一个容易被忽略的细节temp数组是在最外层创建一次然后作为参数传递下去的。很多初学者会在每次merge的时候新建一个数组那样会导致大量的对象创建和GC压力。实测下来复用同一个临时数组在百万级数据上性能差距能到30%以上。还有一个优化点在merge之前可以加一个判断——如果arr[mid] arr[mid1]说明左右两半已经整体有序了不需要再合并。这个优化对于部分有序的数据效果非常明显。注意归并排序的稳定性依赖于arr[i] arr[j]这个判断条件。如果写成相等元素的位置会被交换排序就不稳定了。1.3 归并排序在实际工程中的典型场景归并排序最常被提到的实际应用是Java的Arrays.sort()中对对象数组的排序。TimSort——Java 7引入的排序算法——本质上是归并排序和插入排序的混合体。它利用了归并排序稳定、O(nlogn)的特点同时通过插入排序处理小数组来减少递归开销。另一个典型场景是外部排序。当数据量大到内存装不下时可以把数据分成若干块每块在内存中排好序写回磁盘然后做多路归并。这个思路在数据库的排序操作和大数据处理中非常常见。归并排序天生适合这种“分块合并”的模式因为它的合并操作只需要顺序读取两个有序序列对磁盘I/O非常友好。2. 快速排序平均性能之王但有几个坑必须避开快速排序是面试中出现频率最高的排序算法没有之一。它的核心思想是选一个基准元素把数组分成两部分——左边都比基准小右边都比基准大——然后对左右两部分递归排序。快排的平均时间复杂度是O(nlogn)常数因子比归并排序小所以实际运行速度通常更快。但它的最坏情况是O(n²)而且不稳定。2.1 基准选择策略决定快排的生死快排的性能几乎完全取决于基准元素的选择。如果每次都能选到中位数递归树是平衡的复杂度是O(nlogn)。如果每次选到最大或最小值递归树退化成链表复杂度变成O(n²)。常见的基准选择策略有三种固定选第一个或最后一个元素最简单但对已经有序的数组会退化到O(n²)。这是最忌讳的写法。随机选择从数组中随机选一个元素作为基准和第一个元素交换。这样可以避免对特定输入退化但随机数生成本身有开销。三数取中取左端、中间、右端三个元素的中位数作为基准。这是工程中最常用的策略既避免了最坏情况又没有随机数的开销。我实测过这三种策略在百万级随机数据上的表现固定选第一个和随机选择差距不大但三数取中在部分有序数据上优势明显。对于完全随机的数据三者差异在5%以内。2.2 分区操作的两种写法与边界处理快排的分区操作有两种经典写法Lomuto分区和Hoare分区。Lomuto分区比较直观用最后一个元素做基准维护一个小于基准的边界private static int partitionLomuto(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; }Hoare分区用第一个元素做基准从两端向中间扫描private static int partitionHoare(int[] arr, int low, int high) { int pivot arr[low]; int i low - 1, j high 1; while (true) { do { i; } while (arr[i] pivot); do { j--; } while (arr[j] pivot); if (i j) return j; swap(arr, i, j); } }Hoare分区的交换次数比Lomuto少实际运行更快。但Hoare分区的边界条件更容易写错特别是递归调用时的范围。用Hoare分区时递归调用应该是quickSort(arr, low, j)和quickSort(arr, j 1, high)而不是j-1和j1。这个细节我见过太多人写错了。2.3 快排的工程优化小区间用插入排序标准快排在递归到很小的子数组时效率反而不如插入排序。因为递归调用有函数栈开销而插入排序在小数组上的常数因子极低。工程上的做法是设置一个阈值通常是7到16当子数组长度小于阈值时直接调用插入排序。private static final int INSERTION_THRESHOLD 10; private static void quickSort(int[] arr, int low, int high) { if (high - low 1 INSERTION_THRESHOLD) { insertionSort(arr, low, high); return; } int pivotIndex partitionHoare(arr, low, high); quickSort(arr, low, pivotIndex); quickSort(arr, pivotIndex 1, high); }这个优化在百万级数据上大概能提升10%到15%的性能。另外还有一个优化是“尾递归消除”——先递归处理较小的一半然后用循环处理较大的一半这样可以把递归深度控制在O(logn)以内避免栈溢出。注意快排是不稳定的排序算法。如果你需要稳定排序要么用归并要么在比较时加入原始索引作为第二关键字。3. 堆排序被低估的O(nlogn)原地排序堆排序在面试中的出现频率不如快排和归并但它的特点非常鲜明时间复杂度稳定在O(nlogn)空间复杂度O(1)是唯一一个同时满足这两个条件的排序算法。归并需要O(n)额外空间快排最坏情况会退化。所以当你既要求时间稳定又要求空间原地时堆排序是唯一的选择。3.1 从建堆到排序的完整流程拆解堆排序分两个阶段建堆和排序。建堆阶段从最后一个非叶子节点开始依次向前做“下沉”操作。最后一个非叶子节点的索引是n/2 - 1。下沉操作是把当前节点和它的较大子节点比较如果小于子节点就交换然后继续向下比较直到满足堆性质。排序阶段每次把堆顶元素最大值和堆的最后一个元素交换然后把堆的大小减一对新的堆顶做下沉操作。重复这个过程直到堆的大小为1。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 i, int size) { while (true) { int left 2 * i 1; int right 2 * i 2; int largest i; if (left size arr[left] arr[largest]) largest left; if (right size arr[right] arr[largest]) largest right; if (largest i) break; swap(arr, i, largest); i largest; } }建堆的时间复杂度是O(n)不是O(nlogn)。这个结论很多人第一次听到会觉得反直觉但推导一下就很清楚大部分节点都在底层下沉的深度很小把所有节点的下沉深度加起来是收敛的总和是O(n)。排序阶段要做n次下沉每次O(logn)所以总复杂度是O(nlogn)。3.2 为什么堆排序实际运行比快排慢虽然堆排序的时间复杂度稳定在O(nlogn)但实际运行速度通常比快排慢两到三倍。原因有两个第一堆排序的访存模式对CPU缓存不友好。快排的分区操作是顺序扫描数组缓存命中率高。堆排序的下沉操作是跳跃式访问——父节点索引i子节点索引2i1和2i2每次访问的位置跨度很大缓存命中率低。第二堆排序的交换次数多。每次下沉都可能触发多次交换而快排的分区操作交换次数相对较少。在现代CPU上缓存未命中的代价远高于简单的算术运算所以访存模式的影响非常大。这也是为什么Java的Arrays.sort()对基本类型用双轴快排而不是堆排序——虽然堆排序空间复杂度更优但实际性能差距太大。3.3 堆排序的适用场景与替代方案堆排序最适合的场景是“只需要前K个最大/最小元素”。维护一个大小为K的堆遍历所有元素时间复杂度是O(nlogK)空间复杂度是O(K)。这比全排序再取前K个要高效得多。Java中可以用PriorityQueue来实现这个需求// 找前K个最大的元素 public static int[] topK(int[] arr, int k) { PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : arr) { if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } int[] result new int[k]; for (int i k - 1; i 0; i--) { result[i] minHeap.poll(); } return result; }这个模式在实际项目中非常实用比如排行榜、热搜词统计、日志分析中的TopN查询等。4. 三种线性排序计数、桶排、基数排的适用边界计数排序、桶排序、基数排序这三个算法经常被放在一起讲因为它们都突破了比较排序O(nlogn)的下界。但这个突破是有代价的——它们都依赖于数据的特定性质不是通用的排序算法。4.1 计数排序用空间换时间的极致体现计数排序的思路非常直接统计每个元素出现的次数然后按照值的大小顺序输出。它要求输入数据是有限范围内的整数。public static void countingSort(int[] arr) { if (arr null || arr.length 2) return; int max arr[0], min arr[0]; for (int num : arr) { max Math.max(max, num); min Math.min(min, num); } int range max - min 1; int[] count new int[range]; for (int num : arr) { count[num - min]; } int index 0; for (int i 0; i range; i) { while (count[i]-- 0) { arr[index] i min; } } }计数排序的时间复杂度是O(nk)其中k是数据范围。当k远大于n时计数排序反而不如比较排序。比如对100个范围在0到1000000之间的数排序计数排序需要创建一个百万大小的数组空间浪费严重。计数排序的一个重要应用是作为基数排序的子过程。基数排序的每一轮都需要对某一位进行稳定排序计数排序正好满足这个需求。4.2 桶排序分桶策略决定性能上限桶排序的思路是把数据分到若干个桶里每个桶内部单独排序然后按顺序把桶里的元素串起来。桶排序的性能取决于数据分布的均匀程度——如果数据均匀分布每个桶里的元素数量差不多时间复杂度接近O(n)如果数据全部集中在少数几个桶里就退化成桶内排序的复杂度。public static void bucketSort(double[] arr) { int n arr.length; ListListDouble buckets new ArrayList(n); for (int i 0; i n; i) { buckets.add(new ArrayList()); } for (double num : arr) { int index (int) (num * n); if (index n) index n - 1; buckets.get(index).add(num); } int idx 0; for (ListDouble bucket : buckets) { Collections.sort(bucket); for (double num : bucket) { arr[idx] num; } } }桶排序的关键参数是桶的数量和分桶函数。桶的数量通常取n分桶函数要保证数据均匀分布。对于均匀分布的[0,1)区间数据num * n是一个自然的分桶函数。对于其他分布的数据需要根据实际情况设计分桶函数。注意桶排序的稳定性取决于桶内排序算法是否稳定。如果桶内用快排整体就不稳定如果用插入排序或归并整体就是稳定的。4.3 基数排序从低位到高位的稳定排序链基数排序的核心思想是“从低位到高位每一轮用稳定排序对当前位排序”。经过所有位的排序后整个数组就是有序的。基数排序的正确性依赖于每一轮排序必须是稳定的——如果某一位的排序不稳定前面已经排好的低位顺序就会被破坏。public static void radixSort(int[] arr) { int max Arrays.stream(arr).max().getAsInt(); for (int exp 1; max / exp 0; exp * 10) { countingSortByDigit(arr, exp); } } private static void countingSortByDigit(int[] arr, int exp) { int n arr.length; int[] output new int[n]; int[] count new int[10]; for (int num : arr) { count[(num / exp) % 10]; } for (int i 1; i 10; i) { count[i] count[i - 1]; } for (int i n - 1; i 0; i--) { int digit (arr[i] / exp) % 10; output[count[digit] - 1] arr[i]; count[digit]--; } System.arraycopy(output, 0, arr, 0, n); }基数排序的时间复杂度是O(d(nk))其中d是最大数的位数k是基数十进制是10。对于整数排序基数排序通常比比较排序快特别是当数据量大且位数不多时。基数排序的一个重要细节是从低位到高位排序时每一轮必须从后往前遍历原数组来填充output数组。这是为了保证稳定性——从后往前遍历时相同位的元素会保持原来的相对顺序。5. 十大排序算法的横向对比与选型决策把十大排序算法放在一起对比才能真正理解每个算法的定位。下面这张表是我自己整理的涵盖了时间复杂度、空间复杂度、稳定性、实际性能等关键维度。算法平均时间最坏时间空间稳定性实际性能特点冒泡排序O(n²)O(n²)O(1)稳定几乎不用教学用选择排序O(n²)O(n²)O(1)不稳定交换次数少但比较次数固定插入排序O(n²)O(n²)O(1)稳定小数组和近乎有序数据极快希尔排序O(n^1.3)O(n²)O(1)不稳定插入排序的改进版中等数据量可用归并排序O(nlogn)O(nlogn)O(n)稳定稳定O(nlogn)适合对象排序和外部排序快速排序O(nlogn)O(n²)O(logn)不稳定平均最快工程中需优化基准选择堆排序O(nlogn)O(nlogn)O(1)不稳定时间空间双优但缓存不友好计数排序O(nk)O(nk)O(k)稳定适合小范围整数k不能太大桶排序O(nk)O(n²)O(nk)取决于桶内排序适合均匀分布数据基数排序O(d(nk))O(d(nk))O(nk)稳定适合整数位数不多时极快5.1 按数据规模选小数组别用快排数据规模小于100时插入排序往往是最快的。因为插入排序的常数因子极小没有递归开销对CPU缓存友好。Java的Arrays.sort()在子数组长度小于47时会切换到插入排序。数据规模在100到10000之间时快排和归并的差距不大选哪个都可以。但如果要求稳定选归并如果要求原地选快排。数据规模超过10000时快排的优势开始显现。但要注意基准选择策略避免最坏情况。如果数据可能已经部分有序三数取中或随机化是必须的。5.2 按数据特征选整数、浮点数、对象各有最优解如果数据是范围有限的整数计数排序或基数排序是最快的。比如对年龄、成绩、等级这类数据排序计数排序的O(nk)远优于O(nlogn)。如果数据是浮点数且分布均匀桶排序是很好的选择。但如果分布不均匀桶排序可能退化。如果数据是对象且需要稳定排序归并排序是首选。Java的Arrays.sort(Object[])用的就是归并的变体。5.3 按约束条件选内存、稳定性、最坏情况内存受限时堆排序是唯一的选择——O(1)空间且O(nlogn)时间。但要做好性能比快排慢的心理准备。要求稳定排序时归并、插入、计数、基数、桶排桶内用稳定排序都可以。快排、堆排、选择排、希尔排都不稳定。要求最坏情况也是O(nlogn)时归并和堆排满足。快排不满足但通过随机化可以把最坏情况的概率降到极低。6. 面试中排序算法的高频追问与应对思路排序算法是面试的必考内容但面试官不会只让你写代码他们会追问各种细节。下面整理几个高频追问和应对思路。6.1 “快排的最坏情况是什么怎么避免”最坏情况是每次选的基准都是最大或最小值递归树退化成链表时间复杂度O(n²)。避免方法是随机化基准或三数取中。面试时还可以补充即使随机化理论上仍有极小的概率退化但工程上可以认为不会发生。6.2 “归并排序的空间复杂度能优化到O(1)吗”原地归并排序是存在的但实现非常复杂而且会把时间复杂度从O(nlogn)提高到O(nlogn²)或者常数因子极大。实际工程中不值得。面试时如果被问到可以说明原地归并的理论方案但指出实际不可取。6.3 “为什么Java的Arrays.sort()对基本类型用快排对对象用归并”因为快排不稳定但更快基本类型不需要稳定性相同值的元素无法区分。对象需要稳定性相同值的对象可能在其他字段上有区别所以用归并。这个设计体现了工程上“根据需求选算法”的原则。6.4 “堆排序的建堆为什么是O(n)”直观上每个节点下沉是O(logn)n个节点是O(nlogn)。但实际推导时大部分节点在底层下沉深度很小。把所有节点的下沉深度加起来第i层有2^i个节点每个节点下沉log(n)-i层总和是Σ(2^i * (log(n)-i))这个级数是收敛的结果是O(n)。面试时能说清楚这个推导基本就稳了。6.5 “计数排序能排负数吗”可以但需要先找出最小值把数组映射到非负范围。比如数组范围是[-100, 100]可以映射到[0, 200]。这个细节很多人会忽略面试时主动提出来是加分项。7. 我在实际项目中的排序选型经验做了这么多年开发真正需要手写排序算法的场景其实不多但每次遇到都需要仔细权衡。分享几个我踩过的坑和总结的经验。第一个经验不要过早优化。大多数业务场景下数据量根本不大直接用Arrays.sort()或Collections.sort()就够了。JDK的排序实现经过了大量优化比你自己手写的快排要快。我见过有人为了“性能”手写快排结果因为基准选择不当在部分有序数据上比Arrays.sort()慢了好几倍。第二个经验注意数据的实际分布。有一次处理日志数据需要按时间戳排序。时间戳是递增的几乎已经有序。用快排反而慢因为快排对有序数据不友好。后来换成归并排序性能提升明显。这个案例告诉我选排序算法之前一定要先了解数据的分布特征。第三个经验TopN问题不要全排序。找前K个最大元素用堆是O(nlogK)全排序是O(nlogn)。当K远小于n时堆的优势非常明显。我在一个实时排行榜项目中用PriorityQueue维护Top100处理百万级数据毫无压力。第四个经验稳定性有时候比性能更重要。在一个订单排序的场景中需要先按金额排序金额相同的按时间排序。如果用不稳定的快排金额相同的订单顺序会乱。后来改用归并排序问题解决。这个坑让我深刻理解了“稳定性”不是理论概念而是实际需求。第五个经验注意整数溢出。在写归并排序的mid (left right) / 2时如果left和right都很大相加会溢出。正确的写法是mid left (right - left) / 2。这个细节在面试中经常被考察在实际项目中也可能导致难以排查的bug。排序算法看起来是基础知识但真正用好需要理解每个算法的适用边界和实际表现。希望这篇内容能帮你在面试和实际开发中做出更好的选择。