Q215 数组中第K大的元素

思路

可以用排序，但是不用全有序
还有个要求是O（n）

快排改版

快排只排需要的部分

public int findKthLargest(int[] nums, int k) {return quickSort(nums, 0, nums.length-1, nums.length-k);}public static int quickSort(int[] nums, int low, int high, int k){if (low<high){int pivot = partition(nums, low, high);if (pivot == k){return nums[pivot];}else if (pivot > k){return quickSort(nums, low, pivot-1, k);}else {return quickSort(nums, pivot+1, high, k);}}}public static int partition(int[] nums, int low, int high){int pivot = nums[high];while (low<high){while (low<high && nums[low] <= pivot){low++;}nums[high] = nums[low];while (low<high && nums[high] >= pivot){high--;}nums[low] = nums[high];}nums[low] = pivot;return low;}