求第k小问题快排c++

好的，求解第k小问题可以使用快速排序算法的变种——快速选择算法。下面是使用快速选择算法求解第k小问题的C++代码：

#include <iostream>
#include <vector>
using namespace std;

int partition(vector<int>& nums, int left, int right) {
    int pivot = nums[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (nums[j] <= pivot) {
            i++;
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[i+1], nums[right]);
    return i+1;
}

int quickSelect(vector<int>& nums, int left, int right, int k) {
    if (left == right) return nums[left];
    int pivotIndex = partition(nums, left, right);
    if (k == pivotIndex) return nums[k];
    else if (k < pivotIndex) return quickSelect(nums, left, pivotIndex-1, k);
    else return quickSelect(nums, pivotIndex+1, right, k);
}

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

int main() {
    vector<int> nums = {5, 3, 2, 6, 1, 4};
    int k = 3;
    int res = kthSmallest(nums, k);
    cout << "The " << k << "th smallest element is: " << res << endl;
    return 0;
}

这里的 `quickSelect` 函数是快速选择算法的实现，其核心思想是：选择一个基准元素，将数组划分为两个部分，左边部分的元素都小于等于基准元素，右边部分的元素都大于基准元素，然后根据基准元素的位置和 k 的关系，递归地在左边或右边部分继续查找，直到找到第 k 小的元素为止。