Quick Select - HolmesJJ/Data-Structures-and-Algorithms GitHub Wiki

找到n个未排序的数中第k大的数

传统方法1

排序
返回第k大的数

时间复杂度为O(nlogn + k)

传统方法2

遍历数组，储存在遍历过程中遇到的前k大的数
返回第k大的数

时间复杂度为O(nk)

快速选择算法

详解

经典算法之快速选择算法快速选择(QuickSelect)的平均时间复杂度分析 Top K 问题的最优解 - 快速选择算法（Quickselect） Quick Select Algorithm 快速选择算法

分区Partition分析

每次分区都刚好分两半，这是最好的情况，时间复杂度是O(n)
每次分区都分成1和n-1两个部分，这是最坏的情况，时间复杂度是O(n^2)
如果pivot将数组分为两部分，每部分的大小至少为n/10，则这是个好的pivot（经验值）。 假设每次分区都分成1:9两个部分，即(1/10):(9/10)，时间复杂度仍可以是O(n)

但根据以上的推导过程可以看出，较大分区的占比越大，即log的底数越接近1，时间复杂度越高，因此针对这种情况，可以随机选取pivot的位置，然后不断重复分区，直到分区后的两个部分的大小都在(1/10)n和(9/10)n的区间

Select(A[1..n], n, k)
    if (n == 1) then return A[1];
    else Choose random pivot index pIndex.
        // 随机选取pivot的位置，然后不断重复分区，直到分区后的两个部分的大小都在(1/10)n和(9/10)n的区间
        repeat
            p = partition(A[1..n], n, pIndex)
        until p > (1/10)n and p < (9/10)n
        if (k == p) then return A[p];
        else if (k < p) then
            return Select(A[1..p–1], p–1, k) // p–1为A[1..p–1]的长度
        else if (k > p) then
            return Select(A[p+1], n–p, k) // n–p为A[p+1..n]的长度

选取到一个好的pivot的概率p是8/10，而选取到一个坏的pivot的概率(1 - p)是1/10（假设一个数组的长度是10，好的pivot只能是中间的8个位置中的一个）根据概率论Probability Theory可知，不断循环重复选择一个pivot直到这个pivot是好的预期次数：E[pivot choices] = 1/p = 10/8 < 2，这意味着上面的代码中从repeat到until这个代码块的执行次数是小于2次，由此可得，pivot分区除了1:9，2:8也是可行，因为E[pivot choices] = 1/p = 10/6 < 2

**E[T(n)] = E[T(k)] + E[pivot choices] (n)** <= E[T(k)] + 2n

要点

时间复杂度是O(n)，空间复杂度是O(1)