算法 | 快速排序的演进和3种分区实现（JavaScript）

发表于 分类于 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 13 分钟

本文用 JavaScript 梳理快速排序从非原地实现到原地分区的演进：先用最直观的递归拼接版本理解分治思想，再分别实现 Lomuto、Hoare / Algs 4 双指针分区和三向切分，并对比它们在有序数据、重复元素和空间开销上的表现。

快速排序的精髓在于分而治之，主要分为三个步骤：

  1. 选基准 (Pivot)：从数组中选一个元素作为“基准”。
  2. 分区 (Partition)：重新排序数组，所有比基准小的元素摆放在左边，比基准大的摆在右边。这里就得到了左右两个子集。
  3. 递归：（这个时候左子集都是小于基准元素但是是乱序的，右子集也是。所以还要）对左、右两个子集重复上述步骤，进行递归快排，直到子集大小 <= 1。

Q：为什么是 <= 1 而不是 == 1？

递归时可能产生空数组/空区间，空数组和单元素数组都天然有序，所以终止条件要覆盖 <= 1。

根据分区时是否创建新数组，可以分为两类实现。

1 非原地排序法

这个很简单，也可以直接看代码。

这是最直观的写法，通过创建新数组来存储子集。非原地版本会频繁创建子数组，峰值额外空间通常高于原地版，累计分配量平均可达 O(n log n)。

步骤：

  1. 从原数组中取出基准元素。
  2. 创建两个空数组 leftArr 和 rightArr，分别放置小于、大于基准元素的元素。
  3. 遍历剩余元素，小于等于基准的放 leftArr，大于的放 rightArr。
  4. 递归排序两个子数组，然后拼接，注意中间还要拼接上基准。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function quickSort(arr) {
    if (arr.length <= 1) return arr
    // 选择基准元素
    // 这里选择数组的第一个，也有人选数组中间值
    const pivot = arr.splice(0, 1)[0]
    const leftArr = []
    const rightArr = []
    // 循环，小于等于基准元素放到左边，大于放到右边
    arr.forEach(item => {
        if (item <= pivot) {
            leftArr.push(item)
        } else{
            rightArr.push(item)
        }
    })
    // 这个时候拼接数组，小于基准值数组（leftArr） + 基准值 + 大于基准值数组（rightArr）
    // 并且两侧数组也要递归进行快排
    return quickSort(leftArr).concat([pivot], quickSort(rightArr))
}

这份代码有几个问题。

问题 1：选第一个元素作为基准元素。

这个问题同样适用于下面的代码。

已经有序或基本有序的数组，第一个元素往往是极值（最小或最大），每次分区都有一边为空，另一边包含几乎所有元素，递归深度接近 n，时间复杂度退化为 O(n²)。

用 [1, 2, 3, 4, 5, 6, 7, 8] 举例子对比下。

（a）选第一个元素作为基准（退化情况）：

1
2
3
4
5
6
7
8
pivot=1, left=[], right=[2,3,4,5,6,7,8]
         pivot=2, left=[], right=[3,4,5,6,7,8]
                  pivot=3, left=[], right=[4,5,6,7,8]
                           pivot=4, left=[], right=[5,6,7,8]
                                    pivot=5, left=[], right=[6,7,8]
                                             pivot=6, left=[], right=[7,8]
                                                      pivot=7, left=[], right=[8]
                                                               pivot=8

递归深度：8 层，每次只分出一个元素，O(n²)。

（b）选中间元素作为基准（理想情况）：

1
2
3
4
5
pivot=4, left=[1,2,3], right=[5,6,7,8]
         pivot=2, left=[1], right=[3]     pivot=6, left=[5], right=[7,8]
                  pivot=1     pivot=3              pivot=5     pivot=7
                                                                   right=[8]
                                                                       pivot=8

递归深度：4 层，每次都大致对半分，O(n log n)。

问题 2：等于基准的元素被迫参与递归

