内容：快速排序的递归/非递归实现代码及注解，思路详解，以及快速排序的优化
目录
快速排序的递归实现：
基本思想：
步骤：
让基准值排序到最终位置，使得左右区间自然分割开的方法有如下三种：
1 hoare版本
基本思想：
编辑动图演示：
一些细节：
代码实现：
2 挖坑法
基本思想：
动图演示：编辑
代码实现：
3 前后指针法
基本思想：
动图演示：编辑
代码实现：
4 三路划分法
基本思想：
编辑 三路划分法下的快速排序：
快速排序的递归优化：
三数取中法：挑选合适基准值
基本原理：
代码实现：
快速排序递归代码：
快速排序的非递归实现：
代码实现：
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法
快速排序的递归实现：
基本思想：
任取待排序元素序列中的某元素作为基准值（一般是取最左端or最右端or中间），先使得此基准值经过排序排到最终位置，然后按照该基准值将待排序集合分割成两子序列，左子序列中所有元素均小于或等于基准值，右子序列中所有元素均大于或等于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止
类似与二叉树的前序遍历，是否有种熟悉感？
步骤：
1 对当前区间的基准值进行排序，使其排到最终位置上，自然分割开小于or等于基准值的左区间
大于等于基准值的右区间
2 基准值无需动了，对它旁边的左区间进行递归，使左区间最终有序
对它旁边的右区间进行递归，使右区间最终有序
当然，左右区间的有序并不是一蹴而就的，而是递归按照同样的思路使其有序，即重复上述过程
让基准值排序到最终位置，使得左右区间自然分割开的方法有如下三种：
1 hoare版本
基本思想：
a 认定最左端作为基准值，记录基准值的下标（用于后面的交换）
b 右边先走，右边负责遍历找到一个小于基准值的元素（大于等于的直接跳过）
左边再走，左边负责遍历找到一个大于基准值的元素（小于等于的直接跳过）
c 将右边找到的一个小于基准值的元素与左边找到的一个大于基准值的元素互相交换
这样小于基准值的元素就被弄到左边了，大于基准值的元素就被弄到右边了
d 若区间仍有效，即left<right 则重复bc过程
e 当left==right，left或者right的位置就是基准值的最终排序位置了，将left下标/right下标的元素与基准值互换
动图演示：
一些细节：
1 最左边做基准值右边先走，保证了相遇位置的值比基准值要小or相遇位置就是基准值的位置
2 最右边做基准值左边先走，保证了相遇位置的值比基准值要大or相遇位置就是基准值的位置
原因：（以左边做基准值，右边先走为例分析）
相遇情况，无非就两种：L遇到R，R遇到L（以L代替left，R代替right）
L遇到R：说明R是停下来的，又因为R是先走的一方，故而R停下的位置的值一定是小于基准值的
L在移动，最终它两相遇，相遇在R停下来的位置，故而相遇位置的值小于基准值
R遇到L：说明L是停下来的，L在移动，那分两种情况：
情况1 L一直没有移动，L的位置就是基准值的位置
那么：R遇到L就是在基准值的位置相遇
情况2 L和R都是移动过的，在互相交换过一些轮次后，最终来到相遇的这一轮，
在双方还未移动时，L的值已经是交换过来的小于基准值的元素了
R的值已经是交换过来的大于基准值的元素了
由于R先走，又由于是R遇到L，那么它两相遇的位置就是L的位置
即相遇位置的值小于基准值
关于交换函数：
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
代码实现：
int PartSort1(int* a, int left, int right)//hoare版本：归位基准值，分割左右区间
{
int midi = GetMidIndex(a, left, right);//后面内容关于快速排序的优化：三数取中）
Swap(&a[left], &a[midi]);
int keyi = left;//基准值的下标
while (left < right)
{
while (left < right && a[right] >= a[keyi])//右边先走，右边找小于基准值的元素
{
right--;
}
while (left < right && a[left] <= a[keyi])//左边再走，左边找大于基准值的元素
{
left++;
}
Swap(&a[left], &a[right]);//将较小者交换到前面，较大者交换到后面
}
Swap(&a[left], &a[keyi]);//归位基准值
return left;//返回基准值的下标，用于分割左右区间，以便递归子区间
}
2 挖坑法
基本思想：
a 选取最左端为基准值，保存基准值，最左端成为了一个坑，用hole记录此坑的位置
那么我们就需要找小于基准值的元素来填左边的坑
b 右边找小于基准值的元素填到坑上，右边成为了一个坑，更新坑的位置，即hole的值
那么我们就需要找大于基准值的元素来填右边的坑
c 左边找大于基准值的元素填到坑上，左边成为了一个坑，更新坑的位置，即hole的值
d 循环bc过程，不断填坑
e 最终left==right，在坑位置相遇，因为left或者right是为坑的下标
将基准值填入坑中
动图演示：
代码实现：
int PartSort2(int* a, int left, int right)//挖坑法：归位基准值，分割左右区间
{
int midi = GetMidIndex(a, left, right);
Swap(&a[left], &a[midi]);
int key = a[left];//保存基准值
int hole = left;//坑的位置
while (left < right)
{
while (left < right && a[right] >= key)//右边找小于基准值的元素填补左边的坑
{
right--;
}
a[hole] = a[right];
hole = right;//右边的元素填补后自己成为坑
while (left < right && a[left] <= key)//左边找大于基准值的元素填补右边的坑
{
left++;
}
a[hole] = a[left];
hole = left;//左边的元素填补后自己成为坑
}
a[hole] = key;//最终left==right，相遇位置为坑，将基准值填入坑
return hole;//返回基准值下标
}
3 前后指针法
基本思想：
a 定义两个指针：prev，cur，选取最左端为基准值的位置，记录下来（用于后续交换）
prev初始化为left的位置，cur初始化为left+1的位置
b cur一直向前走，负责找到一个小于基准值的元素：
若是cur位置上的元素不是小于基准值的，那cur就不管，继续前进
若是cur位置上的元素是小于基准值的，那cur就停下来，完成与++prev，prev位置的值的交换
因为++prev位置的值是大于或等于基准值的，cur找到了小于基准值的，将二者互换，就是将较小者占了一个较大者的位置，同时将较大者挪至更靠后的位置
注意：当++prev==cur，没必要自己与自己交换
c 当cur遍历整个数组结束后，prev位置的值与基准值互换
因为当cur因为不断前进（一直忽略大于或者等于基准值的元素）而与prev拉开距离后，
cur和prev中间隔开的都是大于或者等于基准值的元素，prev位置的值是小于基准值的，
prev前面的元素都是包括自己在内都是小于或者等于基准值的，
prev后面的元素都是大于或等于基准值的，那么prev位置就可以成为一道分割线，
不正是基准值应该在的位置吗？，而且prev位置的值与基准值互换，也是把小的换到更前了
动图演示：
代码实现：
int PartSort3(int* a, int left, int right)//前后指针法：归位基准值，自然分割左右区间
{
int midi = GetMidIndex(a, left, right);
Swap(&a[left], &a[midi]);
int keyi = left;
int prev = left;
int cur = left + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev!=cur)//cur找到一个小于基准值的元素
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;//返回基准值归位后的下标
}4 三路划分法
hoare，挖坑法，前后指针法都是同类型的方法，相当于两路划分：
不管与基准值相同的元素，划分出来的左区间是小于等于基准值的，有区间是大于等于基准值的
但是要是对数组中全为同一元素的值进行排序，那快排就是O(n2)与冒泡排序一个级别的了非常慢
比如：222222222222222222222222222222
针对这种，我们衍生出了三路划分法，即小于基准值的在一个区间，等于基准值的在一个区间，大于基准值的在一个区间
基本思想：
1 三个指针 l、c、r，
l指针始终是指向与基准值相同的元素的
2 a[c]<基准值，交换l位置的值与c 位置的值，c++，l++
a[c]>基准值，交换r位置的值与c位置的值，r--（r可以向前走了，但是c指针不能，因为r交换过来给c位置的值是不确定的，所以还需要再判断一波）
a[c]==基准值，c++
3 最终l 到r的这段区间就全是与基准值相同的元素了，在快速排序算法中不需要递归这段区间
需要递归除这段区间之外的其他两个区间
三路划分法下的快速排序：
void QuickSort2(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int left = begin;
int right = end;
int cur = left + 1;
int key = a[left];
while (cur <= right)
{
if (a[cur] < key)
{
Swap(&a[left], &a[cur]);
left++;
cur++;
}
else if (a[cur] > key)
{
Swap(&a[right], &a[cur]);
right--;
}
else
{
cur++;
}
}
QuickSort2(a, begin, left - 1);
QuickSort2(a, right+ 1, end);
}
快速排序的递归优化：
三数取中法：挑选合适基准值
三数取中法很好优化了当数组是有序时，使用快排的效率，不会是O（n2）（冒泡排序一样）
因为数组有序时，基准值能划分出来的区间只有一半，另一半是不存在的，那此时递归的快排就和冒泡排序类似了
基本原理：
1 找最左端、最右端、中间位置的中间值，即三者之中一个不大不小的值
返回此中间值的下标的原因是：我想让此值作为基准值，交换到最左端，也可以是最右端，（因为我一般习惯将最左端作为基准值）
代码实现：
int GetMidIndex(int* a, int left, int right)
{
int mid = (left + right) / 2;//中间位置的值
if (a[left] < a[mid])
{
if (a[mid] < a[right])//mid位置的值是中间值
{
return mid;
}
else if (a[left] > a[right])//mid位置的值是最大值，那么中间值就是第二大的值
{
return left;
}
else
{
return left;
}
}
else
{
if (a[mid] > a[right])//mid位置的值是中间值
{
return mid;
}
else if (a[left] < a[right])//mid位置的值是最小值，那么第二小的值就是中间值
{
return left;
}
else
{
return right;
}
}
}再有一个优化就是当递归到较小的区间时，可以使用直接插入排序使得这个区间有序
快速排序递归代码：
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)//当递归区间仅有1个元素时这个区间已经有序了，区间不存在也无需递归
{
return;
}
int keyi = PartSort3(a, begin, end);//hoare、挖坑法、前后指针法均可
QuickSort(a, begin, keyi - 1);//递归基准值的左区间
QuickSort(a, keyi + 1, end);//递归基准值的右区间
}
递归结束的条件：begin>=end
区间不存在就无需递归了，比如
递归的区间仅有1个元素也无需让基准值归位了，它已经在最终位置了，也不需要递归了
快速排序的非递归实现：
非递归实现借助栈，栈可以模拟递归过程
快速排序递归的重点就是区间
模拟递归，就是处理区间的次序问题
快速排序的递归类似于二叉树的前序遍历，那我们借助栈先处理的就是左区间，然后是右区间
每处理一个区间，就要将它的左右区间进栈
代码实现：
void QuickSortNonR(int* a, int begin, int end)
{
ST st;
STInit(&st);//初始化栈
STPush(&st, end);//将原始区间入栈
STPush(&st, begin);//由于想要先得到区间的左下标，所以它后入栈
while (!STEmpty(&st))//每一次出一对区间下标，对此区间进行处理
{
int left = STTop(&st);
STPop(&st);
int right = STTop(&st);
STPop(&st);
int keyi = PartSort1(a, left, right);//将此区间的基准值归位
if (keyi + 1 < right)//想要先处理左区间，所以右区间先入栈
{
STPush(&st, right);
STPush(&st, keyi + 1);
}
if (left < keyi - 1)//左区间入栈
{
STPush(&st, keyi - 1);
STPush(&st, left);
}
}
STDestroy(&st);
}
完结撒花~
