欢迎来到 Claffic 的博客 💞💞💞

前言： 

快速排序已经带大家实现过了，我们用到的方法是递归法，你知道吗，用循环也可以实现快速排序，来看看吧。

注：

这篇博客属于数据结构内容，建议学习完C语言的小伙伴食用~

目录

🐯1.快排回顾

🦁2.非递归思想

🐮3.实现

1.快排回顾

还记得递归版的快速排序是怎么实现的吗？ 

默认使用前后指针法：
 

代码实现：

//快排(前后指针法)
void QuickSort3(int* a, int left, int right)
{if (left >= right)return;//三数取中int midi = GetMidi(a, left, right);if (midi != left)Swap(&a[midi], &a[left]);int keyi = left;int key = a[left];int prev = left;int cur = left + 1;while (cur <= right){if (a[cur] < key && ++prev != cur)Swap(&a[cur], &a[prev]);cur++;}Swap(&a[keyi], &a[prev]);//与下标为keyi的交换keyi = prev;//递归QuickSort3(a, left, keyi - 1);QuickSort3(a, keyi + 1, right);
}

在代码末尾进行了递归操作，那么非递归如何实现呢？ 

2.非递归思想

要想用非递归实现排序，我们首先要观察递归是如何实现的： 

不变的是一趟中数字的交换逻辑，

变化的是需要进行 调整的区间 ；

我们从变化的入手：

可以看到，调整的区间在变化(紫色标号)；

也就是说，我们可以在循环中 存储要调整的区间 ，用到时再取出来；

这个有先入后出的特点，可以选择栈来实现。

那么如何模拟返回条件呢？

递归版是一个数字的时候就返回，那么非递归版就可以是子区间有一个值或者没有值就不把区间入栈。

思路总结：

• 栈里面取一段区间，单趟排序；

• 单趟分割子区间入栈；

• 子区间只有一个值或者不存在就不入栈。

3.实现

void QuickSortNotR(int* a, int left, int right)
{Stack ST;StackInit(&ST);StackPush(&ST, right); // 先入右，再入左，才能先出左，再出右。StackPush(&ST, left);while (!StackEmpty(&ST)){// 取出区间int begin = StackTop(&ST);StackPop(&ST);int end = StackTop(&ST);StackPop(&ST);// PartSort3返回是快速排序的keyi值int keyi = PartSort3(a, begin, end);//[begin,keyi-1] keyi [keyi+1,end]//满足非一零就出栈if (keyi + 1 < end){StackPush(&ST, end);StackPush(&ST, keyi + 1);}if (begin < keyi - 1){StackPush(&ST, keyi - 1);StackPush(&ST, begin);}}StackDestroy(&ST);
}

代码已上传至 我的gitee 

拿走不谢~

总结： 

这篇博客内容比较简单，就是仿照递归版本实现了非递归的快速排序。

码文不易 

如果你觉得这篇文章还不错并且对你有帮助，不妨支持一波哦  💗💗💗