与基准元素相等的元素都放到左边去了，被迫继续参与后续递归。而它们实际上已经可以确定位置。更好的做法是把它们单独拎出来，不再参与排序。

改进版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 改进版
function quickSort(arr) {
    if (arr.length <= 1) return arr
    // 选数组中间的元素作为基准元素，也可以是第一个元素
    const pivotIndex = Math.floor(arr.length / 2)
    const pivot = arr[pivotIndex]
    const leftArr = []
    const equalArr = []
    const rightArr = []
    // 循环，小于基准元素放到左边，大于放到右边
    arr.forEach(item => {
        if (item < pivot) {
            leftArr.push(item)
        } else if (item > pivot) {
            rightArr.push(item)
        } else {
            equalArr.push(item)
        }
    })
    return quickSort(leftArr).concat(equalArr, quickSort(rightArr))
}

2 原地排序法

上面的非原地排序法固然简单，但是它每次递归都创建左右子数组，数据量大时内存开销很大。

那么原地快排的核心思路就是：不创建新数组，直接在原数组上通过交换来完成分区。

整体流程和非原地版本一致：选基准 → 分区 → 递归左右子集。难点在于「分区」这一步——如何只通过交换，就把数组分成「左边 ≤ pivot、右边 ≥ pivot」两部分。

分区的具体实现有 3 种，也代表了 3 种演进思路：

  1. Lomuto 分区法（单向扫描）
  2. Hoare / Algs 4 分区法（双指针法）
    1. “基准归位”写法（Algs 4 / Sedgewick 版本）
    2. “单纯切分”写法（原始 Hoare 版本）
  3. 三向切分（3-Way Partitioning / Dijkstra）

2.1 Lomuto 分区法（单向扫描）

原理：维护两个指针，i 是“小于区右边界的后一位”，j 从左向右扫描。[left, i-1] 都是小于 pivot 的元素，[i, j-1] 都是大于等于 pivot 的元素。

步骤：

  1. 选择最右侧元素作为基准 pivot。

  2. 初始化 i = left

  3. 用 j从 left扫描到 right - 1：

    • 若 arr[j] < pivot，则交换 arr[i] 和 arr[j]，然后 i++。

  4. 扫描结束后，将 pivot 交换到 i 的位置。

  5. 返回 i（pivot 的最终位置）

为什么 i 指针总是「小于 pivot 区」的右边界呢？

初始时 i = left，左侧为空，不变量自然成立。此后每次循环：

  • 如果 arr[j] < pivot：交换 arr[i] 和 arr[j]，然后 i++。交换到 i 位置的元素一定 < pivot（if 条件保证），所以 i 左侧仍然全是 < pivot 的元素。
  • 如果 arr[j] >= pivot：不做任何操作，j++ 继续扫描。i 不动，不变量不受影响。

因此在扫描过程中，[left, i - 1] 始终是「小于 pivot 区」，而 i 是下一个小元素应该放入的位置。

有一个说法可以这样理解：

交换的意义是：当遇到一个小的元素（< pivot）时，我们想把它放到"小值区域"的末尾。这个区域的末尾就是 i 的位置。但 i 的位置当前放的是一个大的元素（>= pivot），所以我们交换它们。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return arr
    const pivotIndex = partition(arr, left, right)
    quickSort(arr, left, pivotIndex - 1)
    quickSort(arr, pivotIndex + 1, right)
    return arr
}

function partition(arr, left, right) {
    const pivot = arr[right] // 选择最右侧为基准
    let i = left
    for(let j = left; j < right; j++) {
        if (arr[j] < pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]]
            i++
        }
    }
    [arr[i], arr[right]] = [arr[right], arr[i]] // 基准归位
    return i
}

疑问：

Q1、为什么选 arr[right] 做 pivot？

因为扫描范围是 [left, right-1]，pivot 不参与扫描，扫描范围刚好是除 pivot 外的所有元素。选最右端是为了让 for 循环的范围 [left, right) 刚好是「除 pivot 外的所有元素」。

Q2、为什么交换后要 i++？

