一、排序算法

排序的算法是最容易想到的，但是即使是快排，平均复杂度也只有 $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)$$