重写二路归并排序
2019-09-23 08:42:04来源:博客园 阅读 ()
重写二路归并排序
利用两个数组互相作为对方的辅助数组来实现,先二路划分,再从单个元素开始归并。代码如下:
/* 二路归并排序,采用了递归的做法,它首先将整个队列划分为两个部分,再一次对这两个部分进行二分操作, 直到每个部分只包含一个元素为止,然后再依次对这些只包含一个元素的部分开始进行归并,然后递归操作会依次向上 进行回溯,最后返回已排好序的队列,排序完成。 时间复杂度n*log2n */ #include <iostream> using namespace std; void merge(int * b,int * t,int s,int mid,int e){ int i=s; int j=mid+1; int idx=s; while(i<=mid&&j<=e) { if(b[i]<b[j]) { t[idx++]=b[i++]; } else { t[idx++]=b[j++]; } } while(i<=mid) { t[idx++]=b[i++]; } while(j<=e) { t[idx++]=b[j++]; } } void TwoGuiBing(int * a,int * t,int s,int e){ if(s==e) { t[s]=a[s]; return; } int mid=(s+e)/2; TwoGuiBing(t,a,s,mid); TwoGuiBing(t,a,mid+1,e); merge(a,t,s,mid,e); for(int i=s;i<=e;i++) { cout<<t[i]<<" "; //a[i]=t[i]; } cout<<endl; } int main(){ int s[10]={4,1,5,2,4,3,98,6,65,1};//1 1 2 3 4 4 5 6 65 98 int t[10]; for(int i=0;i<10;i++) { t[i]=s[i]; } TwoGuiBing(s,t,0,9); for(int i=0;i<10;i++){ cout<<t[i]<<" "; } cout<<endl; return 0; }
原文链接:https://www.cnblogs.com/JsonZhangAA/p/11566241.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 序列归并 2020-02-19
- MergeSort(归并排序)原理及C++代码实现 2020-01-14
- QRowTable表格控件(五)-重写表头排序、支持第三次单击恢复默 2019-09-17
- 论分治与归并思想 2019-08-16
- 洛谷 P1908 2019-08-16
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash