Java 快速排序：分治思想的最强代表

面试官让你手写快排？稳住，写完就上岸了

引言

快速排序（Quick Sort）是分治思想的最强代表，也是面试出现频率最高的排序算法。

**平均 O(n log n)**，JDK Arrays.sort() 底层就是快排的改良版（Dual-Pivot QuickSort）。基准选择 + 递归边界 + 最坏情况，三座大山压垮过无数面试者。

这篇文章，我会把快排拆到底：

• 用 ASCII 图演示 partition 的完整过程（Lomuto 版）
• 推导为什么最坏情况是 O(n²) 以及如何避免
• 列出 5 个高频易错点（递归终止条件最容易错）
• 配套 LeetCode 912（必须 AC 的快排题）和 215（第 k 大元素）

---

1. 核心思想：分而治之

1.1 通俗理解

快排的精髓用一句话讲：选一个基准，把比它小的扔左边，比它大的扔右边，递归搞定两边。

想象你有一堆混在一起的扑克牌，要按数字大小排序：

1. 随便抽一张当基准（pivot）
2. 把比它小的放左边，比它大的放右边
3. 左边那堆继续抽基准 + 分区
4. 右边那堆继续抽基准 + 分区
5. 直到每堆只剩 1 张或 0 张

1.2 ASCII 图解演示（双指针法）

以数组 [10, 7, 8, 9, 1, 5] 为例，pivot 选最右元素 5：

初始：[10, 7, 8, 9, 1, 5]
pivot = 5，i = -1（小于区的边界）

j=0：10 > 5，不动
j=1：7 > 5，不动
j=2：8 > 5，不动
j=3：9 > 5，不动
j=4：1 < 5，i++ → i=0，swap(arr, 0, 4)
     → [1, 7, 8, 9, 10, 5]

循环结束：swap(arr, i+1, high) → swap(arr, 1, 5)
结果：[1, 5, 8, 9, 10, 7]
       ↑  ↑              ↑
       小于  pivot      大于
       
pivotIndex = 1

递归左半部分 [1] → 已有序
递归右半部分 [8, 9, 10, 7]
  pivot = 7，i = 1
  j=2：8 > 7，不动
  j=3：9 > 7，不动
  j=4：10 > 7，不动
  swap(arr, 2, 5) → [1, 5, 7, 9, 10, 8]
  pivotIndex = 2

  递归 [1, 5, 7] 和 [9, 10, 8]
    递归 [9, 10, 8]，pivot = 8
    j=4：9 > 8，不动
    j=5：10 > 8，不动
    swap(arr, 4, 5) → [1, 5, 7, 8, 9, 10]
    
最终：[1, 5, 7, 8, 9, 10]

1.3 三个关键观察

1. 每趟 partition 后，pivot 一定在最终位置——左边都小，右边都大
2. 递归深度 = partition 次数——理想情况 log n，最坏 n
3. pivot 选择决定性能——选得不好直接退化成 O(n²)

---

2. 完整 Java 实现（经典双指针法）

import java.util.Arrays;
import java.util.Random;

public class QuickSort {
    private static final Random RANDOM = new Random();

    /**
     * 快排入口
     */
    public static void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        quickSort(arr, 0, arr.length - 1);
    }

    /**
     * 递归排序 [low, high] 区间
     */
    private static void quickSort(int[] arr, int low, int high) {
        // 递归终止：区间只剩 0 或 1 个元素
        if (low >= high) {
            return;
        }
        // 优化：小数组切插入排序（提升常数因子性能）
        if (high - low <= 16) {
            insertionSort(arr, low, high);
            return;
        }
        // 随机选 pivot，避免最坏情况
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }

    /**
     * Lomuto 分区方案
     */
    private static int partition(int[] arr, int low, int high) {
        // 随机选 pivot 并交换到末尾
        int randomIndex = low + RANDOM.nextInt(high - low + 1);
        swap(arr, randomIndex, high);
        int pivot = arr[high];
        // i 是"小于区"的右边界
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j);
            }
        }
        // 把 pivot 放到"小于区"右边
        swap(arr, i + 1, high);
        return i + 1;
    }

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

    // 小数组用插入排序（优化）
    private static void insertionSort(int[] arr, int low, int high) {
        for (int i = low + 1; i <= high; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= low && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        System.out.println("排序前: " + Arrays.toString(arr));
        quickSort(arr);
        System.out.println("排序后: " + Arrays.toString(arr));
    }
}

