求第 k 小元素

线性时间选择

元素选择问题的一般提法：给定线性序集中 $n$ 个元素和一个整数 $k$，$1 \leqslant k \leqslant n$，要求找出这 $n$ 个元素中第 $k$ 小的元素。即如果将这个 $n$ 个元素依基线排列时，排在第 $k$ 个位置的元素即为我们所找的元素。

在数组有序的情况下，可以很容易地通过递归的方法找到其中第 $k$ 小元素。

• 如果 $k \leqslant i-p+1$，则 $a[p:r]$ 的第 $k$ 小元素落在子数组 $a[p:i]$ 中。
• 如果 $k > i-p+1$，则 $k$ 落在 $a[i+1:r]$ 是其中第 $k-(i-p+1)$ 小元素。

算法代码

template <class Type>
Type RandomizedSelect(Type a[], int p, int r, int k) {
    if (p == r) {
        return a[p];
    }
    int i = RandomizedPartition(a, p, r);
    j = i - p + 1;
    if (k <= j) {
        return RandomizedSelect(a, p, i, k);
    } else {
        return RandomizedSelect(a, i + 1, r, k - j);
    }
}

算法分析

在最坏情况下，线性时间选择算法需要 $O(n^2)$ 的计算时间。但可以证明，线性时间选择算法可以在 $O(n)$ 平均时间内找出 $n$ 个输入元素中的第 $k$ 小元素。

堆排序

现在问题升级，如果数组不是有序的，即在有 $n$ 个元素的数组中找第 $k$ 小的元素。

此问题的解决思路可以先对原始数组进行排序，然后再采用线性时间选择算法求解。这里可以采用堆排序的方法找第 k 小元素。

算法思想

为了找第 $k$ 小元素，需要将数组按照升序排序，因此建立最大堆。循环执行以下步骤，直至所有元素出堆：

• 每次堆顶元素（即最大元素）与堆中最后一个元素交换。
• 剔除最大元素后调整为最大堆。

算法分析

• 调整为最大堆：$O(\log {n})$
• 循环弹出堆顶元素：$O(n)$

因此堆排序的时间复杂度为 $O(n \log {n})$。

最终对排序后的数组进行线性时间选择，时间复杂度为 $O(n \log {n})$。因此，采用堆排序的方法求解第 $k$ 小元素的时间复杂度为 $O(n \log {n})$。

复杂度为 $O(n)$ 的算法

设数组 S 的长度为 $n$。若 $n < 50$，则采用堆排序的方法找出第 $k$ 小元素。否则，

• 将 $n$ 个元素分为 $\left \lceil n/5 \right \rceil$ 组，每组 $5$ 个元素并排序。
• 将每组的第 $3$ 个元素取出，得到大小为 $\left \lceil n/5 \right \rceil$ 的数组 M。
• 在数组 M 中找第 $\left \lceil \left \lceil n/5 \right \rceil /2 \right \rceil$ 小的元素 m。
• 将原数组 S 分为大于 m、等于 m 和小于 m 的三个集合，并计算集合中元素的个数，并将之与 $k$ 作比较，确定第 $k$ 小元素所在的集合。