别再事倍功半了，手写实现才是事半功倍的正解

刚毕业那会儿，我盯着屏幕上报错的 IndexOutOfBoundsException 抓耳挠腮。复制来的排序代码跑不通，改参数没反应，查文档全是英文术语。那种“我明明按教程敲的，为什么它就不行”的无力感，相信很多应届生都经历过。

后来我悟了：调不通，是因为你不懂底层逻辑。 与其在 try-catch 里打地鼠，不如静下心来，把核心算法手写实现一遍。今天我们就拿最经典的**快排（Quick Sort）**开刀，剖析为什么你写的代码是“事倍功半”，而真正的高手代码是“事半功倍”。

入口定位：从 Java 官方源码看排序

很多新人以为 Java 的 Arrays.sort() 是黑盒，其实不是。去 OpenJDK 官方源码仓库 看看 java.util.Arrays 类，你会发现一个秘密：对于基本类型（如 int[]），它用的是双轴快排（Dual-Pivot Quicksort）；对于对象数组（如 Object[]），它用的是归并排序（TimSort）。

为什么不同？因为基本类型不需要保持稳定性，且内存开销小，快排快；对象数组需要稳定排序（相等元素顺序不变），归并更合适。

如果你不知道这些，你就永远只能复制代码，遇到 int 和 Integer 性能差异巨大时，只会一脸懵圈。

核心片段：双轴快排的递归骨架

下面这段代码摘录自 OpenJDK 17 的 DualPivotQuicksort.java，做了极大简化，但保留了核心递归逻辑。注意看它如何选取两个轴（pivot），并将数组分成三部分：< p1、[p1, p2]、> p2。

// 简化版双轴快排核心逻辑，源自 OpenJDK Arrays.java
public static void sort(int[] a, int left, int right) {// 基线条件：数组长度小于阈值，改用插入排序if (right - left < INSERTION_SORT_THRESHOLD) {insertionSort(a, left, right);return;}// 选取两个轴：这里简化为取首尾元素，实际源码有更复杂的采样策略int p1 = a[left];int p2 = a[right];// 确保 p1 <= p2，否则交换if (p1 > p2) {int temp = p1;p1 = p2;p2 = temp;}// 三指针分区：// left: 指向下一个要处理的元素// less: 指向 < p1 区域的右边界// greater: 指向 > p2 区域的左边界int less = left + 1;int greater = right - 1;for (int i = less; i <= greater; i++) {int current = a[i];if (current < p1) {// 比小轴还小，放到 < p1 区域swap(a, i, less);less++;} else if (current > p2) {// 比大轴还大，放到 > p2 区域while (a[greater] > p2) {greater--;}swap(a, i, greater);// 注意：swap 后 i 位置的元素来自 greater，需要重新判断i--; }// 如果在 [p1, p2] 之间，不动，i 自然后移}// 将轴放到正确位置swap(a, left, less - 1);swap(a, right, greater + 1);// 递归处理三个子区间sort(a, left, less - 2);       // < p1 部分sort(a, less, greater);        // [p1, p2] 部分sort(a, greater + 2, right);   // > p2 部分
}

逐行关键点解读：

INSERTION_SORT_THRESHOLD：当子数组很小时，快排常数因子大，插入排序反而更快。这是“事半功倍”的关键——混合策略。
i-- 这一行极易出错。因为 greater 位置的元素被换到了 i，它可能小于 p1 或大于 p2，必须重新检查。很多复制来的代码漏掉这里，导致排序错误。
三指针分区将数组一分为三，比单轴快排减少了一次递归深度，平均比较次数更少。

设计思想：为什么是“事半功倍”？

很多应届生写快排，习惯用“挖坑法”或“Lomuto 分区”，代码看着简单，但性能差、易栈溢出。OpenJDK 的双轴快排体现了三个工程思想：

自适应优化：不是一味递归，而是根据数据特征切换策略。小数组用插入，大数组用快排，近乎有序的用归并。这叫混合排序。
缓存友好：双轴分区比单轴分区减少内存访问次数。CPU 缓存行是 64 字节，连续访问比随机访问快一个数量级。
避免最坏情况：通过精心选择的轴（源码中会用中位数法），几乎不可能出现 O(n^2) 的情况。

你手写实现时，如果只盯着“交换元素”，忽略了这些底层考量，写出的代码就是“事倍功半”——跑得慢、内存高、还容易出错。

手写简化版：你该怎么写？

别被 OpenJDK 的几百行代码吓到。作为应届生，你不需要写出工业级代码，但必须写出正确、高效、可解释的版本。下面是一个适合面试和日常使用的简化版，兼顾性能与可读性：

public class QuickSortOptimized {private static final int INSERTION_THRESHOLD = 10;public static void sort(int[] arr) {if (arr == null || arr.length < 2) return;quickSort(arr, 0, arr.length - 1);}private static void quickSort(int[] arr, int left, int right) {// 小数组用插入排序，减少递归开销if (right - left < INSERTION_THRESHOLD) {insertionSort(arr, left, right);return;}// 三数取中法选轴，避免最坏情况int mid = (left + right) / 2;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);// 将中位数放到 right-1 位置，作为轴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 insertionSort(int[] arr, int left, int right) {for (int i = left + 1; i <= right; i++) {int key = arr[i];int j = i - 1;while (j >= left && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}
}

这个版本的“事半功倍”之处：

三数取中：比随机选轴更稳定，避免有序数组退化成 O(n^2)。
插入排序兜底：小数组递归开销大于实际排序开销，插入排序无递归，常数因子小。
代码简洁：不到 50 行，面试时能手写，日常能用，性能接近工业级。

应用场景：避坑与选型

什么时候用你手写的快排？什么时候用 Arrays.sort()？

场景	推荐方案	原因
基本类型数组	`Arrays.sort()`	官方实现经过极致优化，双轴快排
对象数组需稳定	`Arrays.sort()`	内部用 TimSort，稳定且自适应
自定义复杂对象	手写快排或归并	需要控制比较逻辑，避免频繁创建临时对象
嵌入式/资源受限	手写快排	避免库函数依赖，内存可控