多图养眼！Partition，荷兰国旗问题与随机快排

行百里er

发布于 2020-12-02 15:06:40

5900

发布于 2020-12-02 15:06:40

文章被收录于专栏：JavaJourney

快速排序的思想是通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归方式实现，以此达到整个数据变成有序序列。

在实现快速排序之前，先了解：

Partition
荷兰国旗问题

这两个问题，将有助于我们实现快速排序算法。

Partition

Partition的过程：给定一个数组arr，和一个整数num。把小于等于num的数放在数组的左边，大于num的数放在数组的右边。

比如数组int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};

给定一个数15，小于等于15的数放在数组的左边，大于15的数放在数组的右边。

分析Partition过程：

分支1：arr[i] <= 15，arr[i]和小于等于区的右边一个元素交换，同时小于等于区向右扩展1个，i++

分支2：arr[i] > 15，不做操作，只是i++

初始化i、小于等于区：

i初始值为0；
小于等于区右边界为-1；

数组初始状态：

i=0，比较arr[0]和15,arr[0] > 15，走分支2，没有操作，只是i++：

执行i++后i=1

i=1，比较arr[1]和15,arr[1] == 15，走分支1，将arr[1]和arr[0]（就是arr[smaller+1]）交换，小于等于区的右边界右移，同时i++：

执行i++后i=2

i=2，比较arr[2]和15,arr[1] < 15，走分支1，将arr[2]和arr[1]（就是arr[smaller+1]）交换，小于等于区的右边界右移，同时i++：

执行i++后i=3

i=3，比较arr[3]和15,arr[2] > 15，走分支2，不做操作，只是i++：

执行i++后i=4

i=4，比较arr[4]和15,arr[4] < 15，走分支1，将arr[4]和arr[2]（就是arr[smaller+1]）交换，小于等于区的右边界右移，同时i++：

执行i++后i=5

i=5，比较arr[5]和15,arr[5] > 15，走分支2，不做操作，只是i++：

执行i++后i=6

i=6，比较arr[6]和15,arr[6] == 15，走分支1，将arr[6]和arr[3]（就是arr[smaller+1]）交换，小于区的右边界右移，同时i++：

执行i++后i=7

i=7，比较arr[7]和15,arr[5] < 15，走分支1，将arr[7]和arr[4]（就是arr[bigger-1]）交换，小于区的右边界右移，同时i++：

执行i++后i=7，越界不继续了

此时，i越界，所有小于等于给定数15的元素都在数组的左边，大于15的元素都在数组的右边，完成了划分。

代码实现：

/**
 * Partition：给数组指定范围进行分区，小于等于arr[R]的放左边，大于arr[R]的放右边
 * @param arr 数组
 * @param L 划分数组范围的左边界
 * @param R 划分数组范围的右边界
 * @return int 返回小于等于区域的右边界
 **/
public static int partition(int[] arr, int L, int R) {
    if (L > R) {
        return -1;
    }
    if (L == R) {
        return L;
    }
    //定义小于等于区的右边界
    int smallAndEq = L - 1;
    int index = L;
    while (index < R) {
        if (arr[index] <= arr[R]) {
            swap(arr, index, ++smallAndEq);
        }
        index++;
    }
    swap(arr, ++smallAndEq, R);
    return smallAndEq;
}

荷兰国旗问题

荷兰国旗问题：给定一个数组arr，和一个整数num。把小于num的数放在数组的左边，等于num的数放在中间，大于num的数放在数组的右边。

荷兰国旗

类比于荷兰国旗中的红白蓝三个区域，因此这种数组划分叫荷兰国旗问题。

解决这类问题，分析其过程如下：

给定一个数15，小于等于15的数放在数组的左边，大于15的数放在数组的右边

分支1：arr[i] < 15，arr[i]和小于区的右边一个元素交换，同时小于区向右扩展1个，i++

分支2：arr[i] == 15，i++

分支3：arr[i] > 15，arr[i]和大于区的左边一个元素交换，同时大于区向左扩展1个，i不变（因为此时arr[i]还未和交换过来的数据进行比较）

初始化i、小于区和大于区：

i初始值为0；
小于区右边界初始值为-1；
大于区左边界初始值为arr.length

初始状态：

i=0，比较arr[0]和15,arr[0] > 15，走分支3，将arr[0]和arr[7]（arr[bigger-1]）交换，大于区的左边界左移：

大于区的左边界左移，bigger-1后为7

i仍然=0，比较arr[0]和15,arr[0] < 15，走分支1，将arr[0]和arr[0]（就是arr[smaller+1]）交换（等于不动），小于等于区的右边界右移，同时i++：

小于区右边界右移，i和smaller均+1

i=1，比较arr[1]和15,arr[1]==15，走分支2，不做操作，只是i++：

只做i++后i为2

i=2，比较arr[2]和15,arr[2] < 15，走分支1，将arr[2]和arr[1]（就是arr[smaller+1]）交换，小于等于区的右边界右移，同时i++：

小于区右边界右移，i和smaller均+1

i=3，比较arr[3]和15,arr[3] > 15，走分支3，将arr[3]和arr[6]（就是arr[bigger-1]）交换，大于区的左边界左移：

大于区的左边界左移，bigger-1后为6

i仍然=3，比较arr[3]和15,arr[3] == 15，走分支2，i++：

只做i++后i为4

i=4，比较arr[4]和15,arr[4] < 15，走分支1，将arr[4]和arr[2]（就是arr[smaller+1]）交换，小于区的右边界右移，同时i++：

