(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-07-03微信支付提示下单账户与支付账户不一致-icode9专业技术文章分享
- 2024-07-03微信支付提示订单号重复-icode9专业技术文章分享
- 2024-07-02微服务启动nacos注册上去了,但是一直没有收到请求-icode9专业技术文章分享
- 2024-07-02如何检查文件的编码格式-icode9专业技术文章分享
- 2024-07-02sublime 更改编码格式-icode9专业技术文章分享
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享