快排的非递归实现
其思想与递归实现快排完全相同,可以先将第一次要排序的右边界和左边界先后入栈,然后判断栈
是否为空,不为空就出栈顶元素,并删除一次,由于栈是先进的后出,所以先出来的应该是左界,
再进行一次取出栈顶元素,并删除一次,从而得到右边界,让后执行快排的单趟排序(返回元素为
排好序的那个元素的下标),同过返回的下标将数组分为两部分,再分别让这两部分的左边界和右
边界先后入栈,再进行判断栈空,形成循环。
1.先将第一次要排序的右边界和左边界先后入栈
入栈元素:8,6
2. 进行两次出栈,并删除
出栈元素:6,8
3.执行单趟排序,执行后数组如下:
4.将两组新的左边界和右边界进行入栈,先入右边界,后入左边界
入栈元素:8,9,4,3
5. 栈不为空,继续循环
接下来给出每一步的代码:
1.先将第一次要排序的右边界和左边界先后入栈
ST st;STInit(&st);STPush(&st, right);STPush(&st, left);
2. 进行两次出栈,并删除
int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);
3. 执行单趟排序,执行后数组如下:
int keyi = PartSort3(a, begin, end);
4.将两组新的左边界和右边界进行入栈,先入右边界,后入左边界
if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}
5.循环体:
while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort3(a, begin, end);if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}
整体代码(一定要在最后销毁栈):
//非递归快排(栈实现)
void QuickSortNoneR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort3(a, begin, end);if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestory(&st);
}