分区函数和快排(快排分为递归和非递归两个版本)

package class08;

import java.util.Arrays;
import java.util.Stack;

/**
 * 分区函数和快排。
 * 快排分为递归和非递归两个版本。
 */
public class Code03_PartitionAndQuickSort {
    /**
     * 分区。结果是分为两个区域，小于等于区(不保证有序)，和大于区(不保证有序)。
     * 以数组arr的最后一个数为基准数，将小于等于它的数，归为小于等于区。大于它的数，归于大于区。
     *
     * @param arr 需要被分区的数组
     */
    public static void splitNum1(int[] arr) {
        //分区函数的默认的前提条件是，数组的最后一个数为基准数。(即arr[N - 1]为基准数)
        int lessEqualsR = -1;//小于等于基准数，区域的最右位置的索引。
        int index = 0;//当前数的索引。即当前要判断的数，判断它是小于等于基准数，还是大于基准数。
        int N = arr.length;
//        while (index < N - 1) {//这个是不对的。
        //index是索引，N是数组的个数，所以，当index=6时，N等于7时，就是数组的最后一个数，和自己比较大小。
        //那么(arr[index] <= arr[N - 1])的结果是true。所以会有一个交换的操作。把基准数换到它该在的位置。
        while (index < N) {//只要当前数的索引(指针)，小于数组长度。
            if (arr[index] <= arr[N - 1]) {//1.如果当前数小于等于基准数。
                swap(arr, ++lessEqualsR, index++);//将小于等于区的再右边一个数，和当前数，交换。指针index往后跳一步，即index++。
                //上边这一句顶下边这三句。
                //swap(arr, lessEqualsR + 1, index);//将小于等于区的再右边一个数，和当前数，交换。
                //lessEqualsR++;//小于等于区，右扩一个位置。
                //index++;//指针index跳一步。
            } else {//2.如果当前数大于基准数。
                index++;//指针index直接++。不做交换操作，小于等于区，也不右扩。
            }
            printArr(arr);
        }
    }

    /**
     * 分区。结果是分为三个区域，小于区(不保证有序)，等于区(都是等于基准数的，所有可以归为有序)，和大于区(不保证有序)。
     *
     * @param arr 需要被分区的数组
     */
    public static void splitNum2(int[] arr) {
        int lessR = -1;//小于区的最右位置的索引。
        int N = arr.length;
        int moreL = N - 1;//大于区的最左位置的索引。
        int index = 0;//当前数的索引。将要对当前数做判断，判断它是小于基准数，还是等于，还是大于。
        while (index < moreL) {//只要当前数的索引，小于大于区的最右位置的索引。
            if (arr[index] < arr[N - 1]) {//1.如果当前数小于基准数。
                swap(arr, ++lessR, index++);//小于区的再右边一个数，和当前数，交换。(小于区右扩一个位置)。当前数跳一步(index++)。
            } else if (arr[index] > arr[N - 1]) {//2.如果当前数大于基准数。
                //大于区的再左边一个数，和当前数，交换。(大于区左扩一个位置)。当前数保持位置不变。
                //因为交换后的当前数，是一个新数，还没判断呢。所有index不能往后跳一步。
                swap(arr, --moreL, index);
            } else {//3.当前数大于基准数。
                index++;//index直接跳一步。不做交换操作。小于区不右扩，大于区也不左扩。
            }
        }
        //跳出循环后，记得：交换数组的最后一个数和大于区的最左位置的数。
        //因为最后一个数就是基准数本身，并不大于基准数。它只是一直"潜伏"在大于区内部。
        //所以在调整完小于区，等于区，和大于区后，最后记得将最后一个数，放在它该在的位置，即等于区的最后位。也就是moreL索引位置。
        swap(arr, N - 1, moreL);
    }

    //part2
    //快排(1.递归版本)
    public static void quickSort1(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        process(arr, 0, arr.length - 1);
    }

    //使arr在L到R上，有序。
    public static void process(int[] arr, int L, int R) {
        if (L >= R) {
            return;
        }
        int[] equalsArea = partition(arr, L, R);
        process(arr, L, equalsArea[0] - 1);//equalsArea[0]：等于区域的第一个数的索引。
        process(arr, equalsArea[1] + 1, R);//equalsArea[1]：等于区域的最后一个数的索引。
    }

