长度为n的整数序列，试设计一个尽可能高效的算法，返回序列中第k小的元素。用c++写出源码

可以使用快速选择算法来解决这个问题，时间复杂度为O(n)。

以下是C++的实现代码：

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

using namespace std;

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

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

这个程序将输出序列中第2小的元素，即“2”。