package cn.leo;

import java.util.Arrays;
import java.util.Random;

/**
 * @author : Jarry Leo
 * @date : 2019/1/17 14:12
 */
public class FindNum {

    public static void main(String[] args) {
        test();
    }

    private static void test() {
        long time1, time2;
        int[] ints;
        int length = 20000000; //生成的數(shù)組長度
        int[] nums = createArr(length, Integer.MAX_VALUE);
        int N = 50;
        System.out.println("查找" + length + "數(shù)組中第" + N + "大數(shù)字速度測試");

        ints = Arrays.copyOf(nums, length);
        time1 = System.currentTimeMillis();
        QuickSortDualPivot(ints, 0, ints.length - 1);
        time2 = System.currentTimeMillis();
        System.out.println("雙軸快速排序耗時(shí)：" + (time2 - time1) + "ms");
        System.out.println("答案是：" + ints[ints.length - N]);


        ints = Arrays.copyOf(nums, length);
        time1 = System.currentTimeMillis();
        int nMaxNum1 = findNMaxNum1(ints, N - 1);
        time2 = System.currentTimeMillis();
        System.out.println("快排原理查找第" + N + "大數(shù)字耗時(shí)：" + (time2 - time1) + "ms");
        System.out.println("答案是：" + nMaxNum1);

        ints = Arrays.copyOf(nums, length);
        time1 = System.currentTimeMillis();
        int nMaxNum2 = findNMaxNum2(ints, N);
        time2 = System.currentTimeMillis();
        System.out.println("小頂堆原理查找第" + N + "大數(shù)字耗時(shí)：" + (time2 - time1) + "ms");
        System.out.println("答案是：" + nMaxNum2);
    }


    //找出數(shù)組中第N大的數(shù)字1
    public static int findNMaxNum1(int[] arr, int N) {
        return quick(arr, 0, arr.length - 1, N);
    }

    //快排原理求第N大數(shù)字
    public static int quick(int[] arr, int left, int right, int N) {
        int l = left, r = right, p = arr[l];
        while (l < r) {
            while (l < r && arr[r] < p) {
                r--;
            }
            while (l < r && arr[l] >= p) {
                l++;
            }
            swap(arr, l, r);
        }
        swap(arr, left, r);
        if (r == N) {
            return arr[N];
        } else if (r > N) {
            return quick(arr, left, r - 1, N);
        } else {
            return quick(arr, r + 1, right, N);
        }
    }

    //找出數(shù)組中第N大的數(shù)字2
    public static int findNMaxNum2(int[] arr, int N) {
        return minHeap(arr, N);
    }

    //小頂堆求第N大數(shù)字
    public static int minHeap(int[] arr, int N) {
        //生成一個長度N的小頂堆
        int[] minHeap = Arrays.copyOf(arr, N);
        for (int i = (N - 1) / 2; i > 0; i--) {
            heapAdjust(minHeap);
        }
        for (int i = N + 1; i < arr.length; i++) {
            if (arr[i] > minHeap[0]) {
                minHeap[0] = arr[i];
                heapAdjust(minHeap);
            }
        }
        return minHeap[0];
    }

    //整堆
    private static void heapAdjust(int[] heap) {
        int p = 0, l, r, min, len = heap.length - 1;
        while ((l = p * 2 + 1) <= len) {
            min = l;
            r = l + 1;
            if (min < len && heap[l] > heap[r]) {
                min = r;
            }
            if (heap[p] > heap[min]) {
                swap(heap, p, min);
                p = min;
            } else {
                break;
            }
        }
    }


    //打印數(shù)組
    private static void print(int[] arr) {
        System.out.println(Arrays.toString(arr));
    }

    //生成隨機(jī)數(shù)組
    public static int[] createArr(int length, int bounds) {
        int[] arr = new int[length];
        Random random = new Random();
        for (int i = 0; i < length; i++) {
            arr[i] = random.nextInt(bounds);
        }
        return arr;
    }

    //交換數(shù)組索引ij的數(shù)值
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }


    //雙軸快排
    public static void QuickSortDualPivot(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        if (arr[left] > arr[right]) {
            swap(arr, left, right); //保證pivot1 <= pivot2
        }
        int pivot1 = arr[left];
        int pivot2 = arr[right];
        int i = left + 1;
        int k = left + 1;
        int j = right - 1;
        OUT_LOOP:
        while (k <= j) {
            if (arr[k] < pivot1) {
                swap(arr, i, k);
                k++;
                i++;
            } else if (arr[k] >= pivot1 && arr[k] <= pivot2) {
                k++;
            } else {
                while (arr[j] > pivot2) {
                    j--;
                    if (j < k) {//當(dāng)k和j錯過
                        break OUT_LOOP;
                    }
                }
                if (arr[j] >= pivot1 && arr[j] <= pivot2) {
                    swap(arr, k, j);
                    k++;
                    j--;
                } else {//arr[j] < pivot1
                    swap(arr, j, k);//注意k不動
                    j--;
                }
            }
        }
        i--;
        j++;
        swap(arr, left, i);//將pivot1交換到適當(dāng)位置
        swap(arr, right, j);//將pivot2交換到適當(dāng)位置
        //一次雙軸切分至少確定兩個元素的位置，這兩個元素將整個數(shù)組區(qū)間分成三份
        QuickSortDualPivot(arr, left, i - 1);
        QuickSortDualPivot(arr, i + 1, j - 1);
        QuickSortDualPivot(arr, j + 1, right);
    }

}