利用分治对于给定的 n 个元素的数组a[0:n-1]，要求从中找出第 k 小的元素代码

如下：

#include <iostream>
using namespace std;

// 利用分治找到第k小的元素
int quickselect(int arr[], int left, int right, int k) {
    if (left == right) {
        return arr[left];
    }

    // 以arr[left]为基准进行划分
    int pivot = arr[left];
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) {
            j--;
        }
        arr[i] = arr[j];
        while (i < j && arr[i] <= pivot) {
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = pivot;

    if (i - left + 1 == k) {
        return arr[i];
    } else if (i - left + 1 < k) {
        return quickselect(arr, i + 1, right, k - (i - left + 1));
    } else {
        return quickselect(arr, left, i - 1, k);
    }
}

int main() {
    int n, k;
    cout << "请输入数组长度n和k的值：";
    cin >> n >> k;

    int arr[n];
    cout << "请输入" << n << "个元素：";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    int kth = quickselect(arr, 0, n - 1, k);
    cout << "第" << k << "小的元素为：" << kth << endl;

    return 0;
}

快速选择算法的时间复杂度为O(n)，可以很好地解决在大数据中查找第k小元素的问题。