企业官网建设流程全解析

排序算法这块内容，我前前后后讲过不下十遍，每次讲到后半段——也就是归并、快排、堆排、计数、桶排、基数排这几个——总有人问我：这些算法到底怎么选？为什么面试老爱问快排和归并的区别？堆排明明时间复杂度也是O(nlogn)，为什么实际项目里用得少？这些问题光看代码是看不出来的，得把每个算法的“脾气”摸透。这篇就接着上篇的内容，把剩下这六个经典排序算法从原理到Java实现，再到实际选型，完整地捋一遍。不管你是正在准备面试，还是想在实际项目里选一个靠谱的排序方案，又或者只是想把算法基础打扎实，下面这些内容应该都能帮到你。

1. 归并排序：分治思想最标准的教科书案例

归并排序是我个人认为最能体现“分治”思想的排序算法。它的逻辑非常干净：把数组一分为二，左右两边分别排好序，然后把两个有序数组合并成一个更大的有序数组。递归下去，直到子数组只有一个元素——单个元素天然有序，这就是递归的终止条件。

1.1 分治的拆解逻辑与递归树

理解归并排序，关键是理解它的递归树。假设数组有8个元素，第一层拆成两个4元素子数组，第二层拆成四个2元素子数组，第三层拆成八个1元素子数组。然后从底层往上合并：1合1变2，2合2变4，4合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[mid+1]，说明左右两半已经整体有序了，不需要再合并。这个优化对于部分有序的数据效果非常明显。

注意：归并排序的稳定性依赖于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和j+1。这个细节我见过太多人写错了。

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，子节点索引2i+1和2i+2，每次访问的位置跨度很大，缓存命中率低。

第二，堆排序的交换次数多。每次下沉都可能触发多次交换，而快排的分区操作交换次数相对较少。在现代CPU上，缓存未命中的代价远高于简单的算术运算，所以访存模式的影响非常大。

这也是为什么Java的Arrays.sort()对基本类型用双轴快排，而不是堆排序——虽然堆排序空间复杂度更优，但实际性能差距太大。

3.3 堆排序的适用场景与替代方案

堆排序最适合的场景是“只需要前K个最大/最小元素”。维护一个大小为K的堆，遍历所有元素，时间复杂度是O(nlogK)，空间复杂度是O(K)。这比全排序再取前K个要高效得多。

Java中可以用PriorityQueue来实现这个需求：

// 找前K个最大的元素 public static int[] topK(int[] arr, int k) { PriorityQueue<Integer> 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(n+k)，其中k是数据范围。当k远大于n时，计数排序反而不如比较排序。比如对100个范围在0到1000000之间的数排序，计数排序需要创建一个百万大小的数组，空间浪费严重。

计数排序的一个重要应用是作为基数排序的子过程。基数排序的每一轮都需要对某一位进行稳定排序，计数排序正好满足这个需求。

4.2 桶排序：分桶策略决定性能上限

桶排序的思路是把数据分到若干个桶里，每个桶内部单独排序，然后按顺序把桶里的元素串起来。桶排序的性能取决于数据分布的均匀程度——如果数据均匀分布，每个桶里的元素数量差不多，时间复杂度接近O(n)；如果数据全部集中在少数几个桶里，就退化成桶内排序的复杂度。

public static void bucketSort(double[] arr) { int n = arr.length; List<List<Double>> 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 (List<Double> 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(n+k))，其中d是最大数的位数，k是基数（十进制是10）。对于整数排序，基数排序通常比比较排序快，特别是当数据量大且位数不多时。

基数排序的一个重要细节是：从低位到高位排序时，每一轮必须从后往前遍历原数组来填充output数组。这是为了保证稳定性——从后往前遍历时，相同位的元素会保持原来的相对顺序。

5. 十大排序算法的横向对比与选型决策

把十大排序算法放在一起对比，才能真正理解每个算法的定位。下面这张表是我自己整理的，涵盖了时间复杂度、空间复杂度、稳定性、实际性能等关键维度。

5.1 按数据规模选：小数组别用快排

数据规模小于100时，插入排序往往是最快的。因为插入排序的常数因子极小，没有递归开销，对CPU缓存友好。Java的Arrays.sort()在子数组长度小于47时，会切换到插入排序。

数据规模在100到10000之间时，快排和归并的差距不大，选哪个都可以。但如果要求稳定，选归并；如果要求原地，选快排。

数据规模超过10000时，快排的优势开始显现。但要注意基准选择策略，避免最坏情况。如果数据可能已经部分有序，三数取中或随机化是必须的。

5.2 按数据特征选：整数、浮点数、对象各有最优解

如果数据是范围有限的整数，计数排序或基数排序是最快的。比如对年龄、成绩、等级这类数据排序，计数排序的O(n+k)远优于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。

排序算法看起来是基础知识，但真正用好需要理解每个算法的适用边界和实际表现。希望这篇内容能帮你在面试和实际开发中做出更好的选择。