java快速排序超详细总结：核心实现+简化版+趣味版

java快速排序超详细总结：核心实现+简化版+趣味版

面试高频 | 四种写法 | 含过程演示 | 新手友好

概要

详解快速排序三种写法：挖坑法、双指针交换法、单指针法，每种均附分步演示与代码注释。涵盖复杂度分析、稳定性及面试易错点，附Python一行趣味版，新手入门面试备战均适用。

先说结论

快速排序就干三件事：选基准 → 分左右 → 递归重复。

平均时间复杂度 $O(n\log n)$，原地排序，实际运行效率很高，是面试手撕排序的首选。

一、核心思想（用生活举例）

想象你在整理一堆扑克牌，随手抽一张作为"基准"：

把比它小的全扔左边，比它大的全扔右边
基准牌就稳稳坐在中间
然后对左边那堆、右边那堆，重复同样的操作
直到每堆只剩一张牌，整副牌就排好了

这就是快排，分治思想，化大问题为小问题。

二、挖坑法（新手首选）

思路

选左边第一个数当基准，把它"挖走"，留下一个坑。然后双指针从两端往中间夹，找到合适的数就填坑，自己变成新坑，最后把基准填回指针相遇的位置。

关键记忆点：基准选左边，必须先动右指针。

过程演示

动态演示：

静态演示：

再换一个数组，以 [5, 2, 9, 3, 8] 为例，基准 = 5（首位）：

初始：[_, 2, 9, 3, 8] 坑在位置0，pivot=5
i j

第1步：j从右往左找 ≤5 的数，找到 arr[3]=3
[3, 2, 9, _, 8] 把arr[3]=3移到坑里面，坑移到位置3
i j

第2步：i从左往右找 ≥5 的数，找到 arr[2]=9
[3, 2, _, 9, 8] arr[2]=9移到坑里面，坑移到位置2
i j

第3步：j继续往左找 ≤5 的数，j移到位置2，i==j 相遇
回填基准:[3, 2, 5, 9, 8]
↑ 基准归位

左边 [3, 2] 全 ≤ 5，右边 [9, 8] 全 ≥ 5，完美分区。

完整代码

public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 8, 4, 1, 7, 6};
quickSort(arr, 0, arr.length – 1); // 对整个数组排序
System.out.println(Arrays.toString(arr));
}

private static void quickSort(int[] arr, int left, int right) {
if (left >= right) return; // 区间只剩0或1个元素，天然有序，直接返回

int pivotIndex = partition(arr, left, right); // 分区，返回基准最终落的位置
quickSort(arr, left, pivotIndex – 1); // 递归处理基准左边的部分
quickSort(arr, pivotIndex + 1, right); // 递归处理基准右边的部分
}

private static int partition(int[] arr, int left, int right) {
int pivot = arr[left]; // 把左边第一个数当基准，"挖走"它，left位置就是第一个坑
int i = left; // i：左指针，始终指向当前坑的位置
int j = right; // j：右指针，从右端开始往左扫

while (i < j) {
// ① 右指针先动（基准选左边时铁律），从右往左找第一个 ≤ 基准的数
while (i < j && arr[j] > pivot) j—;
// 找到了，把 arr[j] 填进左边的坑，然后 i 右移，j 变成新坑
if (i < j) { arr[i] = arr[j]; i++; }

// ② 左指针从左往右找第一个 ≥ 基准的数
while (i < j && arr[i] < pivot) i++;
// 找到了，把 arr[i] 填进右边的坑，然后 j 左移，i 变成新坑
if (i < j) { arr[j] = arr[i]; j—; }
}

// i == j，指针相遇，当前位置就是基准的最终归宿，回填基准值
arr[i] = pivot;
return i; // 返回基准下标，用于划分左右子区间
}
}

注意事项

• 填坑前必须判断 i < j，否则指针相遇后还在赋值，数组会乱
• 基准选左边 → 必须先动右指针，这是铁律，背下来，反之就是：基准选右边→必须先动左指针
• 逻辑清晰，面试讲解首选这个写法

三、双指针交换法（进阶常用/面试用）

思路

不挖坑了，双指针直接找"错位元素"互换。右指针找小的，左指针找大的，找到就交换，最后把基准换到分界点。

比挖坑法代码更短，工程中更常见。

过程演示

以 [5, 2, 9, 3, 8] 为例，基准 = 5，i = 0, j = length – 1：

初始：[5, 2, 9, 3, 8] pivot=5
i j

第1步：j从右找 ≤5，找到 arr[3]=3，停下
i从左找 >5，找到 arr[2]=9，停下
交换 arr[2] 和 arr[3]：
[5, 2, 3, 9, 8]（已经交换过了）
i j

第2步：j继续左移找 ≤5，j=2，arr[2]=3 ≤5，停下
i继续右移找 >5，i=3，i > j，退出循环

最终：j=2 是分界点，交换 arr[0] 和 arr[2]
[3, 2, 5, 9, 8]
↑ 基准归位

关键：退出循环后和 j 交换，不是 i。

关键原因：j 是左区间最后一个 ≤ 基准的位置。！！！！！！！！！

完整代码

public class QuickSortSwap {
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 8, 4, 1, 7, 6};
quickSort(arr, 0, arr.length – 1);
System.out.println(Arrays.toString(arr));
}

private static void quickSort(int[] arr, int left, int right) {
if (left >= right) return; // 区间只剩0或1个元素，直接返回
int pivotIndex = partition(arr, left, right); // 分区，获取基准最终位置
quickSort(arr, left, pivotIndex – 1); // 递归左半部分
quickSort(arr, pivotIndex + 1, right); // 递归右半部分
}

