快速选择

用于求解 Kth Element 问题，也就是第 K 个元素的问题。

可以使用快速排序的 partition() 进行实现。需要先打乱数组，否则最坏情况下时间复杂度为 O(N2)。

堆

用于求解 TopK Elements 问题，也就是 K 个最小元素的问题。使用最小堆来实现 TopK 问题，最小堆使用大顶堆来实现，大顶堆的堆顶元素为当前堆的最大元素。实现过程：不断地往大顶堆中插入新元素，当堆中元素的数量大于 k 时，移除堆顶元素，也就是当前堆中最大的元素，剩下的元素都为当前添加过的元素中最小的 K 个元素。插入和移除堆顶元素的时间复杂度都为 log2N。

堆也可以用于求解 Kth Element 问题，得到了大小为 K 的最小堆之后，因为使用了大顶堆来实现，因此堆顶元素就是第 K 大的元素。

快速选择也可以求解 TopK Elements 问题，因为找到 Kth Element 之后，再遍历一次数组，所有小于等于 Kth Element 的元素都是 TopK Elements。

可以看到，快速选择和堆排序都可以求解 Kth Element 和 TopK Elements 问题。

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

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

题解

Topk问题（ JavaScript-Algorithms ），不过于三种方案：

排序，取第 k 个
构造前 k 个最大元素小顶堆，取堆顶
计数排序或桶排序，但它们都要求输入的数据必须是有确定范围的整数，所以本题不可用

那么除了这两种方案还有没有其它的方式可解决本题喃？其实还有两种：

快速选择（quickselect）算法
中位数的中位数（bfprt）算法

（1）首先，这是自己想的一种方法，看这道题的第一想法就是这个——利用js中数组的sort()方法，但是刚开始写的时候，就直接使用了sort函数，然后返回数组中第k大的数，也就是数组从前到后索引为数组长度减去k的数，然而，我忘记了一点，就是sort()函数的性质，sort()函数是会按照数字的字符串形式进行排序，也就是并不是真正意义上的数值排序，根据红宝书中写到的，如果利用sort()函数对数值进行排序，则需要在sort()函数中加入一个compare（）函数的参数，固定格式如下（降序则反之）。如我在网上查到的关于sort(compare)的真正含义，即此方法使用Array.sort(compareFunction和sortOptions)顺序的语法和参数，其参数定义如下： compareFunction - 用于确定数组元素排序顺序的比较函数。此参数是可选的。比较函数应该用于比较两个参数。给定元素的A和B，compareFunction的结果可以是负值，0或正值：如果返回值为负，则表示A在排序序列中出现在B之前。如果返回值为0，则A和B具有相同的排序顺序。如果返回值为正，则表示A在排序序列中出现在B之后。如以上内容不理解，则建议反复查看红宝书P149页。

var findKthLargest = function(nums, k) {
    let len  = nums.length
    let s = len - k
    nums = nums.sort(compare)     //红宝书149页
    return nums[s]

};
function compare(value1,value2){        //这个是放在sort里的函数
    if(value1<value2){                  
        return -1                       //表示降序
    }else if(value1>value2){            
        return 1                         //表示升序
    }else{
        return 0                         //相等
    }
}

简化一下可以这样。

var findKthLargest = function(nums, k) {
    let len  = nums.length
    let s = len - k
    nums = nums.sort((a,b) => a-b )       //a-b是升序，b-a是降序
    return nums[s]

};

复杂度分析：

时间复杂度：O(nlogn)
空间复杂度：O(logn) 目前还不知道这个是怎么算出来的，先背下来吧。

（2）构造前 k 个最大元素小顶堆，取堆顶

我们也可以通过构造一个前 k 个最大元素小顶堆来解决，小顶堆上的任意节点值都必须小于等于其左右子节点值，即堆顶是最小值。

