寻找第K小数的高效算法-CSDN博客

本文链接：https://blog.csdn.net/sgbfblog/article/details/7925418

这篇博客探讨了寻找第K小数的不同算法，包括排序、建立最大堆、类快速排序以及最坏情况下线性时间的选择方法。其中，建堆和类快速排序方法在效率上优于直接排序，而最坏情况下的线性时间选择算法在特定条件下能达到O(N)的时间复杂度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

前言

寻找第K小的数属于顺序统计学范畴，通常我们可以直接在O(NlgN)的时间内找到第K小的数，使用归并排序或者堆排序对输入数据按从小到大进行排序，然后选择第K个即可。然而，我们还有更好的算法。

一、热身—最大值和最小值

首先来看一个简单的问题，在一个有n个元素的集合中，需要多少次比较才能确定其最小值呢？这可以很容易退出需要n-1次这个上界。伪代码如下所示：

MINIMUM(A)
    min = A[1]
    for i=2 to n
          if  A[i] < min
              min = A[i]
    return min

寻找最小值需要进行n-1次比较，这已经是最优结果。如果需要同时找出最大值和最小值，可以直接进行两次查询，一次最大值一次最小值，共需要2(n-1)次比较。而事实上，我们可以只通过3*[n/2]次比较就足以同时找到最大值和最小值。通过成对的处理元素，先将一对输入元素比较，找到较大值和较小值。然后将较大值与当前最大值比较，较小值与当前最小值比较，这样每两个元素需要比较3次，一共需要3*[n/2]次比较。我们可以用递归算法写一个寻找最大值和最小值的程序，代码如下：

void max_min(int a[], int l, int r, int &minValue, int &maxValue)
{
    if (l == r) { //l与r之间只有1个元素
        minValue = maxValue = a[l];
        return;
    }
    if (l + 1 == r) { //l与r之间一共只有2个元素
        if (a[l] > a[r]) {
            minValue = a[r];
            maxValue = a[l];
        } else {
            minValue = a[l];
            maxValue = a[r];
        }
        return;
    }
    int lmax, lmin;
    int m = (l + r) / 2;
    max_min(a, l, m, lmin, lmax); //找出左边的最大值和最小值
    int rmax, rmin;
    max_min(a, m+1, r, rmin, rmax); //找出右边的最大值和最小值
    maxValue = max(lmax, rmax); //最终的最大值
    minValue = min(lmin, rmin); //最终的最小值
}