用分治算法找出数组中的第k小的元素。C++代码

以下是基于快速选择算法的C++代码，可用于查找数组中的第k小元素。该算法的时间复杂度为O(n)。

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

int partition(int arr[], int left, int right, int pivotIndex) {
    int pivotValue = arr[pivotIndex];
    swap(arr[pivotIndex], arr[right]);
    int storeIndex = left;
    for (int i=left; i<=right-1; i++) {
        if (arr[i] < pivotValue) {
            swap(arr[i], arr[storeIndex]);
            storeIndex++;
        }
    }
    swap(arr[storeIndex], arr[right]);
    return storeIndex;
}

int quickSelect(int arr[], int left, int right, int k) {
    if (left == right) return arr[left];
    int pivotIndex = left + rand() % (right - left + 1);
    pivotIndex = partition(arr, left, right, pivotIndex);
    if (k == pivotIndex) return arr[k];
    else if (k < pivotIndex) return quickSelect(arr, left, pivotIndex-1, k);
    else return quickSelect(arr, pivotIndex+1, right, k);
}

int main() {
    int arr[] = { 3, 7, 9, 2, 6 };
    int k = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Array: ";
    for (int i=0; i<n; i++) cout << arr[i] << " ";
    cout << "\n";
    int kthSmallest = quickSelect(arr, 0, n-1, k-1);
    cout << "kth smallest element: " << kthSmallest << "\n";
    return 0;
}