问题分析

面对这个问题，最简单的想法是对数据进行排序，然后根据下标即可找到第k小的元素，目前已知的排序算法的最低时间复杂度为 O ( n log ⁡ 2 log ⁡ 2 n ) O(n\sqrt{\log_2 {\log_2 n}}) O(nlog2​log2​n ​)，但并不为人熟知。目前应用最广的排序算法的最低时间复杂度为 O ( n log ⁡ 2 n ) O(n\log_2 n) O(nlog2​n)。

但是，作为完美主义者的程序员，需要思考，找到第k小的元素一定需要排序吗？但除了寻找最大或最小的元素之外，我们似乎只能选择排序。那么能否只进行部分排序,便可找到第k小的元素呢？答案是显然的，只需要采用每一趟都能确定一个固定元素的排序算法即可。

思考 O ( n log ⁡ 2 n ) O(n\log_2 n) O(nlog2​n)的排序算法中有哪些算法每一趟可以确定一个固定元素，答案是快速排序和堆排序（不考虑锦标赛排序，堆排序是锦标赛排序的升级版）。这里以快速排序为例，方便引入后面介绍的BFPRT算法，不过还有一个原因是堆排序获取第k小的元素的时间复杂度是 O ( n ) O(n) O(n)的概率小于快速排序。

快排应用

我们知道，快排每一趟都会有随机有一个元素处于最终位置上，故只需在快排中设置一个新的递归出口再加以微改便能返回第k小的元素。
代码如下：
这里采用的快排为随机化快速排序，没有了解过的的朋友可以看一下我的另外一篇博客：升级版快速排序——随机化快速排序

template<typename T>
void partition(T array[],int left,int right,int& mid)
{
	srand(time(0));
	int i = left, j = right, move = rand() % (right - left + 1) + left;
	T temp = array[move];
	array[move] = array[left];
	while (i != j)
	{
		while (array[j] > temp&&j > i) j--;
		if (i < j) array[i++] = array[j];
		while (array[i] < temp&&i < j) i++;
		if (i < j) array[j--] = array[i];

	}
	array[i] = temp;
	mid = i;
}

template<typename T>
T random_quick_sort(T array[], int left, int right,int k)
{
	
	if (k > right - left + 1) exit(7);
	int i;
	partition(array, left, right, i);
	if (k == i - left + 1) return array[i];
	else if (k > i - left + 1) return random_quick_sort(array, i + 1, right, k - i + left - 1);
	else return random_quick_sort(array, left, i - 1, k);
}

这个算法的时间复杂度的确定需要用到指示器随机变量。 E [ T ( n ) ] = E [ ∑ k = 0 n − 1 X k ( T ( m a x E[T(n)]=E[\sum_{k=0}^{n-1}X_k(T(max E[T(n)]=E[∑k=0n−1​Xk​(T(max{ k , n − k − 1 k,n-k-1 k,n−k−1} ) ) + Θ ( n ) ] ))+\Theta(n)] ))+Θ(n)]，最终得到 E [ T ( n ) ] = Θ ( n ) E[T(n)]=\Theta(n) E[T(n)]=Θ(n)，即该算法的时间复杂度的期望值为 O ( n ) O(n) O(n)
但是存在最坏情况，即每一次划分只能划分出一个部分，即 T ( n ) = T ( n − 1 ) + Θ ( n ) T(n)=T(n-1)+\Theta(n) T(n)=T(n−1)+Θ(n)，由等差级数可以得到最坏情况下的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

BFPRT算法

不想写了，困了

重写了篇博客，内容和这一样，转到那边去吧：找到第k小的元素【top-k】：快排应用与BFPRT算法