经典的 Top K 问题有：最大（小） K 个数、前 K 个高频元素、第 K 个最大（小）元素
下面以求数组中的第 K 个最大元素为例，介绍 Top K 问题的解法
题目：
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素。
示例:
我们能想到的最简单的就是将数组进行排序（可以是最简单的快排），取前 K 个数就可以了，so easy
代码实现：
复杂度分析：
时间复杂度：O(nlogn)
空间复杂度：O(logn)
注意：
在 V8 引擎 7.0 版本之前，数组长度小于10时， 使用的是插入排序，否则用快速排序。
在 V8 引擎 7.0 版本之后就舍弃了快速排序，因为它不是稳定的排序算法，在最坏情况下，时间复杂度会降级到 O(n2)。
而是采用了一种混合排序的算法：TimSort 。
这种功能算法最初用于Python语言中，严格地说它不属于以上10种排序算法中的任何一种，属于一种混合排序算法：
在数据量小的子数组中使用插入排序，然后再使用归并排序将有序的子数组进行合并排序，时间复杂度为 。
题目仅仅需要求出数组中的第K个最大元素，没必要对数组整体进行排序
可以使用冒泡排序，每次将最大的数在最右边冒泡出来，只冒泡 k次即可
动图演示
代码实现
复杂度分析：
时间复杂度：最好时间复杂度 O(n)，平均时间复杂度 O(n*k)
空间复杂度：O(1)
我们也可以通过构造一个前 个最大元素小顶堆来解决，小顶堆上的任意节点值都必须小于等于其左右子节点值，即堆顶是最小值。
所以我们可以从数组中取出 个元素构造一个小顶堆，然后将其余元素与小顶堆对比，如果大于堆顶则替换堆顶，然后堆化，所有元素遍历完成后，堆中的堆顶即为第 个最大值
具体步骤如下：
从数组中取前 个数（ 到 位），构造一个小顶堆
从 位开始遍历数组，每一个数据都和小顶堆的堆顶元素进行比较，如果小于堆顶元素，则不做任何处理，继续遍历下一元素；如果大于堆顶元素，则将这个元素替换掉堆顶元素，然后再堆化成一个小顶堆。
遍历完成后，堆顶的数据就是第 K 大的数据
代码实现：
复杂度分析：
时间复杂度：遍历数组需要 O(n) 的时间复杂度，一次堆化需要 O(logk) 时间复杂度，所以利用堆求 Top k 问题的时间复杂度为 O(nlogk)
空间复杂度：O(k)
这种求 Top k 问题是可以使用排序来处理，但当我们需要在一个动态数组中求 Top k 元素怎么办喃？
动态数组可能会插入或删除元素，难道我们每次求 Top k 问题的时候都需要对数组进行重新排序吗？那每次的时间复杂度都为 O(nlogn)
这里就可以使用堆，我们可以维护一个 K 大小的小顶堆，当有数据被添加到数组中时，就将它与堆顶元素比较，如果比堆顶元素大，则将这个元素替换掉堆顶元素，然后再堆化成一个小顶堆；如果比堆顶元素小，则不做处理。这样，每次求 Top k 问题的时间复杂度仅为 O(logk)
更多堆内容可查看 前端进阶算法9：看完这篇，再也不怕堆排序、Top K、中位数问题面试了
无论是排序算法还是构造堆求解 Top k问题，我们都经过的一定量的不必要操作：
如果使用排序算法，我们仅仅想要的是第 k 个最大值，但是我们却对数组进行了整体或局部的排序
如果使用堆排序，需要维护一个大小为 的堆(大顶堆，小顶堆)，同时花费时间也很昂贵，时间复杂度为
那么有没有一种算法，不需要进行排序，也不需要花费额外的空间，就能获取第 K 个最大元素喃？
这就要说到快速选择算法了
快速选择（quickselect）算法与快排思路上相似，下面普及一下快排，已经了解的朋友可以跳过这一段
快排使用了分治策略的思想，所谓分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。
快排的过程简单的说只有三步：
首先从序列中选取一个数作为基准数
将比这个数大的数全部放到它的右边，把小于或者等于它的数全部放到它的左边 （一次快排 ）
然后分别对基准的左右两边重复以上的操作，直到数组完全排序
具体按以下步骤实现：
1，创建两个指针分别指向数组的最左端以及最右端
2，在数组中任意取出一个元素作为基准
3，左指针开始向右移动，遇到比基准大的停止
4，右指针开始向左移动，遇到比基准小的元素停止，交换左右指针所指向的元素
5，重复3，4，直到左指针超过右指针，此时，比基准小的值就都会放在基准的左边，比基准大的值会出现在基准的右边
6，然后分别对基准的左右两边重复以上的操作，直到数组完全排序
注意这里的基准该如何选择喃？最简单的一种做法是每次都是选择最左边的元素作为基准：
但这对几乎已经有序的序列来说，并不是最好的选择，它将会导致算法的最坏表现。还有一种做法，就是选择中间的数或通过 来随机选取一个数作为基准，下面的代码实现就是以随机数作为基准。
代码实现
快排是从小到大排序，所以第 个最大值在 位置上
复杂度分析
时间复杂度：O(nlogn)
空间复杂度：O(nlogn)
上面我们实现了快速排序来取第 k 个最大值，其实没必要那么麻烦，
我们仅仅需要在每执行一次快排的时候，比较基准值位置是否在 位置上，
如果小于 ，则第 k 个最大值在基准值的右边，我们只需递归快排基准值右边的子序列即可；
如果大于 ，则第 k 个最大值在基准值的做边，我们只需递归快排基准值左边的子序列即可；
如果等于 ，则第 k 个最大值就是基准值
代码实现：
复杂度分析：
时间复杂度：平均时间复杂度O(n)，最坏情况时间复杂度为O(n2)
空间复杂度：O(1)
又称为中位数的中位数算法，它的最坏时间复杂度为?O(n)?，它是由Blum、Floyd、Pratt、Rivest、Tarjan提出。该算法的思想是修改快速选择算法的主元选取方法，提高算法在最坏情况下的时间复杂度。
在BFPTR算法中，仅仅是改变了快速选择（quickselect）算法中 中的基准值的选取，在快速选择（quickselect）算法中，我们可以选择第一个元素或者最后一个元素作为基准元，优化的可以选择随机一个元素作为基准元，而在 BFPTR 算法中，每次选择五分中位数的中位数作为基准元（也称为主元pivot），这样做的目的就是使得划分比较合理，从而避免了最坏情况的发生。
如需转载，请注明文章出处和来源网址：http://www.divcss5.com/html/h62393.shtml