交换过来的 arr[j] 一定 < pivot（if 条件保证），它属于小于区，所以小于区的右边界要右移一位。

当然这个方法也有缺点，在数组几乎有序或大量重复元素时，效率会退化到 O(n^2)。

2.2 Hoare / Algs 4 分区法（双指针法）

Algs4 指的是《算法》第四版。

Lomuto 写法简单，但交换次数通常更多；双指针法可以减少一些不必要的交换。

双指针法采用左右夹逼的策略：两个指针从数组两端相向而行，各自跳过「已经站对位置」的元素，发现站错位置的就交换。

步骤：

  1. 选择一个基准 pivot（通常选 arr[left] 或中间元素）。
  2. 左指针 i 从左向右移动，跳过所有 < pivot 的元素（这些元素本来就应该在左边）。
  3. 右指针 j 从右向左移动，跳过所有 > pivot 的元素（这些元素本来就应该在右边）。
  4. 当 i 和 j 都停下时，说明 arr[i] 应该在右边、arr[j] 应该在左边，交换它们。
  5. 重复 2-4，直到 i >= j（指针交错），分区完成。

根据「分区完成后 pivot 是否归位」，双指针有两种写法，分别是 Hoare 法和 Algs4 法，前者是以快速排序发明者 C. A. R. Hoare 命名的，也是快排最初的实现版本，后者是书籍《算法》第四版里的写法。

写法一：单纯切分（原始 Hoare 版本）

分区完成后不保证 pivot 在最终位置，只能保证[left, j]全部<= pivot，[j+1, right]全部>= pivot。递归时 pivot 可能还在左右子数组中继续参与排序

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
function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right ) return arr
    const p = partition(arr, left, right)
    // 基准值没归位
    quickSort(arr, left, p)
    quickSort(arr, p + 1, right)
    return arr
}

function partition(arr, left, right) {
    const pivot = arr[Math.floor((left + right) / 2)]
    let i = left
    let j = right
    while(true) {
        // 从左向右找第一个 >= pivot 的元素
        while(arr[i] < pivot) i++
        // 从右向左找第一个 <= pivot 的元素
        while(arr[j] > pivot) j--
        // i、j相遇或交错，分区完成
        if (i >= j) {return j}
        // 交换
        [arr[i], arr[j]] = [arr[j], arr[i]]
        // 移动指针继续
        i++
        j-- 
    }
}

写法二：基准归位（Algs4 / Sedgewick 版本）

在双指针扫描的基础上，最后多做一步，把 pivot 交换到它的最终位置。这样 pivot 就不再参与后续递归，递归范围变为 [left, p-1] 和 [p+1, right]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function quickSort(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return arr
    const pivotIndex = partition(arr, left, right)
    quickSort(arr, left, pivotIndex - 1) // pivot 已在位置 pivotIndex，左右分别递归
    quickSort(arr, pivotIndex + 1, right)
    return arr
}

