Acwing 785. 快速排序/AcWing 786. 第k个数
简单介绍
快速排序被很多语言的内置函数作为默认的排序算法。也是因为它具有较优的平均时间复杂度O(nlogn)，虽然最坏的时间复杂度也是O(n^2)，即每次比较都要全部交换，但是这种情况并不多见。并且因为快排是在原地操作，空间复杂度上只占用递归时候用到的栈空间，即递归深度，所以空间复杂度在O(logn)，同样优秀。
算法原理
快排的本质实际上也是分治思想的运用。我们随机选取一个数字作为他的基准数（或者叫中心点）。然后我们把小于中心点的元素移动到它的左边，把大于中心点的元素移动到右面，这样以中心点为分界，左边全部小于中心点，右边全部大于中心点，所以左边全部小于右边，我们称为左边整体和右边整体是相对有序的。递归左右分区分别执行上述操作，直到每个分区只有一个数为止。
对于中心点的选取方法很多，使用最多的是设计一个随机选取的算法，使任何输入都能获得较好的性能。更方便的方式就是选取头或者尾元素或者中间元素。
整体思路
1. 设定递归的结束条件，初始化左右两个指针
2. 取中心点，我这里取的是数组的中点。
3. 进入循环体，用当前元素和左右元素分别比较，记录他们的大小关系，如果左面大于中心点记录下来，如果右面小于中心点记录下来，将它们交换。
4. 递归左面，递归右面。
def quick(nums, l, r):if l >= r:return# 为了让左右边界都被选择到，先把左右指针都扩展一位# 在后面就可以先进行移动指针。i, j = l - 1, r + 1x = nums[(i + j) // 2]while i < j:# 该循环寻找左面大于等于中心点的元素while True:i += 1if nums[i] >= x:break# 该循环寻找左面小于等于中心点的元素while True:j -= 1if nums[j] <= x:break# 如果大于等于中心点的在左，小于等于中心点在右，交换他们两个位置。if i < j:nums[i], nums[j] = nums[j], nums[i]quick(nums, l, j)quick(nums, j + 1, r)n = int(input())nums = list(map(int, input().split()))quick(nums, 0, n - 1)print(' '.join(map(str, nums)))
TOP K问题
TOP K是很常见的问题，解法多样，但是最优解就是快速选择，基于快速排序做一点变化。快速排序最后要递归左右两个区间，但是快速选择只要递归一个区间即可，因为他只要保证前面k个数的区间全部小于后面区间就可以，所以每次只需要递归左右两个区间中的一个。
整体思路
1. 快速选择的前面部分与快速排序完全一样，一样到直接复制粘贴就行了，只有在最后递归的时候才会有区分。
2. 在最后递归的过程中，如果小于K的元素都在左面则直接递归左面即可，否则递归右面就可以把剩下的元素移到左面。
def quick(nums, l, r, k):if l >= r:returnx, i, j = nums[l], l - 1, r + 1while i < j:while True:i += 1if nums[i] >= x:breakwhile True:j -= 1if nums[j] <= x:breakif i < j:nums[i], nums[j] = nums[j], nums[i]# 注意从这里开始不同，j是左右的分界，# 如果j < k - 1说明比k小的数，还有在右面的，递归右面# 否则比k小的数都在左面，递归左面，让其有序即可，# 右面是否有序不用管了if j < k - 1:quick(nums, j + 1, r, k)else:quick(nums, l, j, k)n, k = list(map(int, input().split()))nums = list(map(int, input().split()))quick(nums, 0, n - 1, k)print(nums[k - 1])