网站开发维护前景,wordpress部分内容加密,重庆公司团建推荐,印象笔记 wordpress目录
序列文章
前言
学前补充
非递归快速排序
注意事项#xff08;重要#xff09;
实现步骤
代码实现
时空复杂度
快速排序的特性
栈的相关代码 序列文章
非递归实现的快速排序#xff1a;http://t.csdnimg.cn/UEcL6
快速排序的挖坑法与双指针法#xff1a;ht…目录
序列文章
前言
学前补充
非递归快速排序
注意事项重要
实现步骤
代码实现
时空复杂度
快速排序的特性
栈的相关代码 序列文章
非递归实现的快速排序http://t.csdnimg.cn/UEcL6
快速排序的挖坑法与双指针法http://t.csdnimg.cn/I1L7Q
快速排序的hoare法http://t.csdnimg.cn/SV0nA
前言 一般来说我们在写排序时都比较喜欢使用递归的方式但是递归如果层次太深可能会引起栈溢出的问题所以我们在本篇会讲解如何使用非递归的方式实现快速排序\(︶*\))
学前补充
对于递归改非递归我们其实已经不是第一次写了比如斐波那契数列中的递归改非递归
//递归实现斐波那契数列
#include stdio.h
int count 0;
int Fid(int n)
{if (n 0)return 0;else if (n 1)return 1;elsecount;return Fid(n - 1) Fid(n - 2);}int main()
{int n 0;printf(请输入要求第几个斐波那契数列中的数字);scanf_s(%d, n);int ret Fid(n);printf(该数字为%d\n, ret);printf(需要计算的次数为 %d\n, count);return 0;
}//迭代循环实现斐波那契数列
#include stdio.h
int count 0;
int Fun(int n)
{int a 1;int b 1;int c 1;while (n 2) //当n2时开始进行循环相加{c a b;a b;b c;count;n--;}return c; //当n2时直接输出1}int main()
{int n 0;printf(请输入要求第几个斐波那契数列中的数字);scanf_s(%d, n);int num Fun(n);printf(该数字为%d\n, num);printf(所需要的次数为%d,count);return 0;
}我们会发现可以实现递归改迭代的问题它们使用迭代实现的思路会比递归更加的好理解所以一般来说我们在进行递归改非递归的过程中会将递归改为迭代的形式。 但是对于快速排序而言我们会利用栈来将它改为非递归的方式而不是迭代这是因为在快速排序中每次划分操作会将原始数组划分为两个较小的子数组。然后我们需要对这两个子数组进行进一步的划分和排序。这种嵌套关系导致了一个逻辑上的函数调用链。 使用循环来实现非递归版本时我们无法直接模拟出函数调用链中各级函数之间传递参数和保存局部变量等信息的机制。而通过使用栈数据结构在每次遇到新的待处理子数组时我们可以将相关信息如起始索引、结束索引压入栈中并在下一轮迭代时从栈中弹出并取出相应信息进行处理。 换句话说通过利用栈作为辅助数据结构在代码层面上模拟了逻辑上函数调用链所需传递和保存状态信息等功能。这样就能够以迭代方式按照特定顺序处理所有待处理子问题即待切割和排序的子数组达到完成整体排序任务。 结论在非递归实现快速排序算法时选择使用栈来管理状态信息是一种常见且有效的策略
非递归快速排序
注意事项重要 我们利用栈存储的是每次要进行排序的数组元素的下标的值而不是该数组元素的值我们会将这些下标代入到之前实现过的单趟的快速排序中比如伪双指针法快速排序每次循环都进行一次单趟排序这样就可以不再像递归那样排序时需要借助栈帧
实现步骤
1、将数组首尾元素下标0和9入栈将栈顶元素分别赋值给变量left和right后栈顶元素出栈赋值一个出一个一共四步入-出-入-出将作left和right传入快速排序其实就是begin和end实现单趟排序
2、将单趟排序后形成的左区间和右区间的四个下标值入栈单趟排序返回的是作为分界线元素的下标的值 3、后续入栈出栈过程不予解释建议自行理解
代码实现
//非递归排序
void QuickSortNonR(int* a, int begin, int end)
{//初始化栈ST s;STInit(s);//将数组首尾元素的下标的值作为x入栈STPush(s, end);STPush(s, begin);//栈不为空就循环while (!STEmpty(s)){//获取栈顶元素值原数组中的下标并让栈顶元素出栈获取完此时的栈顶元素就出获取两个栈顶元素就开始排序int left STTop(s);STPop(s);int right STTop(s);STPop(s);//将获取的两个下标值进行单趟排序利用之前的伪双指针法int keyi PartSort3(a, left, right);// [left, keyi-1] keyi [keyi1, right]//当左区间范围不为1时没法继续缩小问题规模将划分后左区间两个边界位置元素的下标值入栈if (left keyi - 1){STPush(s, keyi - 1);STPush(s, left);}//当右区间范围不为1时没法继续缩小问题规模将划分后右区间两个边界位置元素的下标值入栈 if (keyi 1 right){STPush(s, right);STPush(s, keyi 1);}}//最后销毁栈空间STDestroy(s);
}
时空复杂度 最坏时间复杂度ON^2当输入数组完全有序时每次切分操作都可能将数组分为一个较小的部分和一个较大的部分导致每次切分只能减少一项 最好时间复杂度ON*logN每次划分都能将数组均匀地分成两个接近子数组N个元素要进行logN次的排序N*logN跟前面的递归排序的意思差不多 空间复杂度OlogN不需要额外的栈空间来保存状态信息只需维护一个辅助堆栈用于存储待处理子数组的起止索引即可 快速排序的特性 快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序 稳定性不稳定 栈的相关代码
代码太多就不再全部展示了需要的自提http://t.csdnimg.cn/kheGO
~over~