---

3. 复杂度证明

3.1 时间复杂度

最坏情况（O(n²)）：每次 partition 都把数组分成 1 和 n-1

• 递归树深度 = n
• 总比较次数 = n + (n-1) + … + 1 = n(n-1)/2 = O(n²)
• 触发条件：数组已经有序 + 每次选最右/最左元素做 pivot

最好情况（O(n log n)）：每次 partition 都从中间分

• 递归树深度 = log n
• 每层 O(n) 次比较
• 总比较次数 = n log n

平均情况（O(n log n)）：

• 期望递归深度 = 2 log n
• 数学证明见《算法导论》第 7 章

3.2 空间复杂度

• 递归调用栈深度 = O(log n)（理想）或 O(n)（最坏）
• 平均 O(log n)，最坏 O(n)

3.3 稳定性：不稳定

• partition 时的交换会跳过中间元素
• 相同元素的相对顺序可能被破坏
• 不稳定排序

---

4. 五个高频易错点

易错点 1：递归终止条件写成 low <= high

// ❌ 错误：会无限递归（low == high 时还会继续调用）
if (low <= high) {
    int pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
}

// ✅ 正确：low == high 时已经有序，无需递归
if (low < high) {
    int pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
}

易错点 2：i 从 low 开始

// ❌ 错误：第一个小于 pivot 的元素会跟自己交换
int i = low;
for (int j = low; j < high; j++) {
    if (arr[j] <= pivot) {
        swap(arr, i, j);  // i=low 时 j=low 自己跟自己交换
        i++;
    }
}

// ✅ 正确：i 是"小于区"的右边界，初始时小于区为空
int i = low - 1;
for (int j = low; j < high; j++) {
    if (arr[j] <= pivot) {
        i++;
        swap(arr, i, j);
    }
}

易错点 3：for 循环写成 j <= high

// ❌ 错误：pivot 自身会被纳入比较
for (int j = low; j <= high; j++) {
    if (arr[j] <= pivot) { ... }
}

// ✅ 正确：pivot 在 high 位置，不参与比较
for (int j = low; j < high; j++) {
    if (arr[j] <= pivot) { ... }
}

易错点 4：pivot 选择不当导致最坏

// ❌ 错误：固定选最右/最左，对有序数组退化为 O(n²)
int pivot = arr[high];

// ✅ 正确：随机选 pivot，把最坏情况的概率降到 1/n!
int randomIndex = low + RANDOM.nextInt(high - low + 1);
int pivot = arr[randomIndex];
swap(arr, randomIndex, high);

易错点 5：partition 里 pivot = arr[high] 后又交换

// ❌ 错误：pivot 变量保存的是值，但交换后 arr[high] 已变
int pivot = arr[high];
swap(arr, low, high);  // arr[high] 已变
// 后续 arr[j] <= pivot 比较时 pivot 还是原值，没问题
// 但读起来很乱

// ✅ 正确：先随机交换再保存
int randomIndex = low + RANDOM.nextInt(high - low + 1);
swap(arr, randomIndex, high);
int pivot = arr[high];

---

5. JDK 实战：Dual-Pivot QuickSort

JDK 的 Arrays.sort() 用的不是经典快排，而是 Dual-Pivot QuickSort（双基准快排），由 Vladimir Yaroslavskiy 在 2009 年提出。

5.1 核心改进

传统快排：选 1 个 pivot，分 2 块
Dual-Pivot：选 2 个 pivot，分 3 块

传统：    [< pivot]  pivot  [> pivot]
双基准：  [< p1]  [p1, p2]  [> p2]

5.2 性能优势

• 减少递归深度（log₂ n vs log₃ n）
• 比较次数减少约 20%
• 实际比经典快排快 10-20%

5.3 JDK 还做了哪些优化？

