第K个数字

代码模板

int qchoise(int q[], int l, int r, int pos)
{
    if (l == r)
        return q[l];
    int i = l - 1, j = r + 1, x = q[(l + r) / 2];
    while (i < j)
    {
        while (q[++i] < x)
        {
        }
        while (q[--j] > x)
        {
        }
        if (i < j)
            swap(q[i], q[j]);
    }
    int sl = j - l + 1;
    if (pos <= sl)
        return qchoise(q, l, j, pos);
    return qchoise(q, j + 1, r, pos - sl);
}

代码原理

扫描+交换

第一步首先和之前的快速排序算法相同，首先在第一步的时候随机取一个位置，然后将这个位置的数字q[x]记录下来，然后一个指针i从前向后扫描数列，一个指针j从后向前扫描数列，最后一般来说最后i会在x的位置停下，而j会停在x的前一个。这样第一轮的排序就达成了，在q[x]前面的数字都比q[x]小，在q[x]后面的数字都比它大。

位置排序

将整个数列分为Left和Right两部分，统计Left和Right的数量，如果pos<Left的数量，则说明需要的数字在Left序列里面，这个时候只需要再次对Left序列进行递归，如果数字在Right序列中，则说明pos的位置变成了第pos-[Left的数量]个，然后只需要对右半边进行递归即可

结果

在不断进行递归操作后，将会只剩下pos位置的数字，也就是第pos个数字，这个时候返回的结果就是第pos个数字了。

时间复杂度

第一次扫描的时候时间复杂度为n，第二次扫描的时候由于是扫描一半，所以最多也只有1/2n，然后依次下去就是1/4n，1/8n…，由数学知识可以得出，n+1/2n+… 最多不会超过2n，所以复杂度为O(n)。