餐饮网站开发背景,快猫,宁波网站关键词排名推广,烟台seo管理#x1f308;个人主页#xff1a;Yui_ #x1f308;Linux专栏#xff1a;Linux #x1f308;C语言笔记专栏#xff1a;C语言笔记 #x1f308;数据结构专栏#xff1a;数据结构 文章目录 1 快速排序非递归2. 归并排序3.排序算法复杂度及稳定性分析 1 快速排序非递归
利…个人主页Yui_ Linux专栏Linux C语言笔记专栏C语言笔记 数据结构专栏数据结构 文章目录 1 快速排序非递归2. 归并排序3.排序算法复杂度及稳定性分析 1 快速排序非递归
利用迭代的方式来模仿递归快速排序递归的本质也就是它可以拿到那些待排序的区间那么不就说明了只要我们右那些待排序的区间就可以不再需要递归了。 为此我们只需要用一个容器来存储这些区间就可以了在众多的数据结构中我选择利用栈来实现这个方法如果你要用队列也可以只是存储区间而已。那么如何获取这些区间呢 正常情况我们只有整个数组的区间然后我们对这个区间排序拿到基准值后新的区间就又出现了新的区间就是区间的左端到该基准值-1的位置即[left,key-1],同理另一个就是[key1,right]。好像和递归差不多每次就是差不多快速排序的逻辑是不会变的我们只把原来的递归处理改成了迭代。 将区间保存到栈中可以写一个结构体也可以直接传取出时也一次取两个就可以了不影响的。
//非递归版本
void QuickSortNonR(int* a, int begin, int end)
{stack s;InitStack(s);//先入left再入rightPushStack(s, begin);//注意传入区间的顺序与取出时相反PushStack(s, end);while (!EmptyStack(s))//只要栈不为空就继续循环{int right TopStack(s);PopStack(s);int left TopStack(s);PopStack(s);int mid PartSort1(a, left, right);//此处调用的是hoare法其他法都可以if (mid 1 right)//保证区间的有效性{PushStack(s, mid 1);PushStack(s, right);}if (left mid - 1)//保证区间的有效性{PushStack(s, left);PushStack(s, mid - 1);}}DestoryStack(s);
}快速排序的总结
快速排序整体的综合性能和使用场景都是比较好的所以才敢叫快速排序时间复杂度O(N*logN)空间复杂度O(1)稳定性不稳定
2. 归并排序
基本思想 归并排序MERGT-SORT是建立在归并操作上的一种有效的排序算法该算法是采用分治Divide and Conquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。归并排序核心步骤
合并时的动图
其实归并排序很简单像分解的过程不是和快速排序很像嘛都是传数组和区间。不同的是因为快速排序是确定基准值因为基准值已经到了它排序后的最终位置后续传区间就是基准值的左右区间但是归并排序可不是这样的归并排序是直接找数组的中间下标然后将数组一分为二这样的话也就表示了再这过程中是中间元素是不会到达最终位置所以我们的区间要包括中间元素。 后序关于合并的问题就更简单了在链表期间我们就应该写过一个合并两个有序链表的问题这个和那题是没有本质区别的逻辑都在两个区间中找小找到后将较小的数据取出然后移动找到小数据那边的指针最后当比较完毕后大概会有一个区间没有走完我们只要再把那个没有走完数据的区间取出即可。
void _MergeSort(int* a, int* tmp, int begin, int end)
{//确定递归出口if (begin end)return;int mid (begin end) / 2;//划分数组将数组一分为二//以下为分解逻辑_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid 1, end);//以下为合并逻辑int begin1 begin,end1 mid;int begin2 mid 1, end2 end;int index begin;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])tmp[index] a[begin1];elsetmp[index] a[begin2];}//处理剩余元素while (begin1 end1)tmp[index] a[begin1];while (begin2 end2)tmp[index] a[begin2];//将临时数组存放的数据重新复制到原数组memcpy(a begin, tmp begin, sizeof(int) * (end - begin 1));}void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);//临时数组存放合并时的数据if (tmp NULL){perror(malloc);exit(-1);}//归并排序的核心逻辑再封装一个函数来实现_MergeSort(a, tmp, 0, n - 1);
}归并排序的特性总结
归并排序缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定
3.排序算法复杂度及稳定性分析
