无序整数序列找第k小 随机算法代码C++

以下是基于快排思想的随机算法，可以找到一个无序整数序列中第k小的数：

#include<iostream>
#include<cstdlib>
#include<ctime>
using namespace std;

int partition(int arr[], int l, int r) {
    int pivot = arr[r];
    int i = l - 1;
    for(int j = l; j < r; j++) {
        if(arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[r]);
    return i+1;
}

int randomPartition(int arr[], int l, int r) {
    int n = r-l+1;
    int pivot = rand() % n;
    swap(arr[l+pivot], arr[r]);
    return partition(arr, l, r);
}

int kthSmallest(int arr[], int l, int r, int k) {
    if(k > 0 && k <= r-l+1) {
        int pos = randomPartition(arr, l, r);
        if(pos-l == k-1)
            return arr[pos];
        if(pos-l > k-1)
            return kthSmallest(arr, l, pos-1, k);
        return kthSmallest(arr, pos+1, r, k-pos+l-1);
    }
    return INT_MAX;
}

int main() {
    int n, k;
    cout << "Enter the number of elements in the array: ";
    cin >> n;
    int arr[n];
    cout << "Enter the elements of the array: ";
    for(int i = 0; i < n; i++)
        cin >> arr[i];
    cout << "Enter the value of k: ";
    cin >> k;
    srand(time(NULL));
    cout << "The " << k << "th smallest element is " << kthSmallest(arr, 0, n-1, k);
    return 0;
}

注：该算法的时间复杂度为O(n)，其中n为序列长度。