用c++实现最坏情况下为线性时间的选择算法

好的，让我来回答你的问题。

选择算法是一种在未排序的数组中查找第k小元素的算法。最差情况下，选择算法的时间复杂度是O(n^2)。但是，我们可以使用随机化算法将其优化到O(n)。

这里介绍一种最坏情况下为线性时间的选择算法——中位数的中位数算法（Median of Medians Algorithm）。

该算法的基本思想是将数组分成大小为5的小组，并找到每个小组的中位数。然后，递归地找到这些中位数的中位数（即第n/2小的元素），并将其作为主元素。接着，通过主元素将数组分成两个子数组，其中一个子数组包含所有小于主元素的元素，另一个子数组包含所有大于主元素的元素。然后，根据k与主元素的大小关系，在其中一个子数组中递归查找第k小的元素。

这个算法的时间复杂度为O(n)，但是实际上，常数项比较大，因此在实际应用中，可能不如QuickSelect算法效率高。

以下是C++代码实现：

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

using namespace std;

int findMedian(vector<int>& arr, int left, int right) {
    sort(arr.begin() + left, arr.begin() + right + 1);
    return arr[(left + right) / 2];
}

int partition(vector<int>& arr, int left, int right, int pivot) {
    while (left <= right) {
        while (arr[left] < pivot) left++;
        while (arr[right] > pivot) right--;
        if (left <= right) {
            swap(arr[left], arr[right]);
            left++;
            right--;
        }
    }
    return left;
}

int findKthSmallest(vector<int>& arr, int left, int right, int k) {
    if (k > 0 && k <= right - left + 1) {
        int n = right - left + 1;
        int i;
        vector<int> median((n + 4) / 5);
        for (i = 0; i < n / 5; i++) {
            median[i] = findMedian(arr, left + i * 5, left + i * 5 + 4);
        }
        if (i * 5 < n) {
            median[i] = findMedian(arr, left + i * 5, left + i * 5 + n % 5 - 1);
            i++;
        }
        int medianOfMedians = (i == 1) ? median[i - 1] : findKthSmallest(median, 0, i - 1, i / 2);
        int pos = partition(arr, left, right, medianOfMedians);
        if (pos - left == k - 1) return arr[pos];
        if (pos - left > k - 1) return findKthSmallest(arr, left, pos - 1, k);
        return findKthSmallest(arr, pos + 1, right, k - pos + left - 1);
    }
    return INT_MAX;
}

int main() {
    vector<int> arr = { 12, 3, 5, 7, 4, 19, 26 };
    int n = arr.size();
    int k = 3;
    cout << "K'th smallest element is "
         << findKthSmallest(arr, 0, n - 1, k);
    return 0;
}

以上代码实现了一个在最坏情况下为线性时间的选择算法，可以在O(n)的时间复杂度内查找未排序数组中的第k小元素。