快速排序的递归展开图
了解了快速排序的工作原理，独立画出它的递归展开图有助于了解它的工作原理
快速排序的优化
快速排序确实是在很多方面都很优秀的排序，但是仅仅用上述的代码并不能完全解决问题，假设现在给的序列是一个按升序排列的序列，那么此时我们选取的key是最小的数据，时间复杂度是O(N^2)，但如果每次选取的数据恰好是中位数，那么就是整个数据最高效的方式，时间复杂度是O(NlogN)，因此如何优化？
常见的优化有三数取中法和递归到小的子区间选取插入排序法
三数取中法
顾名思义，就是取开头，末尾和中间的三个数，选这三个数中最中间的一个，让这个数作为key
int GetMid(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[left] > a[right])
{
return left;
}
else
{
return right;
}
}
else // a[left] > a[midi]
{
if (a[midi] > a[right])
{
return midi;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
int PartSort1(int* a, int left, int right)
{
int midi = GetMid(a, left, right);
Swap(&a[midi], &a[left]);
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[keyi], &a[left]);
return left;
}
int PartSort2(int* a, int left, int right)
{
int midi = GetMid(a, left, right);
Swap(&a[midi], &a[left]);
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;
return hole;
}
int PartSort3(int* a, int left, int right)
{
int midi = GetMid(a, left, right);
Swap(&a[midi], &a[left]);
int cur = left+1;
int prev = left;
int keyi = left;
while (cur <= right)
{
if (a[cur] < a[keyi])
{
++prev;
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 = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
快速排序的非递归实现
快速排序是利用递归实现的，而凡是递归就有可能爆栈的情况出现，因此这里要准备快速排序的非递归实现方法
非递归实现是借助栈实现的，栈是在堆上malloc实现的，栈区一般在几十Mb左右，而堆区有几G左右的空间，在堆上完成操作是没有问题的
当left<keyi-1才会入栈，当keyi+1<right才会入栈
随着不断入栈出栈，区间划分越来越小，left最终会等于keyi-1，这样就不会入栈，右边同理，不入栈只出栈，最终栈会为空，当栈为空时，排序完成
