(C++)归并排序的递归与非递归实现
2021/7/27 22:07:33
本文主要是介绍(C++)归并排序的递归与非递归实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
递归实现
merge函数利用的是双指针技巧降低复杂度。
mergeSort函数使用了递归,当中先对左右序列各调用一次mergeSort,再对整个序列调用merge。就按照最浅层的归并的思想去理解,不要大脑走到哪就step in。
另外mergeSort进入递归有个left<right的判定容易漏写。
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 10; const int INF = 1000000000;//INF:下确界 const LL SUP = (1LL<<63)-1;//SUP:上确界 const double eps = 1e-5; LL Map[128]; void merge(int A[],int L1,int R1,int L2,int R2){ int i=L1,j=L2; int temp[maxn]; int index = 0; while(i<=R1&&j<=R2){//是≤不是< if(A[i]<=A[j]){ temp[index++] = A[i++]; }else{ temp[index++] = A[j++]; } } while(i<=R1)temp[index++] = A[i++];//这个while很容易写成if while(j<=R2)temp[index++] = A[j++]; for(int i=0;i<index;i++){ A[L1+i] = temp[i]; } } void mergeSort(int A[],int l,int r){//递归实现的归并排序 if(l<r){ int mid = (l+r)/2; mergeSort(A,l,mid); mergeSort(A,mid+1,r); merge(A,l,mid,mid+1,r); } } int main(){ int A[maxn] = {66,12,33,57,64,27,39,66,78,66}; mergeSort(A,0,maxn-1); for(int i=0;i<maxn;i++){ printf("%d ",A[i]); } return 0; }
非递归实现
基础的归并函数sort是一样的,但感觉非递归道理容易想明白但是实现起来细节多。注意两个for和一个if的<n不能写成<=n
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<bits/stdc++.h> using namespace std; typedef long long LL; const int maxn = 10; const int INF = 1000000000;//INF:下确界 const LL SUP = (1LL<<63)-1;//SUP:上确界 const double eps = 1e-5; LL Map[128]; void merge(int A[],int L1,int R1,int L2,int R2){ int i=L1,j=L2; int temp[maxn]; int index = 0; while(i<=R1&&j<=R2){//是≤不是< if(A[i]<=A[j]){ temp[index++] = A[i++]; }else{ temp[index++] = A[j++]; } } while(i<=R1)temp[index++] = A[i++];//这个while很容易写成if while(j<=R2)temp[index++] = A[j++]; for(int i=0;i<index;i++){ A[L1+i] = temp[i]; } } void mergeSort(int A[],int n){//非递归实现的归并排序 //step为组内元素个数(每归并一次乘二) for(int step=2;step/2<n;step*=2){ //每step个元素一组,组内左一半step/2和右一半step/2的元素合并,注意有很多个这样的组 for(int i=0;i<n;i+=step){ int mid = i+step/2-1;//step/2为左子区间元素个数 if(mid+1<n){//右子区间存在元素则合并 merge(A,i,mid,mid+1,min(i+step-1,n)); } } } } int main(){ int A[maxn] = {66,12,33,57,64,27,39,66,78,66}; mergeSort(A,maxn); for(int i=0;i<maxn;i++){ printf("%d ",A[i]); } return 0; }
这篇关于(C++)归并排序的递归与非递归实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解