1.快速排序（递归）
快速排序是
Hoare
于
1962
年提出的一种二叉树结构的交换排序方法，其基本思想为：
任取待排序元素序列中
的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右
子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止
。
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyi = PartSort3(a, begin, end);
//[begin,keyi-1]keyi[keyi+1,end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
上述为快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉 树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
将区间按照基准值划分为左右两半部分的常见方式有：
1.
hoare
版本
2.
挖坑法
3.
前后指针版本
我来给大家讲解一下前后指针版本，因为这个代码简洁，但是不太好理解。
首先创建一个变量keyi保存left的值keyi=left，然后创建后指针prev开始也是在left位置prev=left，前指针cur在prev前一个位置cur=prev+1，，然后写一个while循环，结束条件是cur>right,意味着cur越界了，进入循环首先判断一下a[cur]和a[keyi]的大小，如果a[cur]大则再判断++prev是否等于cur，如果等于则不用交换，cur++,如果两个条件都满足则交换a[prev]和a[cur]，因为prev已经++，所以直接交换即可。循环结束之后再交换a[key]和a[prev].
cur的作用就是和prev拉开距离，然后将大于a[keyi]的值放到右边的部分，最后交换a[keyi]和a[prev]，就完成了部分排序。
int PartSort(int* a, int left, int right)
{
int keyi = left;
int prev = left, cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi] && (++prev) != cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[prev], &a[keyi]);
return prev;
}void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
return;
int keyi = PartSort3(a, begin, end);
//[begin,keyi-1]keyi[keyi+1,end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}2.快速排序优化
2.1三数取中
三数取中是取大小位于中间的值放到最左边，这样可以防止快排中最坏的情况出现O(n*2)，也就是要排序的这一组数据接近有序或者就是有序的情况，那么使用了三数取中后这种最坏的情况就变成了最好的情况.
//三数取中
int GetMidi(int* a, int left, int right)
{
int midi = (left + right) / 2;
if (a[left] < a[midi])
{
if (a[midi] < a[right])
{
return midi;
}
else if (a[right] < a[left])
{
return left;
}
else
{
return right;
}
}
else//a[left]>a[midi]
{
if (a[left] < a[right])
{
return left;
}
else if (a[midi] > a[right])
{
return midi;
}
else
{
return right;
}
}
}2.2小区间优化
当区间较小时可以使用插入排序来进行优化，因为插入排序最坏的情况就是要插入的数都比前面的数小，插入排序在小区间里面比较不错的一种排序算法，在快速排序里面使用插入排序可以提高很多的效率。
void QuickSort2(int* a, int begin, int end)
{
if (begin >= end)
return;
if ((end - begin + 1) > 10)
{
int keyi = PartSort3(a, begin, end);
//[begin,keyi-1]keyi[keyi+1,end]
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
else
{
InsertSort(a+begin, end - begin + 1);
}
}3.快速排序（非递归）
非递归的快速排序可以借助一个栈来实现，先入右边的值，再入左边的值，然后每次取值都是先取栈顶，也就是左边的值，然后再进行部分排序，直到返回的keyi-1=left,就代表着左边排序完成，右边返回的keyi+1=right,代表右边的部分排序完成。
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 = PartSort3(a, left, right);
if (keyi + 1 < right)
{
STPush(&st, right);
STPush(&st, keyi+1);
}
if (keyi - 1 > left)
{
STPush(&st, keyi-1);
STPush(&st, left);
}
}
STDestroy(&st);
}今天的分享到这里就结束了，感谢大家的阅读！