    /**
     * 在arr[L...R]范围上，将arr[R]作为基准数。划分出小于区，等于区，和大于区。
     *
     * @param arr 要被分区的数组
     * @param L   arr的最左索引
     * @param R   arr的最右索引
     * @return 一个只有两个元素的数组。
     * 第一个数代表：等于区域的第一个数的索引。
     * 第二个数代表：等于区域的最后一个数的索引。
     */
    public static int[] partition(int[] arr, int L, int R) {
        int lessR = L - 1;//当L等于0时，lessR等于-1，所以抽象后后，lessR等于L-1。
        int moreL = R;//当R等于N-1时，moreL等于N-1，所以抽象化后，moreL等于R。
        int index = L;//当L等于0时，index等于0，所以抽象化后，index等于L。
        while (index < moreL) {//当R等于N-1时，index<N-1，所以抽象化后，index<moreL。
            if (arr[index] < arr[R]) {//原来是：arr[index] < arr[N-1]。基准数的索引，永远是[L...R]范围上的R。
                swap(arr, ++lessR, index++);
            } else if (arr[index] > arr[R]) {//原来是：arr[index] > arr[N-1]。基准数的索引，永远是[L...R]范围上的R。
                swap(arr, --moreL, index);
            } else {
                index++;
            }
        }
        swap(arr, moreL, R);//记得将[L...R]范围上，最后索引位置的数，放在它该在的位置上。也就是归位。
        //等于区域的最左数的索引是，小于区域的最右数的索引，再+1。
        //等于区域的最右数的索引是，大于区域的最左数的索引。没有-1。因为arr[N-1]和arr[moreL]交换了，所以moreL就是等于区域的最右数的索引。
        return new int[]{lessR + 1, moreL};
    }

    //part3
    //2.快排(非递归版本)
    public static void quickSort2(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        Stack<Job> stack = new Stack<>();//定义一个栈，用来存放任务。
        stack.push(new Job(0, arr.length - 1));//先往任务栈里添加一个任务：在[0,N-1]上排序。
        while (!stack.empty()) {//只要任务栈不是空的，就继续。
            Job cur = stack.pop();//弹出一个任务，记为当前任务。
            int[] equalsArea = partition(arr, cur.L, cur.R);//将当前任务的左边界，和右边界，作为参数，调用分区函数partition()。返回一个等于区。
            if (equalsArea[0] > cur.L) {//当等于区的第一个元素，大于当前任务的左边界，才有小于区域。
                stack.push(new Job(cur.L, equalsArea[0] - 1));//向任务栈中添加一个任务，范围是，当前任务的左边界，和等于区的第一个数的索引的，前一个位置。
            }
            if (equalsArea[1] < cur.R) {//当等于区的第二个元素，小于当前任务的有边界，才有大于区域。
                stack.push(new Job(equalsArea[1] + 1, cur.R));//向任务栈中添加一个任务，范围是，等于区的最后一个数的索引的，后一个位置，和当前任务的右边界。
            }
        }
    }

    /**
     * 自定义任务类，在[L,R]山排序。
     * 比如：最大的任务就是将数组arr，在0到arr.length-1范围上，排序。
     * new Job(0, arr.length - 1);
     * 属性L：当前任务的左边界
     * 属性R：当前任务的右边界
     */
    public static class Job {
        public int L;
        public int R;

        public Job(int left, int right) {
            L = left;
            R = right;
        }
    }

    //交换数组arr中i和j索引位置的两个数
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //打印数组
    public static void printArr(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    //生成随机数组
    public static int[] generateRandomArr(int maxValue, int maxSize) {
        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;
    }

    //复制数组
    public static int[] copyArr(int[] arr) {
        int[] arr2 = new int[arr.length];
        for (int i = 0; i < arr.length; i++) {
            arr2[i] = arr[i];
        }
        return arr2;
    }

    //判断两个数组是否相等
    public static boolean isEquals(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[] arr = {5, 1, 3, 2, 4, 6, 5, 8, 7, 9, 3, 5};
//        printArr(arr);
//        splitNum1(arr);
////        splitNum2(arr);
//        printArr(arr);

        int testTimes = 100000;
        int maxValue = 10000;
        int maxSize = 100;
        boolean flag = true;
        System.out.println("test start!");
        for (int i = 0; i < testTimes; i++) {
            int[] arr0 = generateRandomArr(maxValue, maxSize);
            int[] arr1 = copyArr(arr0);
            int[] arr2 = copyArr(arr0);
            quickSort1(arr1);
            quickSort2(arr2);//快排，非递归。
            Arrays.sort(arr0);
            if (!isEquals(arr0, arr1) || !isEquals(arr0, arr2)) {
                System.out.println("Oops1!");
                flag = false;
                break;
            }
        }
        System.out.println("test end!");
        System.out.println(flag ? "Nice!" : "Oops2!");
    }
}