小于区右边界右移，i和smaller均+1，i为5

i=5，比较arr[5]和15,arr[5] > 15，走分支3，将arr[5]和arr[5]（就是arr[bigger-1]）交换，大于区的左边界左移：

大于区的左边界左移，bigger-1后为5

此时i==bigger了，荷兰国旗完成，停止循环。

代码实现：

为了更具有普遍性，荷兰国旗问题定义为：让一个数组的L ~ R位置上，另小于等于arr[R]的元素放在数组左边，等于arr[R]的元素放在中间，大于arr[R]的元素放在数组右边。

/**
 * 荷兰国旗问题：给数组指定范围进行分区，小于arr[R]的放左边，大于arr[R]的放右边，中间是等于arr[R]的
 * @param arr 数组
 * @param L 待划分数组范围的左边界
 * @param R 到划分数组范围的右边界
 * @return int[] 返回相等区域的左右边界索引
 **/
public static int[] hollandFlag(int[] arr, int L, int R) {
    if (L > R) {
        return new int[] {-1, -1};
    }
    if (L == R) {
        return new int[] {L, R};
    }
    int smaller = L - 1;
    int bigger = R;
    int index = L;

    while (index < bigger) {
        //System.out.println("index:" + index + ",smaller:" + smaller + ",bigger:" + bigger + ",arr[index]:" + arr[index] + ",arr[R]:" + arr[R]);
        //分支1，arr[index] < arr[R]
        if (arr[index] < arr[R]) {
            swap(arr, index++, ++smaller);
        }
        //分支2，arr[index] == arr[R]
        else if (arr[index] == arr[R]) {
            index++;
        }
        //分支3，arr[index] > arr[R]
        else {
            swap(arr, index, --bigger);
        }
        //System.out.println(Arrays.toString(arr));
    }
    //要把R位置上的数放到大于区的第一个位置
    swap(arr, bigger, R);
    return new int[] {smaller + 1, bigger};
}

快速排序算法

快速排序也是采用分治思想实现，基于前面Partition和荷兰国旗问题的解决方案，我们把排序过程划分成很多小的规模，每个规模都调用Partition或者荷兰国旗问题来解决就可以完成排序了。

快排V1：使用Partition

在arr[L..R]范围上，进行快速排序的过程：

1）用arr[R]对该范围做partition，<= arr[R]的数在左部分并且保证arr[R]最后来到左部分的最后一个位置，记为M；<= arr[R]的数在右部分（arr[M+1..R]）

2）对arr[L..M-1]进行快速排序(递归)

3）对arr[M+1..R]进行快速排序(递归)

因为每一次Partition都会搞定一个数的位置且不会再变动，所以排序能完成。

/**
 * 快速排序v1 用Partition方法
 **/
public static void quickSortV1(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    processV1(arr, 0, arr.length - 1);
}

public static void processV1(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int M = partition(arr, L, R);
    processV1(arr, L, M - 1);
    processV1(arr, M + 1, R);
}

快排V2：使用解决荷兰国旗问题的方案

在arr[L..R]范围上，进行快速排序的过程：

1）用arr[R]对该范围做partition，< arr[R]的数在左部分，== arr[R]的数中间，>arr[R]的数在右部分。假设== arr[R]的数所在范围是[a,b]

2）对arr[L..a-1]进行快速排序(递归)

3）对arr[b+1..R]进行快速排序(递归)

因为每一次Partition都会搞定一批数的位置且不会再变动，所以排序能完成。

/**
 * 快速排序V2 升级版Partition-荷兰国旗问题解决方案
 **/
public static void quickSortV2(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    processV2(arr, 0, arr.length - 1);
}

public static void processV2(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    int[] equalArea = hollandFlag(arr, L, R);
    processV2(arr, L, equalArea[0] - 1);
    processV2(arr, equalArea[1] + 1, R);
}

快排V3：随机快排+荷兰国旗技巧优化

前两个版本的时间复杂度，数组已经排好序的情况下，复杂度均为O（N²），性能不太好，还有更好的解决方案。

在arr[L..R]范围上，进行快速排序的过程：

1）在这个范围上，随机选一个数记为num

2）用num对该范围做Partition，< num的数在左部分，== num的数中间，>num的数在右部分。假设== num的数所在范围是[a,b]

3）对arr[L..a-1]进行快速排序(递归)

4）对arr[b+1..R]进行快速排序(递归)

因为每一次Partition都会搞定一批数的位置且不会再变动，所以排序能完成。

变化点就是在数组中选一个随机数作为比较对象，然后进行Partition。

/**
 * 快速排序V3 随机快排+荷兰国旗技巧优化
 **/
public static void quickSortV3(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    processV3(arr, 0, arr.length - 1);
}

public static void processV3(int[] arr, int L, int R) {
    if (L >= R) {
        return;
    }
    //优化点：选一个随机位置的数进行Partition
    swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
    int[] equalArea = hollandFlag(arr, L, R);
    processV3(arr, L, equalArea[0] - 1);
    processV3(arr, equalArea[1] + 1, R);
}

时间复杂度（结论）：

1）随机选的数越靠近中间，性能越好；越靠近两边，性能越差

2）随机选一个数进行划分的目的就是让好情况和差情况都变成概率事件

3）把每一种情况都列出来，会有每种情况下的时间复杂度，但概率都是1/N

4）那么所有情况都考虑，时间复杂度就是这种概率模型下的长期期望！

时间复杂度O(N*logN)，额外空间复杂度O(logN)都是这么来的。