本文将记录一些奇技淫巧，先从今天开始写，以前的找个时间再补上
应用超快速排序（$O(n)$），平常都是$O(nlogn)$
基于快排的思想，在每一层递归中，随机选取一个数做基准时，统计出大于基准值的数的个数$cnt$,如果$k<=cnt$就在左半段（比基准数大）中寻找第$k$大的数，反之则在右半段寻找第$k-cnt$大的数
复杂度证明:
因为每次只进入了左右两段的任意一个，则在平均情况之下复杂度为:$n+\frac{n}{2}+\frac{n}{3}+.....+1=O(n)$
原文：https://www.cnblogs.com/pyyyyyy/p/11669535.html