脚本宝典收集整理的这篇文章主要介绍了【数据结构】快速排序非递归实现,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
常见的排序算法有以上八种,点击专栏就可以看其他排序算法,感兴趣的朋友们不妨点个收藏专栏。 ღ( ´・ᴗ・` )比心
OJ链接
快速排序的非递归实现可以使用 队列 和 栈进行。使用 队列 类似于 二叉树的层序遍历F1b;使用 栈 类似于 二叉树的前序遍历。
本文采用栈进行非递归实现。
根据栈先入后出的特点,用栈实现快速排序非递归分为以下过程:
在一次单趟排序后,右区间、左区间依次入栈。
栈中数据:
取栈顶元素,进行单趟排序,依次压入右区间和左区间。
依次循环,直到左右区间不满足条件。
void QuicksortNonR(int* a, int left, int right)
{
// 栈
ST st;
StackInIT(&st);
StackPush(&st, left);
StackPush(&st, right);
while (!StackEmpty(&st))
{
int end = StackTop(&st);
StackPop(&st);
int begin = StackTop(&st);
StackPop(&st);
// 单趟排序
int keyi = PartSort3(a, begin, end);
// 先入右区间
if (keyi + 1 < end)
{
StackPush(&st, keyi + 1);
StackPush(&st, end);
}
// 再入左区间
if (begin < keyi - 1)
{
StackPush(&st, begin);
StackPush(&st, keyi - 1);
}
}
StacKDEstroy(&st);
}
注:此处栈是用先前用C自己实现的栈功能。
以上是脚本宝典为你收集整理的【数据结构】快速排序非递归实现全部内容,希望文章能够帮你解决【数据结构】快速排序非递归实现所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。