问题
如何在 O(n) 时间复杂度内在无序数组中找到第K大的数？
思路
我们的目的是找到第K大的数（对于第K小的数同理），不需要关注具体哪些数比K大，也不需要关注具体哪些数比K小。
由此我们可以想到快速排序的分区思想。进行分区后，在分区点两侧分别是比分区点大的数和比分区点小的数。
以找出第K大的数为例，可以编写分区算法，令分区点左侧比分区点大，分区点右侧比分区点小。
设数组A，分区点p，分区后 A[p] 就是第 p+1 大的数：（因为 p表示数组中索引，所以需要 +1）
- 若 p+1=K，则 A[p] 就是第 K 大的数；
- 若 p+1<K，则第 K 大的数在分区点右侧，即 A[p+1...n-1]；（因为第p+1大的数大于第K大的数，所以需要在右侧区间中继续找）
- 若 p+1>K，则第 K 大的数在分区点左侧，即 A[0...p-1]；（因为第p+1大的数小于第K大的数，所以需要在左侧区间中继续找）
若第 K 大的数在分区点左右侧区间中，则按照上述过程递归查找。
评估
这种方法在大部分情况下都可以保证 O(n) 的时间复杂度。假设每次分区都能将数组分成两半，那么分至只剩一个元素，遍历次数为 n + (n/2) + (n/4) + ... + 1，即 2n - 1，复杂度为 O(n)。
在极端情况下，比如[100, 99, 98, ..., 1]中找出第40大的数，复杂度会变得很高。这个时候可以考虑优化分区算法，找合适的分区点。
值得一提的是，若K很小，可以通过维护一个长度为K的数组，仅需遍历一次无序数组即可找到第K大的数。
