package cn.enjoyedu.ch2.forkjoin.sort;

/**
 * 215. 数组中的第K个最大元素
 * 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [3,2,1,5,6,4] 和 k = 2
 * 输出: 5
 * 示例 2:
 * <p>
 * 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
 * 输出: 4
 * 说明:
 * <p>
 * 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
 */
public class QuickSort {

    //快排
    public static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int index = getIndex(arr, left, right);
            quickSort(arr, left, index);
            quickSort(arr, index + 1, right);
        }
    }

    public static int getIndex(int[] arr, int low, int hign) {
        int temp = arr[low];
        while (low < hign) {
            //每次都要判断low<hign
            while (low < hign && arr[hign] >= temp) {
                hign--;
            }

            arr[low] = arr[hign];
            while (low < hign && arr[low] <= temp) {
                low++;
            }
            arr[hign] = arr[low];

        }
        arr[low] = temp;
        return low;
    }

    public static int findKthLargest(int[] nums, int k) {
        quickSort(nums, 0, nums.length - 1);
        return nums[nums.length - k];
    }

    public static void main(String[] args) {
        System.out.println("============================================");
        long start = System.currentTimeMillis();

        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
//        int[] arr = MakeArray.makeArray();
//            quickSort(arr, 0, arr.length - 1);
        findKthLargest(arr, 2);
        System.out.println("排序后:");
        System.out.println(" spend time:" + (System.currentTimeMillis() - start) + "ms");
//            for (int i : arr) {
//                System.out.println(i);
//            }
    }
}