// 摘自 OpenJDK 源码（简化版）
static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen) {
    // 1. 小数组用插入排序
    if (right - left < QUICKSORT_THRESHOLD) {
        insertionSort(a, left, right);
        return;
    }
    // 2. 递归过深切堆排序
    if (depth == 0) {
        heapSort(a, left, right);
        return;
    }
    // 3. 双基准分区
    int[] pivots = partitionDualPivot(a, left, right);
    // 4. 递归三部分
    sort(a, left, pivots[0] - 1, ...);
    sort(a, pivots[0] + 1, pivots[1] - 1, ...);
    sort(a, pivots[1] + 1, right, ...);
}

三个关键优化：

1. 小数组切插入排序（n < 47）
2. 递归过深切堆排序（防止栈溢出）
3. 三路快排（大量重复元素时效率高）

---

6. 适用场景与禁区

6.1 适用场景

• 数据量大且乱序：快排是首选
• 内存充足：递归调用需要栈空间
• 要求平均性能高：O(n log n) 平均 + 较低常数

6.2 不适用场景

• 数据基本有序：固定选 pivot 会退化（用随机化可缓解）
• 要求稳定排序：快排不稳定，改成稳定版本代价大
• 链表排序：快排对链表不友好（partition 需要随机访问）

---

7. 面试常见变形

变形 1：随机快排

思路：pivot 随机选，把最坏情况的概率降到极低

private static int randomPartition(int[] arr, int low, int high) {
    int randomIndex = low + RANDOM.nextInt(high - low + 1);
    swap(arr, randomIndex, high);
    return partition(arr, low, high);
}

面试加分项：能说出”期望时间复杂度 O(n log n)，最坏 O(n²) 但概率极低”。

变形 2：三路快排

思路：把等于 pivot 的元素单独放一块

private static void threeWayQuickSort(int[] arr, int low, int high) {
    if (low >= high) return;
    int pivot = arr[low];
    int lt = low, gt = high, i = low + 1;
    while (i <= gt) {
        if (arr[i] < pivot) {
            swap(arr, lt++, i++);
        } else if (arr[i] > pivot) {
            swap(arr, i, gt--);
        } else {
            i++;
        }
    }
    threeWayQuickSort(arr, low, lt - 1);
    threeWayQuickSort(arr, gt + 1, high);
}

适用：大量重复元素的场景（如排序 0/1 数组），效率极高。

变形 3：第 k 大元素（快速选择）

思路：只递归 pivot 一边，平均 O(n)

public static int findKthLargest(int[] nums, int k) {
    return quickSelect(nums, 0, nums.length - 1, nums.length - k);
}

private static int quickSelect(int[] arr, int low, int high, int k) {
    int pivotIndex = partition(arr, low, high);
    if (pivotIndex == k) return arr[pivotIndex];
    else if (pivotIndex < k) return quickSelect(arr, pivotIndex + 1, high, k);
    else return quickSelect(arr, low, pivotIndex - 1, k);
}

复杂度：平均 O(n)，最坏 O(n²)。

---

8. LeetCode 真题实战

题目 1：912. 排序数组（中等）

这道题是快排的试金石——直接套用上面的随机快排模板，能 AC。

class Solution {
    private static final Random RANDOM = new Random();
    
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    
    private void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
    
    private int partition(int[] arr, int low, int high) {
        int randomIndex = low + RANDOM.nextInt(high - low + 1);
        swap(arr, randomIndex, 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;
    }
    
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

题目 2：215. 数组中的第 K 个最大元素（中等）

快速选择解法：套用上面的变形 3 模板，能 AC。

复杂度：平均 O(n)，最坏 O(n²)。

---

总结

一句话精髓

快排 = 选 pivot + 分区 + 递归左右。

三个关键洞察

1. 随机化是必备的——不随机就是 O(n²) 风险炸弹
2. **递归终止是 low < high**——写成 <= 永远跑不完
3. JDK 用 Dual-Pivot——双基准比单基准快 20%

下一步行动

1. 把上面的随机快排模板背下来，LeetCode 912 必须能 10 分钟内写完
2. 手写三路快排，理解大量重复元素的优化思路
3. 在 OpenJDK 源码搜索 DualPivotQuicksort，看工业级实现

---

本文由 AI 对话整理精炼而成
整理时间：2026-06-18
原文来源：DeepSeek