说明：参考书目为《Computer Algorithms --- Introduction to Design and Analysis》（第三版）Sara Baase, Allen Van Gelder
部分内容参考自大工林晓惠老师的课程【算法设计与分析】讲解。林老师讲算法非常细致，让人很容易理解，推荐一波~
（如部分内容涉及侵权，请联系我删除，谢谢）
之前的文章请见：
【算法设计与分析】如何分析一个算法
【算法设计与分析】4.1 插入排序
【算法设计与分析】(习题4.2-4.5) 冒泡排序
本篇文章目录
4.3 分治策略
1. 概念
2. 用分治法求解的条件
3. 步骤
4. 伪代码描述
4.4 快速排序
1. 定义
2. 排序过程示例
3. 算法代码
4. 分析 W(n), A(n)
5. 算法改进
1）pivot的选择
2）小排序问题
3）栈空间优化
将一个大问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
①小规模时，问题容易求解
②问题可以分解成若干个规模较小的相同问题，子问题的解可以合并为该问题的解
③子问题相互独立，即不包含公共的子问题
①划分（divide）:将原问题分解成若干规模较小、相互独立、与原问题形式相同的子问题。
②解决（conque）：若子问题规模较小，则直接求解；否则递归求解个子问题。
③合并（combine）：将各子问题的解合并为原问题的解。
solve(I) // 解决I问题的函数
n = size(I); // n是I这个问题的大小
if(n <= smallSize) // 问题规模小直接解决
solution = directlySolve(I);
else
divide I into I1,...,Ik. // 问题规模大划分成k个子问题
for each i in {1,...,k}:
Si = solve(Ii); // 递归调用
solution = combine(S1,...,Sk); // 合并k个子问题的解
return solution;每趟排序从待排序的数组中取一个值作为pivot，该趟排序后pivot左边的数全部<=pivot，pivot右边的数全部>pivot，由此将数组划分为<=pivot和>pivot两部分，对这两部分迭代地用上述方法继续排序，直到所有数据元素均排好序。（n个数据元素的排序经过n-1次比较，划分为2个与原问题形式相同的排序子问题）
注意：一次比较可能不止消除一对逆序
void QSort(Element[] E, int first, int last)
{
int t;
if(first < last)
{
t = partition(E, first, last);
QSort(E, first, t-1);
QSort(E, t+1, last);
}
}
int partition(Element[] E, int first, int last)
{
E[0]=E[first]; // 此种方法选择待排序数组的第一个元素作为pivot
while(first<last)
{
while((first < last) && (E[last] >E[0])) last--;
if (first < last)
{
E[first]=E[last];
first++;
}
while((first < last) && (E[first]<=E[0])) first++;
if(first < last)
{
E[last]=E[first];
last--;
}
}
E[first]=E[0];
return first;
}空间：使用快速排序时，会将待排序的子数组放入栈中，栈的大小取决于划分的子数组大小。在最坏情况下，空间复杂度就是
时间：
1）最坏情况：【待排序的数组已经是升序，如果每次取子数组的第一个元素作为pivot，那么数组每次都会被划分为含有0个元素的左区域和n-1个元素的右区域】
推理过程如下图 ↓
2）平均情况：
假定所有划分情况都是等可能的，
目前A(n)只是一个递推公式，我们需要进一步得到以n为自变量的公式，才能得到A(n)的时间复杂度。
现在有两种方法可以求解A(n)：①先猜A(n)的估计值，然后证明这个值；②直接推理计算
方法①：
首先估计一下A(n)大致的公式： 第一个n是划分需要的比较次数；假设每一次划分都得到两个大小一样的子域 -> 2Q(n/2)
根据定理3.17可以估计出，具体推导过程如下图 ↓
根据上面我们的估计，可以做出如下假设（同时也是书中定理4.2）：
接下来使用数学归纳法证明A(n)<=cnlnn：
因为，所以有推论4.3：平均来说，假设所有输入是等概率的，那么在大小为n的序列上使用快速排序所需的比较次数大概是1.386nlgn（n足够大）。
方法②：
为了避免最坏情况的发生，即选择的pivot是当前数组最大或最小值，我们需要改变选择pivot的策略：
①随机选择
②在E[first]，E[last]和E[(first+last)/2]这三个数中取中值
因为快排采用递归的方式排序，当待排序数较少时，递归调用函数就比直接迭代排序（如插入排序）的开销大。所以在排序数较少时，可以采用插入排序。
设待排序数<=smallSize时为小排序，有两种情况涉及到小排序：
①原本待排序数<=smallSize
②经过快排的分治策略，将原数组不断划分，子数组的大小<=smallSize
// 针对小排序问题，修改原递归程序
void QSort(Element[] E, int first, int last)
{
int t;
if(last - first > smallSize)
{
t = partition(E, first, last);
QSort(E, first, t-1);
QSort(E, t+1, last);
}
else
{
smallSort(E, first, last); // 小排序使用的排序方法（如插入排序）
}
}在递归调用时，会将子数组存入栈中，如果子数组过大，栈所需空间过大，频繁做pop或push的压力大。
因此改进算法：①原本两个递归只保留第一个（由于第二个递归的代码位于程序的最后一行，所以依照前面插入排序的shiftVac将递归改为迭代 → 用while循环处理）
②每次递归处理的比迭代处理的子数组要小
quickSortTRO(E, first, last)
int first1, last1, first2, last2, t;
first2 = first; last2 = last;
while(last2 - first2 > 1)
t = partition(E, first2, last2);
if(t < (first2 + last2) / 2)
first1 = first2; last1 = t - 1;
first2 = t + 1; last2 = last2;
else
first1 = t + 1; last1 = last2;
first2 = first2; last2 = t - 1;
quickSortTRO(E, first1, last1); // first1->last1是递归部分，即子数组中较小的部分
return;