前言：
快速排序已经带大家实现过了，我们用到的方法是递归法，你知道吗，用循环也可以实现快速排序，来看看吧。
注：
这篇博客属于数据结构内容，建议学习完C语言的小伙伴食用~
目录
🐮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); }
总结：
这篇博客内容比较简单，就是仿照递归版本实现了非递归的快速排序。
