针对从乱序数组中找到第 $k$ 小元素的问题，最经典且高效的算法是 快速选择算法 (Quick Select)。

虽然普通的排序（如快速排序、归并排序）可以将数组全排好后取第 $k$ 个，时间复杂度是 $O(N \log N)$，但如果只要第 $k$ 个，其实没必要把所有人都有序排列。

以下是几种针对该场景的方法，按推荐程度排序：

1. 快速选择算法 (Quick Select) —— 最推荐

这是基于快速排序 (Quick Sort) 思想的变种算法。

  • 核心思想：

    在快排中，我们每次选取一个基准值 (Pivot)，执行 Partition 操作，将小于 Pivot 的放左边，大于 Pivot 的放右边。

    • 快排：需要递归处理左右两边。

    • 快选：Partition 后，我们可以知道 Pivot 最终所在的下标 index。

      • 如果 index == k-1，那 Pivot 就是我们要找的目标，直接返回。

      • 如果 index > k-1，说明目标在左半区，我们只递归左边。

      • 如果 index < k-1，说明目标在右半区，我们只递归右边。

  • 时间复杂度：

    • 平均情况：$O(N)$。因为每次大约甩掉一半的数据（$N + N/2 + N/4 + ... = 2N$）。

    • 最坏情况：$O(N^2)$（极少出现，除非数组本身有序且每次选最差 Pivot）。

  • 空间复杂度：$O(1)$ （迭代写法）或 $O(\log N)$ （递归栈）。

C++ 代码实现 (结合你的 C++ 背景)

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// 标准的 Partition 操作
int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right]; // 选最右边作为基准
    int i = left;
    for (int j = left; j < right; j++) {
        if (nums[j] < pivot) { // 找第k小，所以小于放左边
            swap(nums[i], nums[j]);
            i++;
        }
    }
    swap(nums[i], nums[right]);
    return i; // 返回 pivot 的最终位置
}

int quickSelect(vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];

    int pivotIndex = partition(nums, left, right);

    // k-1 是因为数组下标从0开始，第k小的元素下标是k-1
    if (k - 1 == pivotIndex) {
        return nums[pivotIndex];
    } else if (k - 1 < pivotIndex) {
        // 目标在左边
        return quickSelect(nums, left, pivotIndex - 1, k);
    } else {
        // 目标在右边
        return quickSelect(nums, pivotIndex + 1, right, k);
    }
}

int findKthSmallest(vector<int>& nums, int k) {
    return quickSelect(nums, 0, nums.size() - 1, k);
}

2. 堆排序 (Heap Select) —— 适合处理海量数据流

如果你不能一次性把数据都读进内存（比如数据是源源不断过来的流），或者 $k$ 远小于 $N$ 时，堆是很好的选择。

  • 核心思想：

    维护一个容量为 $k$ 的大顶堆 (Max Heap)。

    1. 先把前 $k$ 个元素入堆。

    2. 从第 $k+1$ 个元素开始遍历：

      • 如果当前元素 < 堆顶元素，说明当前元素比堆里最大的那个更小，更有可能是“前 $k$ 小”的一员。

      • 弹出堆顶，压入当前元素。

    3. 遍历结束后，堆顶元素就是第 $k$ 小的数（因为堆里存的是最小的 $k$ 个数，而堆顶是这 $k$ 个里最大的，即第 $k$ 小）。

  • 时间复杂度：$O(N \log k)$。

  • 空间复杂度：$O(k)$。

3. C++ STL 的“作弊”方法 (std::nth_element)

作为 C++ 学生，在实际工程或比赛中（非手写算法题），你应该直接使用标准库。

C++ STL 提供了一个专门针对这个问题的函数 std::nth_element。它底层通常使用的是 Introselect 算法（混合了快速选择，当递归太深时转为堆排序，保证最坏也是 $O(N)$）。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <vector>
#include <algorithm>
#include <iostream>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    int k = 3; 

    // 该函数会将第 k 小的元素放到 v[k-1] 的位置
    // 且保证 v[k-1] 左边的都比它小，右边的都比它大（但不保证左右两边内部有序）
    std::nth_element(v.begin(), v.begin() + k - 1, v.end());

    std::cout << "第 " << k << " 小的元素是: " << v[k-1] << std::endl; // 输出 2
    return 0;
}

总结建议

  • 面试/考试手写算法：首选 快速选择算法 (Quick Select)，因为它的平均时间复杂度是线性的 $O(N)$。

  • 实际开发/工程：直接使用 std::nth_element，它经过了极致优化。

  • 海量数据/数据流：使用 容量为 k 的大顶堆。