快速排序与荷兰国旗问题

1. 荷兰国旗问题

想象一下，你有一堆红色、白色、蓝色的珠子混在一起，需要将它们按照荷兰国旗的颜色顺序（红、白、蓝）排列好。这就是荷兰国旗问题的原型。

在编程中，我们可以将这个问题抽象为：给定一个整数数组 arr 和一个数 num，请把小于 num 的数放在数组的左边，等于 num 的数放在中间，大于 num 的数放在右边。

这个问题其实就是快速排序算法最核心的分区操作。让我们先从一个简化版的问题开始。

通过这个问题和快速排序，我们还能进一步理解分而治之的递归思想

1.1 两分区版

我们先不管“等于”区域，只要求将数组分为两部分：小于等于 num 的数 和 大于 num 的数。

在我们的代码中，为了方便，我们通常选取数组某个范围（例如 [L, R]）内的最后一个元素 arr[R] 作为我们的 num。

思路很简单：

我们设定一个“小于等于区域”的右边界 border，初始时在 L-1 的位置。
我们用一个指针 cur 从 L 开始遍历数组，直到 R（num 所在的位置）。
当 cur 遍历到 arr[cur]：
- 如果 arr[cur] <= num，说明它属于“小于等于区域”。我们把它和 border 的下一个元素交换，然后将 border 右移一位。
- 如果 arr[cur] > num，它天然就应该在右边，我们什么都不做，继续考察下一个数。
遍历结束后，border 右边的所有数都大于 num，border 及左边的数都小于等于 num（除了我们一开始选定的 arr[R]）。最后，我们将 arr[R] 和 border 的下一个位置交换，就把它放到了分界线上。

这个 border 的最终位置，就是我们划分后两个区域的分界点。

java

public static int partitionBase(int[] arr, int l, int r) {
    if (l > r) {
        return -1;
    }
    if (l == r) {
        return l;
    }

    int border = l - 1;
    int cur = l;
    while (cur < r) {
        if (arr[cur] <= arr[r]) {
            swap(arr, border + 1, cur);
            border++;
        }
        cur++;
    }
    swap(arr, ++border, r);

    return border;
}

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

1.2 三分区版

现在，我们回到完整版的荷兰国旗问题：划分出 小于、等于、大于 三个区域。

这次我们需要两个边界：

小于区的右边界 bl (less border)，初始为 L-1。
大于区的左边界 br (right border)，初始为 R（我们同样用 arr[R] 作为 num，所以它暂时不属于大于区）。
一个指针 cur 从 L 开始遍历，直到与 br 相遇。

遍历逻辑如下：

如果 arr[cur] < num：它属于小于区。将其与 bl 的下一个元素交换，然后 bl 和 cur 都向右移动。
如果 arr[cur] == num：它就待在原地，属于等于区。cur 直接向右移动。
如果 arr[cur] > num：它属于大于区。将其与 br 的前一个元素交换，然后 br 向左移动。注意：此时 cur 不动！ 因为从右边换过来的那个数我们还没有处理过，需要下一轮循环来判断它的大小。

循环结束后，bl 和 br 之间就是等于 num 的区域。我们再将 arr[R] (也就是 num) 与 br 所在位置的元素交换，就完成了标准的三色分区。最后返回等于区域的左右边界。

java

public static int[] netherlandsFlag(int[] arr, int l, int r) {
    if (l > r) {
        return new int[] {-1, -1};
    }
    if (l == r) {
        return new int[] {l, l};
    }

    int bl = l - 1;
    int br = r;
    int cur = l;

    while (cur < br) {
        if (arr[cur] < arr[r]) {
            swap(arr, ++bl, cur++);
        } else if (arr[cur] == arr[r]) {
            cur++;
        } else {
            swap(arr, --br, cur);
        }
    }
    swap(arr, br, r);

    return new int[] {bl + 1, br};
}

2. 快速排序 QuickSort

理解了分区（Partition），快速排序就水到渠成了。它的核心思想是分而治之：

在数组中选择一个元素作为 “主元”（Pivot）。
分区：重新排列数组，所有比主元小的元素都移动到主元前面，所有比主元大的元素都移动到主元后面。在这个分区结束后，主元就位于数组的最终排序位置。
递归：对主元前、后的两个子数组，递归地执行上述过程。

2.1 基础快速排序

用两分区版来构建，递归深度达到 O(N)，总的时间复杂度到 O(N²)。

将左边排好序（小于区），将右边排好序（大于区）

由于数组左右本就有序，那么排序就完成了

java

public static void quickSort1(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process1(arr, 0, arr.length - 1);
}

// 函数作用：将数组[l,r]范围上用快速排序排好序
public static void process1(int[] arr, int l, int r) {
    if (l >= r) {
        return;
    }
    int bdr = partitionBase(arr, l, r);
    process1(arr, l, bdr - 1);		// 将左边排好序（小于区）
    process1(arr, bdr + 1, r);		// 将右边排好序（大于区）
}

2.2 优化快速排序

我们可以使用三区分版的函数来优化。它返回的是等于区域的左右边界 [el, er]。

这意味着，在一次分区后，[el, er] 范围内的所有数都已经找到了它们最终的位置，我们无需再处理它们！我们只需要递归处理小于区 [L, el-1] 和大于区 [er+1, R] 即可。

这对于包含大量重复元素的数组来说，是一个巨大的性能提升。

java

public static void quickSort2(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process2(arr, 0, arr.length - 1);
}

public static void process2(int[] arr, int l, int r) {
    if (l >= r) {
        return;
    }
    int[] bdr = netherlandsFlag(arr, l, r);
    process2(arr, l, bdr[0] - 1);
    process2(arr, bdr[1] + 1, r);
}

版本2虽然更优，但它解决 O(N²) 的问题了吗？并没有。

2.3 终极快速排序

问题的根源在于我们 可预见地 选择了 “坏” 的主元。如何打破这种可预见性？答案是：随机！

在每次分区前，我们不再固定地选择 arr[R]，而是在 [L, R] 范围内随机选择一个数，然后把它与 arr[R] 交换。这样一来，后续的分区逻辑完全不变，但我们选到“坏”主元的概率变得极小。

从数学期望上讲，每次分区都会以很高的概率将数组划分成规模大致相等的两部分，使得递归树的高度保持在 O(logN) 的水平，从而保证了 O(N*logN) 的时间复杂度。

这只需要在2.2的基础上加上一句随机即可

java

public static void quickSort3(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    process3(arr, 0, arr.length - 1);
}

public static void process3(int[] arr, int l, int r) {
    if (l >= r) {
        return;
    }
    int ram = l + (int) (Math.random() * (r - l + 1));
    swap(arr, ram, r);
    int[] bdr = netherlandsFlag(arr, l, r);
    process3(arr, l, bdr[0] - 1);
    process3(arr, bdr[1] + 1, r);
}