快速选择

快速的找到第k大的数，思想和快排差不多。均摊分析时间复杂度为$O(n)$

主要思路

1. 选取一个pivot
2. 把数据划分成$>pivot,<pivot,=pivot$三个区间
3. 判断目标第k大的数位于哪个区间，然后对应迭代查找

规避了排序的过程，在划分区间的时候只需要知道“大小”，而不需要知道“顺序”

小模板

使用非原地的递归方式，如果是原地算法，空间复杂度为$O(1)$，尾递归也可以优化成迭代实现

public static int QuickSelectKthLargest(int[] nums, int k)
{
	if (nums.Length == 1)
		return nums[0];
	int pivot = nums[nums.Length / 2];
	var lows = new List<int>();
	var highs = new List<int>();
	var sames = new List<int>();
	foreach (var val in nums)
	{
		if (val == pivot) sames.Add(val);
		if (val < pivot) lows.Add(val);
		if (val > pivot) highs.Add(val);
	}
	if (k <= highs.Count)
	{
		// 第 k 大在 highs 中
		return QuickSelectKthLargest(highs.ToArray(), k);
	}
	else if (k <= highs.Count + sames.Count)
	{
		// 第 k 大在 pivots 区间
		return pivot;
	}
	else
	{
		// 第 k 大在 lows 中，递归查找
		return QuickSelectKthLargest(lows.ToArray(), k - highs.Count - sames.Count);
	}
}