快速排序
从名字可以看出是个速度很快的排序。快排说穿了就是确定主元的正确位置的过程，其余元素只关注分布是否正确，而不关注位置是否正确。
快排的实现原理：
快排利用双指针实现
首先确定一个主元（随机选择，但一般选择数组第一个元素；实际上快排不关心如何选取主元，但主元的选择确实关乎性能），然后low 、high指针分别指向头尾，从high开始，判断high指向的元素是否小于主元，若小于，则将该元素的值赋给low指向的位置（将小于主元的元素丢到数组左边），同时low向后移动一个单位，判断low指向的元素是否大于主元，若大于，则将该元素的值赋给high指向的位置（将大于主元的元素丢到数组右边）。如此反复，直到low和high指向同一位置，这就是主元的正确位置。这样将数组扫描一轮之后，主元就确定在了正确的位置，同时主元左边的元素都比它小，右边的元素都比它大
结合图解的具体过程可以参考https://blog.csdn.net/nrsc272420199/article/details/82587933
从数据结构上理解快排的时间复杂度O(n * log n)
快排可以看成构造一棵近似的完全二叉树的过程。每进行一次递归，树就生长一个高度。一般情况下，主元会把数组分成左右两部分，这样树的高度一般为log n，除非运气差到家，每一次找的主元都是最小值或最大值（这样每一个结点都只有左子树或者右子树，而非二叉）。因此一般认为需要递归log n次。而每一次需要遍历的次数都约等于n。因此快排的时间复杂度为O(n * log n)
如图，对乱序的0-9进行快排，快排过程形成了一棵树。树的每一层需要遍历的次数都约等于n，同时可认为递归了log2 N次，那么快排的时间复杂度为O(n * log n)
快排的核心代码实现如下
def fastSort(self, nums: List[int], low, high) -> int:
if low < high:
base = nums[low]
left = low
right = high
# 核心代码：3while
while left < right:
while left < right and nums[right] > base:
right -= 1
nums[left] = nums[right]
while left < right and nums[left] <= base:
left += 1
nums[right] = nums[left]
nums[left] = base
self.fastSort(nums, left+1, high)
self.fastSort(nums, low, left-1)
return
BFPRT算法
目的：求一个乱序数组中第i大的元素
常规思路或者说暴力思路：
排序后直接利用i取下标得到目标元素。就算利用快速排序，时间复杂度也至少是N*log N
有没有时间复杂度更小的方法？或者说，我们有没有什么方式优化上面的常规思路。有的
我们获取第i大的元素，只需要保证第i大的元素位置正确，不需要对这个元素两侧的元素做具体排序。这和快排的单次操作是一致的。所以，BFPRT算法从快排中诞生了
BFPRT算法的实现
- 将数组的n个元素每5个一组（取5好像是和cpu寄存器数量有关），划分为n/5组，有多的则多余元素为一组。每组排序后取出每个组的中位数
- 找出这些中位数的中位数，定为主元（如果第一步得到偶数个中位数，约定主元是较小的中位数）。
- 按主元对数组进行划分。假设主元是第k小的元素，那么有n-k个元素在划分的高区
- 如果i等于k，返回主元。如果i小于k，则在低区递归调用算法来找出第i小的元素。如果i大于k，则在高区递归查找第i-k小的元素
我们可以发现，BFPRT算法与快速排序的区别仅仅在于主元的选取方式不同，是优化的快排算法。BFPRT算法中，由于主元由中位数的中位数确定，因此主元更偏居中的位置，避免了快排中可能出现的最坏情况--即主元都在排序区间的边界
BFPRT算法，作为优化的快排，是在快排构造的近似完全二叉树的基础上进行剪枝。它的最坏情况是，总保留7/10 * n 的那一支，剪去3/10 * n 的那一支。这样，即使最坏的情况下，我们也不断有3/10的一支直接被剪掉，不需要任何操作，显然时间复杂度是比快排优的，即优于O(n * log n)
有人证明了BFPRT算法最差的时间复杂度也是O(n)，数学感觉比较复杂，这里不展开了。。。
