求第k小数代码c++

在C++中，求解第k小的元素通常需要结合优先队列（如`std::priority_queue`）或者快速选择算法（QuickSelect）。这里我将简单地解释一种基于快速选择的基本思路：

#include <vector>
#include <cstdlib>

// 快速选择函数，返回数组中第k小的元素的位置
int quickselect(std::vector<int>& nums, int k) {
    if (nums.empty()) return -1; // 空数组处理
    int left = 0, right = nums.size() - 1;
    
    while (left <= right) {
        int pivot_index = partition(nums, left, right);
        if (pivot_index == k - 1) return k - 1; // 找到目标位置
        else if (pivot_index > k - 1) right = pivot_index - 1; // 向左部分继续查找
        else left = pivot_index + 1; // 向右部分继续查找
    }
    return -1; // 如果k超出范围，返回-1
}

// 将数组分割成两部分，并返回pivot所在位置的索引
int partition(std::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) {
            std::swap(nums[i], nums[j]);
            ++i;
        }
    }
    std::swap(nums[i], nums[right]); // 将pivot放到正确的位置
    return i;
}

// 示例用法
int main() {
    std::vector<int> numbers = {3, 6, 8, 10, 1, 2, 1};
    int k = 4;
    int result_index = quickselect(numbers, k);
    if (result_index != -1)
        std::cout << "第" << k << "小的元素是：" << numbers[result_index] << std::endl;
    else
        std++.cout << "k超出范围" << std::endl;
    return 0;
}