import java.util.Date;
import java.util.Random;

/**
 * Created by maopengyu on 2019/11/27.
 * 快排、双路快排、三路快排
 * 参考：https://a1049145827.github.io/2018/10/15/Swift-%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E3%80%81%E5%8F%8C%E8%B7%AF%E5%BF%AB%E6%8E%92%E5%92%8C%E4%B8%89%E8%B7%AF%E5%BF%AB%E6%8E%92/
 */
public class QuickSort {
    private Random random = new Random();
    private int[] quickSort3Arr = new int[2];

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

    /**
     * 普通快排，时间复杂度O(nlogn)，在数组有序或者重复元素较多时会退化到O(n2)
     * 当数组重复元素较多时，partition过程会将数组分成两个不平衡的部分（重复元素都在一边）
     * @param arr
     * @param start
     * @param end
     */
    public void quickSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = partition(arr, start, end);
        quickSort(arr, start, mid - 1);
        quickSort(arr, mid + 1 , end);
    }

    private int partition(int[] arr, int start, int end) {
        int r = start + random.nextInt(end - start + 1);
        swap(arr, r, start);
        int j = start;
        for (int i = start + 1; i <= end; i++) {
            if (arr[i] < arr[start]) {
                swap(arr, i, ++j);
            }
        }
        swap(arr, j, start);
        return j;
    }

    /**
     * 双路快排，优化重复元素多的情况，指针i和j从两端向中间逼近，
     * 将小于arr[mid]的值，放在左边；大于arr[mid]的值，放在右边，不会将重复元素放在一边，左右两变都可能包含相等的元素
     * @param arr
     * @param start
     * @param end
     */
    public void quickSort2(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = partition2(arr, start, end);
        quickSort(arr, start, mid - 1);
        quickSort(arr, mid + 1 , end);
    }

    private int partition2(int[] arr, int start, int end) {
        int r = start + random.nextInt(end - start + 1);
        swap(arr, r, start);
        int i = start + 1;
        int j = end;

        while (true) {
            // 这里不能arr[i] <= arr[start] 否则如果连续出现多个==的情况，则会把这些值归到一边
            while (i <= end && arr[i] < arr[start]) {
                i++;
            }
            // 这里不能arr[j] >= arr[start] 否则如果连续出现多个==的情况，则会把这些值归到一边
            while (j >= start + 1 && arr[j] > arr[start]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arr, i, j);
            i++;
            j--;
        }

        swap(arr, j, start);
        return j;
    }

    /**
     * 三路快排，将数据按arr[mid]分为，小于、等于、大于三个区域，
     * 递归时，只需处理小于和大于的区域，减少了一次处理的元素
     * @param arr
     * @param start
     * @param end
     */
    public void quickSort3(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int[] mid = partition3(arr, start, end);
        quickSort3(arr, start, mid[0]);
        quickSort3(arr, mid[1], end);
    }

    private int[] partition3(int[] arr, int start, int end) {
        int r = start + random.nextInt(end - start + 1);
        swap(arr, r, start);

        int lt = start; //arr[start+1, lt] < arr[start]
        int i = start + 1; //arr[lt+1, i] < arr[start]
        int gt = end + 1; //arr[gt, end] > arr[start]

        while (i < gt) {
            if (arr[i] < arr[start]) {
                swap(arr, i, lt + 1);
                i++;
                lt++;
            }else if (arr[i] > arr[start]) {
                swap(arr, i, gt - 1);
                gt--;
            }else {
                i++;
            }
        }
        swap(arr, lt, start);

        quickSort3Arr[0] = lt - 1;
        quickSort3Arr[1] = gt;

        return quickSort3Arr;
    }

    public static void main(String[] args) {
        Random random1 = new Random();
        int[] arr1 = new int[50000];
        int[] arr2 = new int[50000];
        int[] arr3 = new int[50000];
        for (int i = 0; i < 50000; i++) {
            int num = random1.nextInt(10);
            arr1[i] = num;
            arr2[i] = num;
            arr3[i] = num;
        }

        QuickSort quickSort = new QuickSort();

        Date start1 = new Date();
        quickSort.quickSort(arr1, 0, arr1.length - 1);
        Date end1 = new Date();
        System.out.println((end1.getTime() - start1.getTime()));
        StringBuilder sb1 = new StringBuilder();
        for (int i : arr1) {
            sb1.append(i);
        }

        Date start2 = new Date();
        quickSort.quickSort2(arr2, 0, arr3.length - 1);
        Date end2 = new Date();
        System.out.println((end2.getTime() - start2.getTime()));
        StringBuilder sb2 = new StringBuilder();
        for (int i : arr2) {
            sb2.append(i);
        }

        Date start3 = new Date();
        quickSort.quickSort3(arr3, 0, arr3.length - 1);
        Date end3 = new Date();
        System.out.println((end3.getTime() - start3.getTime()));
        StringBuilder sb3 = new StringBuilder();
        for (int i : arr3) {
            sb3.append(i);
        }

        if (sb1.toString().equals(sb2.toString()) && sb2.toString().equals(sb3.toString())) {
            System.out.println("true");
        }
        /**
         * 结果：
         * 108
         * 70
         * 7
         * true
         */
    }
}