leetCode (js)：215. 数组中的第K个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

输入: [1] 和 k = 1
输出: 1

(假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度)

var findKthLargest = function(nums, k) {
    return quickSort(nums, k-1, 0, nums.length - 1);    
};

let quickSort = (arr, k, l, h) => {
    let low = l,
        high = h,
        pivot;

    if(h === 0) return arr[k]; // [1],1 => 1

    pivot = partition(arr, low, high);

    if(k>pivot){
      if(k==arr.length || (pivot + 1) == high) {
        return arr[k];
      }else{
        return quickSort(arr, k, pivot+1, high);
      }
    }
    if(k === pivot) return arr[k];
    if(k<pivot) return quickSort(arr, k,low,pivot-1);
};

let partition = (arr, low, high) => {
    for(let j = low; j <= high; j++) {
      if(arr[j] > arr[high]) {
        swap(arr, low, j);
        low++;
      }
    }
    swap(arr, low, high);
    return low;
};

let swap = (arr, low, high) => {
    let tmp = arr[low];
    arr[low] = arr[high];
    arr[high] = tmp;
};

利用快排分区的思想，这里if(arr[j] > arr[high])用排列出倒序数组后再去拿返回的low(pivot) 与 k-1 判断大小，若小于则在左侧，若大于则在右侧。
      其实还有更加简便的方法，如下：

var findKthLargest = function(nums, k) {
    return nums.sort((a, b) => b - a)[k-1];    
};

这样也是可以的，但是sort函数的具体实现原理我们就忽略掉了。其实V8引擎中实现sort函数的时候用到了插入排序和快排，当元素个数小于等于10的时候使用插入排序For short (length <= 10) arrays, insertion sort is used for efficiency.
源码地址：v8_Array.js