← 返回首页

快速排序

TS 写一份原地快排，顺便解释 pivot 在左侧时为什么要从右开始遍历。

发布 2019年3月05日 标签 #algorithms #sorting

~/posts/quick-sort $ cat post.md

/ 语言 EN / 中文
/ 主题 / /

写快排的文章已经很多了，这篇只想把几个细节说清楚。

  • 快排的优势之一是可以原地排序，所以那些需要额外空间的”快排变体”基本就没必要用了。
  • 如果 pivot 从最左侧选取，那应该从最右侧开始遍历。
  • 快排不是稳定排序，重复元素的相对位置可能改变。

代码

下面是一个 TypeScript 写的原地快排：

const swap = <T>(arr: T[], left: number, right: number): void => {
    const temp: T = arr[left];
    arr[left] = arr[right];
    arr[right] = temp;
};

const quickSort = <T>(
    arr: T[],
    left: number = 0,
    right: number = arr.length - 1,
): void => {
    if (left > right) {
        return;
    }

    let lp: number = left;
    let rp: number = right;

    const pivot: T = arr[left]; // pivot 取最左

    while (lp != rp) {
        // 在两指针未相遇前，从右向左找下一个比 pivot 小的数
        while (lp < rp && arr[rp] >= pivot) {
            rp--;
        }
        // 在两指针未相遇前，从左向右找下一个比 pivot 大的数
        while (lp < rp && arr[lp] <= pivot) {
            lp++;
        }
        // 两个数交换：让较小的回到左侧
        if (lp < rp) {
            swap(arr, lp, rp);
        }
    }

    // 把 pivot 放到正确位置
    arr[left] = arr[lp];
    arr[lp] = pivot;

    // 递归处理左右两段
    quickSort(arr, left, lp - 1);
    quickSort(arr, lp + 1, right);
};

为什么”从右开始遍历”

举个简单的例子：9 10 5 7。

  1. 选最左侧的 pivot = 9。
  2. 从右向左找比 9 小的数：7。
  3. 从左向右找比 9 大的数：10，交换得 9 7 5 10。
  4. 从右向左找比 9 小的数：5。
  5. 从左向右找比 9 大的数——这时左指针追上了右指针 5，把 pivot 和当前指针位置交换得 5 7 9 10，完成。

关键在第 4 步：如果反过来从左侧开始遍历，左指针会停在 10 上；再去和 pivot 交换的话，pivot 会落到一个比它大的数的位置上，整个分区就破了。pivot 选最左 ⇒ 必须从右开始，反之亦然。

← 返回首页