大家好，我是周一。

最近几篇算法，我们都是聊的归并排序，归并排序也说的差不多了，今天讲讲快速排序。

一、荷兰国旗问题

1、啥是荷兰国旗问题

荷兰国旗是由红白蓝3种颜色的条纹拼接而成，如下图所示：

假设这样的条纹有多条，且各种颜色的数量不一，并且随机组成了一个新的图形，新的图形可能如下图所示，但不仅仅只有这一种情况：

需求是：把这些条纹按照颜色排好，红色的在上半部分，白色的在中间部分，蓝色的在下半部分，我们把这类问题称作荷兰国旗问题。

2、荷兰国旗问题的抽象

我们把荷兰国旗问题抽象成数组的形式是下面这样的：

给定一个整数数组和一个值M（存在于原数组中），要求把数组中小于M的元素放到数组的左边，等于M的元素放到数组的中间，大于M的元素放到数组的右边，最终返回一个整数数组，只有两个值，0位置是等于M的数组部分的左下标值、1位置是等于M的数组部分的右下标值。

进一步抽象为更加通用的形式是下面这样的：

给定数组arr，将[l, r]范围内的数（当然默认是 [ 0 - arr.length - 1 ]），小于arr[r]（这里直接取数组最右边的值进行比较）放到数组左边，等于arr[r]放到数组中间，大于arr[r]放到数组右边。最后返回等于arr[r]的左, 右下标值。

3、解决的思路

定义一个小于区，一个大于区；遍历数组，挨个和arr[r]比较，

（1）小于arr[r]，与小于区的后一个位置交换，当前位置后移；

（2）等于arr[r]，当前位置直接后移；

（3）大于arr[r]，与大于区的前一个位置交换，当前位置不动（交换到此位置的数还没比较过，所以不动）。

遍历完后，arr[r]和大于区的最左侧位置交换。

最后返回，此时小于区的后一个位置，大于区的位置，即是最后的等于arr[r]的左, 右下标值。

4、详细的参考代码

    /**
     * 荷兰国旗问题
     * <p>
     * 把数组arr中，[l, r]范围内的数，小于arr[r]放到数组最左边，等于arr[r]放到数组中间，大于arr[r]放到数组最右边
     *
     * @return 返回等于arr[r]的左, 右下标值
     */
    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, r};
        }
        // 小于arr[r]的右边界，从L的左边一位开始
        int less = l - 1;
        // 大于arr[r]的左边界，从r开始，即当前右边界里已经有arr[r]
        int more = r;
        // 当前正在比较的下标
        int index = l;
        // 不能与 大于arr[r]的左边界 撞上
        while (index < more) {
            if (arr[index] < arr[r]) {
                // 小于时，将当前位置的数和小于arr[r]的右边界的下一个位置交换
                // 当前位置后移一位
                swap(arr, index++, ++less);
            } else if (arr[index] == arr[r]) {
                // 等于时，当前位置后移一位即可
                index++;
            } else {
                // 大于时，当前位置的数和大于arr[r]的左边界的前一个位置交换
                // 当前位置不动
                swap(arr, index, --more);
            }
        }
        // 将arr[r]位置的数和大于arr[r]的左边界的数交换
        // 此时整个数组就按照 小于、等于、大于arr[r] 分成了左中右三块
        swap(arr, more, r);

        // 最后整个数组中，等于arr[r]的左右边界分别是less + 1, more
        return new int[]{less + 1, more};
    }

二、快速排序

1、啥是快排（排序流程）

首先设定一个分界值，通过该分界值将数组分成左中右三部分。

（1）将小于分界值的数据集中到数组的左边，等于分界值的数据集中到数组的中间，大于分界值的数据集中到数组右边。

（2）然后，左边和右边的数据可以独立排序。对于左侧的数据，又可以取一个分界值，将该部分数据分成左中右三部分，同样在左边放较小值，中间放等于值，右边放较大值。右边数据也做同样的处理。

（3）重复上述过程，可以看出，这是一个递归过程。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

当看完了快排的流程，是不是发现快排的核心方法就是荷兰国旗问题，所以知道为啥本文一开始就介绍荷兰国旗问题了吧。

2、抽象后的快排流程

（1）随机将数组中的某个数放到比较位置上（即最右侧位置）

（2）调用荷兰国旗方法，（此时等于区的数即在最后排好序的位置上），拿到等于区的左右下标

（3）小于区和大于区再各自递归调用（1）（2）步即可将小于区和大于区排好序。

