C++在无序数组中选择第k小个数的实现方法

使用C++在无序数组中选择第k小的数可以通过一些排序算法或选择算法来实现。以下是一种通过快速选择算法（QuickSelect）的方式来实现的例子：

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

int partition(std::vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

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

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

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

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

    // This should not happen if k is valid.
    return -1;
}

int main() {
    std::vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int k = 4;  // 选择第4小的数

    int result = quickSelect(arr, 0, arr.size() - 1, k);
    
    std::cout << "第" << k << "小的数是: " << result << std::endl;

    return 0;
}

还有其他的选择算法，例如堆排序等。