所以我们可以从数组中取出 k 个元素构造一个小顶堆，然后将其余元素与小顶堆对比，如果大于堆顶则替换堆顶，然后堆化，所有元素遍历完成后，堆中的堆顶即为第 k 个最大值。

遍历数组需要 O(N) 的时间复杂度，一次堆化需要 O(logK) 时间复杂度，所以利用堆求 Top K 问题的时间复杂度为 O(NlogK)。

具体步骤如下：

从数组中取前 k 个数（ 0 到 k-1 位），构造一个小顶堆
从 k 位开始遍历数组，每一个数据都和小顶堆的堆顶元素进行比较，如果小于堆顶元素，则不做任何处理，继续遍历下一元素；如果大于堆顶元素，则将这个元素替换掉堆顶元素，然后再堆化成一个小顶堆。
遍历完成后，堆顶的数据就是第 K 大的数据

解析详情参考力扣大牛分析

let findKthLargest = function(nums, k) {
    // 从 nums 中取出前 k 个数，构建一个小顶堆
    let heap = [,], i = 0
    while(i < k) {
       heap.push(nums[i++]) 
    }
    buildHeap(heap, k)
    // 从 k 位开始遍历数组
    for(let i = k; i < nums.length; i++) {
        if(heap[1] < nums[i]) {
            // 替换并堆化
            heap[1] = nums[i]
            heapify(heap, k, 1)
        }
    }
    // 返回堆顶元素
    return heap[1]
};
// 原地建堆，从后往前，自上而下式建小顶堆
let buildHeap = (arr, k) => {
    if(k === 1) return
    // 从最后一个非叶子节点开始，自上而下式堆化
    for(let i = Math.floor(k/2); i>=1 ; i--) {
        heapify(arr, k, i)
    }
}
// 堆化
let heapify = (arr, k, i) => {
    // 自上而下式堆化
    while(true) {
        let minIndex = i
        if(2*i <= k && arr[2*i] < arr[i]) {
            minIndex = 2*i
        }
        if(2*i+1 <= k && arr[2*i+1] < arr[minIndex]) {
            minIndex = 2*i+1
        }
        if(minIndex !== i) {
            swap(arr, i, minIndex)
            i = minIndex
        } else {
            break
        }
    }
}
// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

(3)快速选择算法

每执行一次的时候，比较基准值位置是否在 n-k 位置上，如果小于 n-k ，则第 k 个最大值在基准值的右边，我们只需递归基准值右边的子序列即可；如果大于 n-k ，则第 k 个最大值在基准值的做边，我们只需递归基准值左边的子序列即可；如果等于 n-k ，则第 k 个最大值就是基准值。

let findKthLargest = function(nums, k) {
    return quickSelect(nums, nums.length - k)
};
let quickSelect = (arr, k) => {
  return quick(arr, 0 , arr.length - 1, k)
}
let quick = (arr, left, right, k) => {
  let index
  if(left < right) {
    // 划分数组
    index = partition(arr, left, right)
    // Top k
    if(k === index) {
        return arr[index]
    } else if(k < index) {
        // Top k 在左边
        return quick(arr, left, index-1, k)
    } else {
        // Top k 在右边
        return quick(arr, index+1, right, k)
    }
  }
  return arr[left]
}
let partition = (arr, left, right) => {
  // 取中间项为基准
  var datum = arr[Math.floor(Math.random() * (right - left + 1)) + left],
      i = left,
      j = right
  // 开始调整
  while(i < j) {
    // 左指针右移
    while(arr[i] < datum) {
      i++
    }
    // 右指针左移
    while(arr[j] > datum) {
      j--
    }
    // 交换
    if(i < j) swap(arr, i, j)
    // 当数组中存在重复数据时，即都为datum，但位置不同
    // 继续递增i，防止死循环
    if(arr[i] === arr[j] && i !== j) {
        i++
    }
  }
  return i
}
// 交换
let swap = (arr, i , j) => {
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}