function partition(arr, left, right) {
    const pivot = arr[left] // 选最左元素做基准
    let i = left
    let j = right + 1
    while(true) {
        // 从左找第一个 >= pivot 的位置（跳过所有 < pivot 的）
        while(arr[++i] < pivot) if(i === right) break
        // 从右找第一个 <= pivot 的位置（跳过所有 > pivot 的）
        while(arr[--j] > pivot) if(j === left) break
        if (i >= j) break
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
    // 关键：pivot 归位
    [arr[j], arr[left]] = [arr[left], arr[j]]
    return j
}

关键解释：为什么最后能交换 arr[left] 和 arr[j]？

当 i >= j 退出循环时：

  • j 指向的位置，其值一定 <= pivot（因为 j 停在「从右找到的第一个 <= pivot 的位置」或者原地不动）
  • 所以把 pivot和 arr[j] 交换后，arr[j] = pivot，左边全部 <= pivot，右边全部 >= pivot
  • pivot 被放到了它的最终排序位置

2.3 三向切分（3-Way Partitioning / Dijkstra）

当数据集中有大量的重复元素，标准快排会把等于 pivot 的元素分散到两边，造成不必要的递归。因此诞生了三向切分法，它的原理是将数组分为三部分：小于基准、等于基准、大于基准。等于 pivot 的元素全部集中在中间，不再参与递归。

使用三个指针维护四个区间

1
2
3
4
[left, lt-1]   <  pivot   （小于区）
[lt, i-1]      == pivot   （等于区）
[i, gt]        未扫描
[gt+1, right]  >  pivot   （大于区）
  • lt 指针：等于区起点 / 小于区右边界后一位。
  • gt 指针：未扫描区右边界 / 大于区左边界前一位。
  • i 指针：当前扫描位置。

步骤：

  1. 选 arr[left] 为 pivot

  2. 初始化：lt = left，i = left + 1，gt = right

  3. 当 i <= gt时循环：

    • arr[i] < pivot：交换 arr[lt] 和 arr[i]，lt++，i++（归入小于区，lt 和 i 同步右移）
    • arr[i] > pivot：交换 arr[i] 和 arr[gt]，gt--（归入大于区，gt 左移，但 i 不动（因为换过来的元素还没检查））
    • arr[i] == pivot：i++（直接归入等于区）

  4. 递归 [left, lt-1] 和 [gt+1, right]，跳过中间的等于区。

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
31
32
33
function quickSort3Way(arr, left = 0, right = arr.length - 1) {
    if (left >= right) return arr

    let lt = left      // lt 之前全是小于 pivot 的
    let gt = right     // gt 之后全是大于 pivot 的
    let i = left + 1   // 扫描指针
    let pivot = arr[left]

    while(i <= gt) {
        if (arr[i] < pivot) {
            // 情况 A：当前值小于基准
            // 归入小于区，lt 和 i 同步右移
            [arr[i], arr[lt]] = [arr[lt], arr[i]]
            lt++
            i++
        } else if (arr[i] > pivot) {
            // 情况 B：当前值大于基准
            // 归入大于区，gt 左移，但 i 不动（因为换过来的元素还没检查）
            [arr[i], arr[gt]] = [arr[gt], arr[i]]
            gt--
        } else {
            // 情况 C：当前值等于基准
            // 啥也不动，i 继续往前走，等于区自然变长
            i++
        }
    }

    // 此时：[left, lt-1] < pivot，[lt, gt] == pivot，[gt+1, right] > pivot
    // 只递归左右两部分，中间的等于区已经排好
    quickSort3Way(arr, left, lt - 1)
    quickSort3Way(arr, gt + 1, right)
    return arr
}

疑问：

Q1、为什么 arr[i] > pivot 时 i 不增加？

这是最容易出错的地方。当你把 arr[gt]（一个从未扫描过的元素）交换到 i 位置后，你不知道这个新元素比 pivot 大还是小，所以必须在下一轮循环中重新检查它。反之，当 arr[i] < pivot 时，换到 i 位置的数来自 lt，而 lt 指向的数一定等于 pivot（或者是 i 自己），因此 i 可以放心自增。

Q2、为什么 lt 和 gt 的初始值这样定？

我们默认把第一个元素 arr[left] 当作 pivot，所以等于区已经有一个成员（left 自己），因此扫描指针 i 从 left + 1 开始。循环结束后，lt 指向等于区的起始索引，gt 指向等于区的结束索引。

2.4 三种分区方法对比

方法 扫描方向 交换次数 重复元素处理 稳定性 适用场景
Lomuto 单向 较多 较差 不稳定 教学、简单实现
Hoare 双向 较少 一般 不稳定 通用场景
三向切分 双向 + 三指针 取决于数据 优秀 不稳定 大量重复元素

参考

  1. 【算法】经典排序算法总结-JavaScript描述-图解-复杂度分析-插入-快速-归并-堆排序等已经有很多排序算法的文章 - 掘金
  2. 通过动画可视化数据结构和算法 - VisuAlgo
  3. 各 AI：xiaomi mimo、Google gemini