题目

编写程序，演示 STL 威力巨大但在业务中常被忽视的算法 std::nth_element。通过基于快速选择算法（Quickselect），在平均 O(N) 线性时间复杂度内将排名第 N 小的元素准确归位至第 N 个迭代器槽位，并保证其左侧所有元素均不大于它，右侧所有元素均不小于它；对比完全排序 std::sort 的 O(N log N)，在求海量数据中位数时的极致速度提升。

输入格式：无需外部输入。

输出格式：输出使用 nth_element 快速求得的中位数、第 K 小元素以及划分后的部分有序数组。

数据范围与约定：快速选择划分、平均线性时间复杂度 O(N)。

思路与算法

1. 完全排序的算力浪费
如果只想找中位数或第 10 小的元素，调用 std::sort 将整个数组全部排好序是严重的算力浪费（耗时 O(N log N)）。

2. Quickselect 核心机制
std::nth_element(first, nth, last) 利用快排的单侧分区（Partition）：如果基准数落在了 nth 左侧，只需递归处理右半部分；反之只递归左半部分。几何级数求和 \(N + N/2 + N/4 + \dots \approx 2N\)，因此平均时间复杂度严格为 O(N)！

3. 局部有序性保证
执行完毕后，虽然整个数组不是严格有序的，但标准保证：对于任意处于 nth 左边的位置 \(i\)，arr[i] <= arr[nth]；对于任意右边位置 \(j\)，arr[nth] <= arr[j]。

完整程序

#include <iostream>
#include <vector>
#include <algorithm>

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

    std::cout << "原始乱序数组 (大小 9): ";
    for (int x : nums) std::cout << x << " ";
    std::cout << "\n";

    // 寻找中位数：第 nums.size() / 2 个位置（索引为 4）
    auto midIter = nums.begin() + nums.size() / 2;
    std::nth_element(nums.begin(), midIter, nums.end());

    std::cout << "\n执行 std::nth_element 重排后:\n";
    std::cout << "归位后的中位数元素 (索引 4): " << *midIter << "\n";
    std::cout << "重排后数组全貌: ";
    for (int x : nums) std::cout << x << " ";
    std::cout << "\n";
    std::cout << "验证：中位数 5 的左侧全部 <= 5，右侧全部 >= 5！\n\n";

    // 快速查找第 3 小元素（索引 2）
    auto kIter = nums.begin() + 2;
    std::nth_element(nums.begin(), kIter, nums.end());
    std::cout << "快速查询第 3 小元素 (索引 2): " << *kIter << "\n";

    return 0;
}

运行示例

输出：

原始乱序数组 (大小 9): 9 1 8 2 7 3 6 4 5 

执行 std::nth_element 重排后:
归位后的中位数元素 (索引 4): 5
重排后数组全貌: 3 1 4 2 5 7 6 8 9 
验证：中位数 5 的左侧全部 <= 5，右侧全部 >= 5！

快速查询第 3 小元素 (索引 2): 3