快速选择算法--无序数组中寻找中位数 O(n)的算法及证明

一、排序算法

排序的算法是最容易想到的，但是即使是快排，平均复杂度也只有 $O(n\log n)$。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

double findMid(vector<int>& nums) {
    int n = nums.size();
    sort(nums.begin(), nums.end());
    if (n % 2) {
        return nums[n/2];
    }
    else {
        return (nums[n/2] + nums[n/2-1]) / 2.0;
    }
}


int main() {
    vector<int> nums = {9, 8, 7, 6, 1, 2, 3, 4};
    cout << findMid(nums) << endl;
    return 0;
}

这就很简单，没什么说的了，只需要注意如果数组为偶数需要求两个数的平均值

二、快速选择算法

1、随机选择一个元素作为基准

2、将数组分为三个部分，小于基准，等于基准，大于基准

3、确定位置：

• 如果基准的位置恰好是中位数位置，那么返回基准
• 如果中位数在小于基准位置，那么递归处理小于部分
• 如果中位数在大于基准位置，那么递归处理大于部分

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int quickselect(vector<int> nums, int l, int r, int k) {
    if (l == r) return nums[l];

    // 元素选择为最右边元素
    int pivot_value = nums[r];

    int j = l;
    for (int i=l; i<r; i++) {
        if (nums[i] < pivot_value) {
            swap(nums[i], nums[j]);
            ++j;
        }
    }
    // 基准元素放回数组中间
    swap(nums[r], nums[j]);

    if (k == j) {
        return nums[k];
    }
    else if (k < j) {
        return quickselect(nums, l, j-1, k);
    } 
    else {
        return quickselect(nums, j+1, r, k);
    }
    

}

double findMid(vector<int>& nums) {
    int n = nums.size();
    if (n % 2) {
        // cout << '$' << endl;
        return quickselect(nums, 0, n-1, n/2);
    }
    else {
        int a = quickselect(nums, 0, n-1, n/2);
        int b = quickselect(nums, 0, n-1, n/2-1);
        // cout << a << ' ' << b << endl;
        return (a + b) / 2.0;
    }
}


int main() {
    vector<int> nums = {9, 8, 7, 6, 1, 2, 3, 4};
    cout << findMid(nums) << endl;
    return 0;
}

快速选择算法有点类似于快速排序，可以帮助我们快速找到数组中的第k个元素。但是快速排序的时间复杂度是 $O(n\log n)$为什么快速选择算法就是 $O(n)$ 呢？

2.1、期望时间复杂度

期望分析：

• 假设基准将数组分为 $an$ 和 $(1-a)n$ 两部分，其中 $a$ 是一个介于 0 和 1 之间的常数。
• 每次递归调用后的时间复杂度可以表示为： $T(n)=T(\alpha n)+O(n)$
• 这里，$O(n)$ 是当前分区所需的时间。

递归展开：

• 我们可以展开这个递归公式：

$$T(n)=O(n)+T(an)=O(n)+O(n^2)+T(a^{2}n)=...=O(n)+O(n^2)+...+O(a^{k}n)$$

其中k是递归深度，直到n变为1。

求和公式：

• 求和部分是一个几何级数：

$$O(n)+O(n^2)+...+O(a^{k}n)=O(n)(1+a+a^2+...+a^k)=\frac{1-a^k}{1-a}O(n)$$

最终结果：

• 因此，整体的时间复杂度可以表示为：$O(n)$

2.2、最差时间复杂度

最差时间复杂度就可以看做每一层选择的值都很差，都需要和剩下的n-1个值比较
$$T(n)=T(n-1)O(n)=T(n-2)O(n-1)O(n)=...=O(\frac{n(n-1)}{2})=O(n^2)$$