3、详细的参考代码

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

    private static void processRandom(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        // 随机将数组中的某个数放到比较位置上（即数组最右边位置）
        // 这一步是保证快排时间复杂度是O(N*logN)的关键，不然，快排的时间复杂度是O(N^2)
        swap(arr, l + (int) ((r - l + 1) * Math.random()), r);
        // 将数组划分为 小于、等于、大于arr[r] 的左中右三块
        int[] equalArea = netherlandsFlag(arr, l, r);
        // 此时等于区域的值已经处于最后排序结果的位置了
        // 递归将左半部分的排好序
        processRandom(arr, l, equalArea[0] - 1);
        // 递归将右半部分的排好序
        processRandom(arr, equalArea[1] + 1, r);
    }

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

荷兰国旗问题

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边
要求额外空间复杂度O（1），时间复杂度O（N）

思路

使用两个指针来标记小于num部分和大于num部分
less指向小于num部分最后一位
more指向大于num部分的第一位
cur指向当前位置
分三种情况：
（1）当arr[cur] > num时，交换arr[cur] 和 arr[–more]，cur保持不变
（2）当arr[cur] < num时，交换arr[cur]和arr[++less]，cur++
（3）当arr[cur] = num时，cur++

代码

#include <bits/stdc++.h>
using namespace std;

inline void swap(int arr[], int i, int j);

int* partition(int arr[], int L, int R, int num){
    int less = L-1;
    int more = R+1;
    int cur = L;
    while(cur < more){
        if(arr[cur] > num){
            swap(arr, --more, cur);
        }else if (arr[cur] < num){
            swap(arr, ++less, cur++);
        }else{
            cur++;
        }
    }
    return new int [2] {less, more};
}

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

inline void outputArr(int arr[], int L, int R){
    for(int i = L; i <= R; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main(){
    int num;
    int arr[10] = {2,4,8,9,4,3,2,1,6,8};
    int *result;
    cin >> num;
    outputArr(partition(arr, 0, 9, num), 0, 1);
    outputArr(arr, 0, 9);
}

相关问题

荷兰国旗问题是实现快速排序的基本思想，对于理解快速排序有重要意义
快速排序的实现可以参考这篇文章：
随机快速排序

荷兰国旗问题

• 简化版荷兰国旗问题

给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。要求额外空间复杂度O(1)，时间复杂度O(N)。

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
void process(int *a[], int num)
{
    int i = 0;
    int p1 = -1;
    while (i < 8)
    {
        if (a[i] <= num)
        {
            swap(&a[i], &a[p1 + 1]);
            i++;
            p1++;
        }
        else
            i++;
    }
}

int main()
{
    int a[8] = {3, 5, 6, 7, 4, 3, 5, 8};
    int num = 5;
    process(&a, num);

    for (int i = 0; i < 8; i++)
        printf("%d", a[i]);

    return 0;
}

这里举的例子是3,5,6,7,4,3,5,8

这相当一个一个从左到右的推进。p1指向左，i指向待定区域的开始，然后i向右推进，碰到>num的不做处理，i++,如果碰到<=num的，将i指向的这个符合条件的元素和最靠近左区域的数，也就是中区域最左边的数交换，这样中区域最左边的数就符合<=num，然后i++，p++。

本质是左区域推着中区域向右，最终判断完所有的待定区域。

• 真荷兰国旗问题

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边，要求额外空间复杂度O(1)，时间复杂度O(N)。

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void process(int *a[], int flag)
{
    int i = 0;
    int p1 = -1;
    int p2 = 10;//这里直接赋了一个具体的数，本来用sizeof（a）来求，却有bug
    while (i < p2)//注意sizeof(a)在这里得到的并不是一个数组的长度，而是一个元素的长度。
    {
        if (a[i] < flag)
        {
            swap(&a[i], &a[p1 + 1]);
            p1++;
            i++;
        }
        else if (a[i] == flag)
        {
            i++;
        }
        else
        {
            swap(&a[i], &a[p2 - 1]);
            p2--;
        }
    }
}

int main()
{
    int a[10] = {3, 5, 6, 3, 4, 5, 2, 6, 9, 0};
    int flag = 5;
    process(&a, flag);
    for (int i = 0; i < 10; i++)
    {
        printf("%d,", a[i]);
    }

    return 0;
}

真正的荷兰国旗问题，多了右边向左的推进，同时注意，i只向右推进，因为i左边的数都被遍历过，所以对于<num可以进行i++，而>num再交换数之后，不能有i++，因为此时i指向的数是右边交换过来的新数，没有经过遍历，所以i不动。

荷兰国旗问题中的i变化，根据不同情况将数变动至<num和>num区域的思想能跟很好地契合进快排算法中去，具体内容见下一篇博客。

感谢你能看到这里，祝好。