private static int partition(int[] arr, int left, int right) {
int pivot = arr[left]; // 选左边界为基准
int i = left; // 左指针，从左端出发往右找"大数"
int j = right; // 右指针，从右端出发往左找"小数"

while (i < j) {
// ① 右指针先动，从右往左找第一个 ≤ 基准的数（找到"小数"）
while (i < j && arr[j] > pivot) j—;
// ② 左指针从左往右找第一个 > 基准的数（找到"大数"）
while (i < j && arr[i] <= pivot) i++;
// 两个"错位元素"都找到了，直接交换，各回各位
if (i < j) swap(arr, i, j);
}

// 循环结束时 i >= j，j 是左区间最后一个 ≤ 基准的位置（分界点）
// 把基准从 left 换到分界点 j，基准正式归位
// 注意：这里必须和 j 交换，不能和 i 交换！
swap(arr, left, j);
return j; // 返回基准下标
}

private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}

挖坑法 vs 双指针交换法

四、单指针法（最简单，零困惑）

思路

换个角度：不用双指针来回移动，改用一个指针 p 标记"小于等于基准的区域"的边界。

遍历数组，遇到 ≤ 基准的数就把它划入左区域，遍历完把基准放到分界点。

基准选右边界，完全不用考虑指针先后顺序问题。

过程演示

以 [5, 2, 9, 3, 8] 为例，基准 = 8（右边界）：

初始：p = -1（左区域为空）

i=0, arr[0]=5 ≤ 8：p=0，交换arr[0]和arr[0]，[5, 2, 9, 3, 8]
i=1, arr[1]=2 ≤ 8：p=1，交换arr[1]和arr[1]，[5, 2, 9, 3, 8]
i=2, arr[2]=9 > 8：跳过
i=3, arr[3]=3 ≤ 8：p=2，交换arr[2]和arr[3]，[5, 2, 3, 9, 8]

遍历结束：基准换到 p+1=3 的位置
结果：[5, 2, 3, 8, 9]
↑ 基准归位

完整代码

public class QuickSortSinglePointer {
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 8, 4, 1, 7, 6};
quickSort(arr, 0, arr.length – 1);
System.out.println(Arrays.toString(arr));
}

private static void quickSort(int[] arr, int left, int right) {
if (left >= right) return; // 区间只剩0或1个元素，直接返回
int pivotIndex = partition(arr, left, right); // 分区
quickSort(arr, left, pivotIndex – 1); // 递归左边
quickSort(arr, pivotIndex + 1, right); // 递归右边
}

private static int partition(int[] arr, int left, int right) {
int pivot = arr[right]; // 选右边界为基准（这样就不用管指针先后顺序了）
int p = left – 1; // p 是"小于等于基准的区域"的右边界，初始在区间外

// 遍历 left 到 right-1（不包括基准本身）
for (int i = left; i < right; i++) {
if (arr[i] <= pivot) {
p++; // 左区域扩大一格
swap(arr, p, i); // 把当前元素换进左区域
}
// 如果 arr[i] > pivot，直接跳过，它自然就在右区域
}

// 遍历结束，p+1 就是基准应该待的位置
// 把基准从右边界换过来，正式归位
swap(arr, p + 1, right);
return p + 1; // 返回基准下标
}

private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}

这个写法是 LeetCode 官方题解里最常见的风格，刷题时经常能看到。

五、趣味版：Python 一行快排

学了这么多，来个解压的😊。Python 一行代码实现快排：

def quick_sort(arr):
if len(arr) <= 1: return arr
else: return quick_sort([x for x in arr[1:] if x < arr[0]]) + [arr[0]] + quick_sort([x for x in arr[1:] if x >= arr[0]])

print(quick_sort([5, 2, 9, 3, 8, 4, 1, 7, 6]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

拆解一下：

arr[0] → 基准（第一个元素）
arr[1:] < arr[0] → 左边（比基准小的）
arr[1:] >= arr[0] → 右边（比基准大的）
递归拼接三部分 → 排好了

优点：写起来爽，面试秀一下没问题。
缺点：每次都创建新数组，空间复杂度 O(n)，不是原地排序，实际项目别用。

六、核心考点速查

时间复杂度

最坏情况怎么避免？

数组有序时快排会退化成 O(n²)，两种常见优化：

• 随机选基准：每次从区间里随机挑一个数当基准，打破有序的"陷阱"
• 三数取中：取 arr[left]、arr[mid]、arr[right] 三个数的中间值当基准，比随机更稳定

稳定性

快排是不稳定排序。

什么叫不稳定？举个例子：数组里有两个 5，排序前第一个 5 在第二个 5 左边，排完之后顺序可能反了。如果业务要求相同元素保持原来的相对顺序，用归并排序，不要用快排。

面试最容易写错的三个地方

① 递归终止条件别漏
当外层循环里面是true的时候，内层必须写下面这段代码来跳出循环。
当外层循环是i < j的时候，就不用写

if (left >= right) return;

漏了这行，递归永远不停，直接栈溢出。用 >= 而不是 ==，因为边界情况下 left 可能超过 right。

② 基准选左边，必须先动右指针

原因：基准挖走后，left 位置是空坑。如果先动左指针，左指针找到大数填到右边，左边坑消失了，但基准还没归位，数组就乱了。先动右指针，保证左边的坑始终存在，基准最后才能安全回填。

反过来同样成立：基准选右边 → 必须先动左指针。

③ 交换法最后和 j 交换，不是 i

退出循环时 i >= j，此时：

• j 停在左区间最后一个 ≤ 基准的位置（分界点）
• i 停在右区间第一个 > 基准的位置

基准要放在分界点，所以和 j 交换。如果和 i 交换，基准会跑到右区间里，分区就错了。

三种写法对比

作者：[识君啊]