https://zhuanlan.zhihu.com/p/64627590

一个无序数组的第K大的元素

一个比较简单的想法是先快速排序排好，然后直接拿第k个就好。提醒一下这样的时间复杂度是 $O(n * log(n))$，空间复杂度是 $O(log n)$

如果用一个大小为 k 的**Min-Heap，**从头开始遍历数组，扫描到值若大于堆顶则入队，然后删除堆顶。它的时间复杂度是 $O(Nlogk)$ ，空间复杂度是 $O(k)$

其实上面的算法都额外计算了一些不需要的东西，接下来介绍的东西只会得到Top K 的值，其他什么都不会得到。现在先冷静地想一下原来的算法究竟干了什么事情

[1, 2, 3, 4, 5, 6]
             ↑
           n - k

对于一个有序的数组，Top k即是第$n-k$个元素。我们甚至不需要一个排序的数组，只要 n - k 的左边是小于 nums[n-k] 的值，n - k 的右边是大于 nums[n-k] 的值，那么 n - k 就是我们要找的 Top k。

快速选择算法流程

随机选择一个 pivot，通过一系列计算，查看是否是我们需要找到的 Top k 对应的 pivot

把 pivot 移动到最右的位置，已最右为标杆，从头开始对剩余部分进行选择查找

定义两个指针，查看 j 所在的指针是否小于等于 pivot，4 大于 3，所以我们把 j 指针右移一位。

查看 j 所在的指针是否小于等于 pivot，2 小于等于 3，我们替换 i 指针和 j 指针所在的位置，同时把 i 和 j 指针都右移一位。

查看 j 所在的指针是否小于等于 pivot，1 小于等于 3，我们替换 i 指针和 j 指针所在的位置，同时把 i 和 j 指针都右移一位。