c++分治算法求N个数中第K小(大)的数

使用分治算法求解N个数中第K小（大）的数的C++代码如下：

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

// 函数声明
int partition(std::vector<int>& nums, int low, int high);
int quickSelect(std::vector<int>& nums, int low, int high, int k);

// 分治算法的实现
int partition(std::vector<int>& nums, int low, int high) {
    int pivot = nums[high];
    int i = low - 1;

    for (int j = low; j < high; ++j) {
        if (nums[j] <= pivot) {
            ++i;
            std::swap(nums[i], nums[j]);
        }
    }

    std::swap(nums[i + 1], nums[high]);
    return i + 1;
}

int quickSelect(std::vector<int>& nums, int low, int high, int k) {
    if (low <= high) {
        int pivotIndex = partition(nums, low, high);

        if (pivotIndex == k - 1) {
            return nums[pivotIndex];
        } else if (pivotIndex < k - 1) {
            return quickSelect(nums, pivotIndex + 1, high, k);
        } else {
            return quickSelect(nums, low, pivotIndex - 1, k);
        }
    }

    // 这里可以根据实际情况返回一个默认值或者抛出异常等
    return -1;
}

int main() {
    // 输入数组和K的值
    std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
    int k = 3;

    // 调用快速选择算法
    int result = quickSelect(nums, 0, nums.size() - 1, k);

    // 输出结果
    std::cout << result << std::endl;

    return 0;
}

这段代码实现了一个基于快速选择算法的分治解法，其中 partition 函数用于在数组中选择一个主元，并将数组分为两部分，左边的元素小于主元，右边的元素大于主元。quickSelect 函数通过多次调用 partition 来找到第K小的数。