算法 - 快速排序 (Quick Sort)

Posted on

1. 题目

给定一个整数数组 nums，把它按升序排序。要求手写快速排序，并分析平均与最坏时间复杂度、空间复杂度。

示例:

1
2
输入: [5, 2, 9, 1, 5, 6]
输出: [1, 2, 5, 5, 6, 9]

2. 解题思路

快速排序基于分治（Divide & Conquer）：

  1. 选基准 pivot：从数组里挑一个值（首/尾/随机/三数取中）。
  2. 分区 partition：重排数组，使「小于 pivot 的在左边、大于的在右边」，并把 pivot 放到它最终应在的位置 p。
  3. 递归：对左右两个子区间分别快排。

分区是灵魂。最常用 Lomuto 方案：以最后一个元素为 pivot，用指针 i 维护「小于区」的右边界，遍历指针 j，遇到比 pivot 小的就与 i+1 交换。

复杂度：

  • 平均时间 O(n log n)，每次大致对半分。
  • 最坏时间 O(n²)：数组已有序且总选端点为 pivot，退化为链式划分。随机化 pivot 可高概率避免。
  • 空间 O(log n)：递归栈（原地版本），非原地拼接版本为 O(n)。
  • 快排是不稳定排序（相等元素相对顺序可能改变）。

3. TypeScript 实现

3.1 简洁版（易记，额外空间 O(n)）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function quickSortSimple(nums: number[]): number[] {
    if (nums.length <= 1) return nums;

    const pivot = nums[Math.floor(nums.length / 2)];
    const left: number[] = [];
    const mid: number[] = [];
    const right: number[] = [];

    for (const x of nums) {
        if (x < pivot) left.push(x);
        else if (x === pivot) mid.push(x);
        else right.push(x);
    }

    return [...quickSortSimple(left), ...mid, ...quickSortSimple(right)];
}

用 mid 单独收集等于 pivot 的元素，能正确处理重复值且不重复比较，避免部分实现卡在相等上。

3.2 原地版（面试官更想看的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function quickSort(nums: number[], lo = 0, hi = nums.length - 1): number[] {
    if (lo >= hi) return nums;

    const p = partition(nums, lo, hi);
    quickSort(nums, lo, p - 1);
    quickSort(nums, p + 1, hi);
    return nums;
}

function partition(nums: number[], lo: number, hi: number): number {
    // 随机化 pivot，避免有序数据退化
    const rand = lo + Math.floor(Math.random() * (hi - lo + 1));
    [nums[rand], nums[hi]] = [nums[hi], nums[rand]];

    const pivot = nums[hi];
    let i = lo; // i 指向「小于区」的下一个位置

    for (let j = lo; j < hi; j++) {
        if (nums[j] < pivot) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
        }
    }

    [nums[i], nums[hi]] = [nums[hi], nums[i]]; // pivot 归位
    return i;
}

// 测试
console.log(quickSort([5, 2, 9, 1, 5, 6])); // [1,2,5,5,6,9]

4. 面试延伸

  • 为什么快排实践中比归并快？ 原地、缓存友好、常数小；归并需要额外数组。
  • ** nth element / Top-K（快速选择 215 题）**：partition 后只递归一边，平均 O(n) 找第 K 大，是快排的孪生应用。
  • 三路快排（Dutch National Flag）：把区间分成 < == > 三段，专门治「大量重复元素」，此时等于段直接不再递归。
  • 手写必问：pivot 怎么选？最坏什么情况？是否稳定？——三点答上来就是满分。

难度：中等 | 手写排序基本功 | 快速选择衍生高频