分层，荷兰国旗，快排。

package class05;

import java.util.Arrays;

/**
 * 分层，荷兰国旗，快排。
 */
public class Code02_PartitionAndQuickSort {
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //分层
    //小于等于区，大于区。但是每个区内部并保证有序。
    public static int partition(int[] arr, int L, int R) {
        if (L > R) {
            return -1;
        }
        if (L == R) {
            return L;
        }
        int lessEqual = L - 1;//小于区的右边界
        int index = L;//当前数
        while (index < R) {//只要当前位置，和R位置，没有撞上，就一直循环。
            //如果当前数小于等于最后一个数
            //当前数和小于区的下一个数，交换。小于区右扩，当前数跳下一个。
            //而如果当前数大于最后一个数
            //当前数，直接跳下一个。
            if (arr[index] <= arr[R]) {
                swap(arr, index, ++lessEqual);
            }
            index++;
        }
        //当前数来到R位置时，将小于区的下一个数，和R位置的数，交换。
        swap(arr, ++lessEqual, R);
        return lessEqual;//返回小于区的右边界。
        //此时整个数组arr，就分成了两层。[0, lessEqual]是小于等于arr[R]的区域。[lessEqual, R]是大于arr[R]的区域。
    }

    //荷兰国旗问题
    public static int[] netherLandFlag(int[] arr, int L, int R) {
        if (L > R) {
            return new int[]{-1, -1};
        }
        if (L == R) {
            return new int[]{L, R};
        }
        int less = L - 1;//小于区的右边界
        int more = R;//大于区的左边界
        int index = L;//当前数的位置
        while (index < more) {//这里已经不是index<R了，而是index<more。即当index撞上more时，跳出循环。
            if (arr[index] < arr[R]) {//如果当前数小于最后一个数
                swap(arr, index++, ++less);//当前数和小于区的下一个数，交换。小于区右扩，当前数跳下一个。
            } else if (arr[index] == arr[R]) {//如果当前数等于最后一个数
                index++;//当前数直接跳下一个
            } else {//如果当前数大于最后一个数
                //当前数和大于区的左边一个数，交换。大于区左扩。
                //当前位置不变，因为当前这个数是后边换过来的，还没看呢，不能直接跳下一个。
                swap(arr, index, --more);
            }
        }
        //当前数和大于区的左边界撞上时，只有最后一个数还没有归位。
        //大于区的左边界和最后一个数，交换。
        swap(arr, more, R);
        //此时三层已经分层完毕。小于arr[R]区，等于arr[R]区，大于arr[R]区。
        return new int[]{less + 1, more};//返回等于arr[R]区的，左边界和右边界的索引位置。
    }

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

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

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

    private static void process2(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] equalArea = netherLandFlag(arr, L, R);//等于区，[equalArea[0], equalArea[1]]
        process2(arr, L, equalArea[0] - 1);
        process2(arr, equalArea[1] + 1, R);
    }

    //快排3.0
    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;
        }
//        swap(arr, (int) (Math.random() * (R - L + 1)), R);
//        int[] equalArea = netherLandFlag(arr, L, (int) (Math.random() * (R - L + 1)));
        //将固定以arr[R]为比较值，换成，将随机获取一个数作为比较值。
        //这样一来，提高了效率。
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
        int[] equalArea = netherLandFlag(arr, L, R);
        process3(arr, L, equalArea[0] - 1);
        process3(arr, equalArea[1] + 1, R);
    }

    // for test
    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
        }
        return arr;
    }

    // for test
    public static int[] copyArray(int[] arr) {
        if (arr == null) {
            return null;
        }
        int[] res = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    // for test
    public static boolean isEqual(int[] arr1, int[] arr2) {
        if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
            return false;
        }
        if (arr1 == null && arr2 == null) {
            return true;
        }
        if (arr1.length != arr2.length) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int testTime = 10;
        int maxSize = 20;
        int maxValue = 100;
        boolean flag = true;
        System.out.println("test start!");
        for (int i = 0; i < testTime; i++) {
            int[] arr0 = generateRandomArray(maxSize, maxValue);
            int[] arr1 = copyArray(arr0);
            int[] arr2 = copyArray(arr0);
            int[] arr3 = copyArray(arr0);
            int[] arr4 = copyArray(arr0);
            Arrays.sort(arr4);
            quickSort1(arr1);
            quickSort2(arr2);
            quickSort3(arr3);
            if (!isEqual(arr1, arr2) || !isEqual(arr1, arr3) || !isEqual(arr1, arr4)) {
                flag = false;
                break;
            }
        }
        System.out.println("test start!");
        System.out.println(flag ? "nice!" : "oops!");
    }
}