一、荷兰国旗问题

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;    }