目录
概述
思路
算法过程
quick_sort()
partition()
Code
优化方案
1.随机数优化
2.小区间插入优化
Code
复杂度
DLC
在上一篇文章中，我们介绍了三种基本的暴力排序：
他们的时间复杂度均为O(n²)级别。
在这篇文章，我们将介绍其中的第一个算法：冒泡排序的究极promax进化版：快速排序。
经过重重优化的冒泡排序几乎是最快的排序算法，可谓是从冒泡这个几乎最慢的排序彻底脱胎换骨。
我们先回想一下冒泡排序的算法过程：
在第i轮循环他总把第i大的数放在数组末尾。这带来的影响是什么？
那就是它的下一次循环的遍历范围比这次循环范围只小了1个数而已。
那如果我们不在第i轮循环找第i大的数会发生什么？
在一个大小为n的无序数组中，
假设我们在第一次循环能够把第k小中位数（或者一个很靠近中间的数）放在位置k上，也就是它在排好后的有序数组里所处的位置。
我们发现：只需要分别对它的左侧和右侧进行遍历就可以了，而这两次遍历的范围都至于都缩小到了n/2。
而他们又分别能使得第i小的数放在位置i上，第j小的数放在位置j上（0<=i<k<j<=n-1）。
我们发现：将这三个数（i,j,k）在乱序数组中排好序（即放在数组彻底有序时他们所应该在的位置），前三次遍历的范围是：n+n/2+n/2=2n。
而冒泡的前三次遍历的范围是： n+n-1+n-2=3n-3。
在n极其巨大，这个提升是极其显著的，并且，对于k所划分出的左右两个小区间，这两个小区间的首次遍历所划分出的小小区间也有这样的性质，一直可以递推到区间长度为1，它们都有这样的性质。
这就是分治。
这个过程往往依靠递归实现。
quick_sort()
我们给出函数quick_sort，它接收一个范围，它只干两件事：
①将这个范围中的一个数放在它应该在的位置
②这个数划分出的左右两个小范围传入quick_sort
*注意* :如果你首次接触递归，那么你应该认识到上一级quick_sort和下一级quick_sort并不是同一个函数，他们只是有相同的名字，执行相同的功能。
一直到小范围长度减少到1为止（1个数天生有序）。
在这里，我们用partition函数执行这个分区操作。
pos表示分区完成后某个已安放好的数所处的位置。
*注意*：根据代码语言传统，l和r往往是一个左闭右开区间，即[l,r），表示范围取到l，但取不到r。
partition()
我们给出函数partition()，它接收一个范围，它只干一件事：
在区间里找个数，给它安放好，然后返回安放位置。
一般我们把这个数称为pivot（基准数）。
朴素的快速排序直接选择第一个数当基准数。
我们这样理解安放基准数：那无非就是把比他大的数放在它右边，比它小的数放在它左边，只有左边范围和右边范围的内部是否有序，我不关心。
以同向双指针游走实现这件事：
先把要安放的基准数放在数组末尾，防止它干扰我们划分。（现在数组末尾就是基准数）
i和j一开始都指向范围内的第一个数：
①如果第一个数大于基准数，j前进，i不动，随后j发现的所有大于基准数的数，如此直到j发现了小于等于基准数的数：那就交换j指向的数和i指向的数，然后i前进一位，j继续往前走。
②如果第一个数小于等于基准数，那么i和j齐头并进继续走（在代码层面上其实这里一直在发生自己与自己交换），直到i和j指向的数比基准数大，j与i发生分离，i留下来维护这个数，j继续向前探索。
这样理解：
在一轮循环后，
i总是指向第一个大于基准数的数，i身后的数都小于等于基准数；
j总是指向未知区域的第一个数，j身后一直到i的范围是已经探明的比基准数大的数。
在j抵达基准数后，基准数被向前交换到了它需要被安放的位置。
注意此时由于i++，我们返回i-1。
Code
1.随机数优化
还记得快速排序是冒泡排序的究极promax进化版吗？它可是会退化的。
如果你选择的基准数总是区间最左侧的数，而整个数组本身相当有序，那么你的划分得到的左侧和右侧范围长度就是1和n-1。如此一来快排就退化回了冒泡。。
处理方法也很简单：在范围里随机取个数当基准数，而不是固定取最左边，这样就实现了随机分区函数。
关于C++标准库中的random文件的简单应用可参考：
2.小区间插入优化
最底层的quick_sort会调用大量的分区函数，而他们分区的范围却极小，这是不必要的，而且相当被动。
插入排序在小区间的表现要好于快速分区，当分区小到某个程度时，我们直接转发给插入排序。
Code
时间复杂度：O(nlogn)
空间复杂度：O(logn)
复杂度分析：
时间分析：{
在理想情况下，每次都正好实现了区域均分。
设总用时为T(n)，那么
T(n)=T(n/2)+T(n/2)+n。···①
（n为本次分区所用时间，两个T(n/2)为下一级的总时间）
注意到，
T(n/2)=T(n/4)+T(n/4)+n/2。···②，代入①得到：
T(n)=T(n/4)+T(n/4)+n/2+T(n/4)+T(n/4)+n/2+n
=4T(n/4)+2n
如此迭代得到：T(n)=2^mT(1)+mn
（m为迭代折半从n得到1的次数，即m=logn）
即T(n)=nT(1)+nlogn=n+nlogn，省去小量，得到O(nlogn)。
}
空间分析： {
在分割数组时，观察：
*注意*：同一层的每次小函数结束后空间会被释放，下次函数都会再次占据这块空间
空间复用使得每一层的复杂度都是O(1)，整体为O(logn) 。
}
百万数量级抗压测试
快速选择是快速排序的延伸算法，详见：