QuickSelection \texttt{QuickSelection} QuickSelection是NOIP算法，用于求第k大的元素，原理就是快排的快速划分。
每次随机选一个值，把比这个值小的放在左边，比这个值大的放在右边，
如果我们要求的元素比左边的大，那么就递归右边，反之为左边或答案就是当前点。
这个过程如果随机就是期望 O ( n ) O(n) O(n)的，实际运行很快。
而
Median of medians \texttt{Median of medians} Median of medians是快速选择算法的严格 O ( n ) O(n) O(n)版本。
我们随机选值是不行的，要确定，但是这个算法已经是快排的简化版，在排序界已经没有什么算法可以套用了。。。。。那就套用他自己，我们考虑怎样选值比较好，分成 n k \frac nk kn个大小为 k k k的序列，每个序列求一个中位数，再求这些中位数的中位数 x x x，那么至少有 k 2 ∗ n 2 k = n 4 \frac k2 * \frac n{2k} = \frac n4 2k∗2kn=4n个数比 x x x小，那么划分出来的区域最大也就是 3 n 4 \frac {3n}{4} 43n
那么最坏复杂度就是 T ( n ) = n k T ( k ) + T ( n k ) + T ( 3 n 4 ) T(n) = \frac nkT(k) + T(\frac nk) +T(\frac {3n}4) T(n)=knT(k)+T(kn)+T(43n)
因为 T ( k ) T(k) T(k)是常数，所以可以看做是常数 C C C
T ( n ) = n C k + T ( n k ) + T ( 3 n 4 ) T(n)=\frac {nC}k+T(\frac nk) + T(\frac {3n}4) T(n)=knC+T(kn)+T(43n)
这个复杂度乍一看不好分析。
一般来说用 k = 5 k=5 k=5， C = k 2 = 25 C=k^2 = 25 C=k2=25， T ( n ) = 5 n + T ( 0.2 n ) + T ( 0.75 n ) = O ( n ) T(n) = 5n+T(0.2n)+T(0.75n)=O(n) T(n)=5n+T(0.2n)+T(0.75n)=O(n)
常数据说极大。