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