前提
快排的递归实现,在深度过深时会存在栈溢出的风险,所以我们需要掌握快排的非递归写法
快排的实现
单趟实现
上次我们使用了hoare的快排单趟写法,所以这次我们使用前后指针法.
前后指针法
初始状态下,初始化prev为left,cur为left+1,循环结束条件为cur <= right. 如果cur的值小于keyi,则cur与prev均向后移动,并且交换prev与cur的值;如果比keyi大,则cur向后移动.,同时,为防止prev与cur相等时交换,要写这样一句:
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
cur++;//无论如何cur都要加加往后移动
最后实现左边都比keyi小,右边都比keyi大. 实现代码如下:
int PartSort2(int* a, int left, int right)
{
int keyi = left;
int prev = left;
int cur = prev + 1;
//挖坑法
while (cur <= right)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[prev], &a[cur]);
cur++;//无论如何cur都要加加往后移动
}
Swap(&a[prev], &a[keyi]);
return prev;//单趟结束
}
多趟实现
对于非递归实现,我们一般使用栈存储(属于深度优先遍历). 原理是:循环每走一次取栈顶区间,右左区间入栈. 每次入栈相当于递归的过程:每次入栈都会对左右区间进行单趟排序. 代码实现如下:
//快排非递归(递归深度太可能会栈溢出)
//用栈存储
#include "Stack.h"
void QuickSortNonR(int* a, int left, int right)
{
ST st;
STInit(&st);
STPush(&st, &left);
STPush(&st, &right);
while (!STEmpty(&st))
{
int begin = STTop(&st);
STPop(&st);
int end = STTop(&st);
STPop(&st);
int keyi = PartSort2(a, begin, end);
//分成三段区间[begin, keyi - 1] keyi [keyi + 1, end]
//先处理右区间
if (keyi + 1 < end)
{
STPush(&st, end);
STPush(&st, keyi + 1);
}
//再处理左区间
if (begin < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, begin);
}
}
STDestroy(&st);
}