1 / 4
文档名称:

归并排序及逆序对数.doc

格式:doc   大小:25KB   页数:4页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

归并排序及逆序对数.doc

上传人:xunlai783 2018/11/15 文件大小:25 KB

下载得到文件列表

归并排序及逆序对数.doc

相关文档

文档介绍

文档介绍:归并排序介绍
归并排序是一种稳定的排序方法,时间复杂度O(n log(n)),主要思路是递归实现,把数组a[] ,分成两部分,分别进行排序,然后从新排序的两个(其中实现的时候用一个子数组就搞定了,这是个牛X的地方)子数组中取较小的数放入保存最后结果的数组中。核心思想:就是把两个已经排好的数组合成一个排序的数组。(显然是递归了)
归并排序的代码实现:
代码一:
#include<iostream>
using namespace std;
int Sort(int a[],int merge[],int low,int high)//把a中的值排序到merge中
{
int b[100];//这是个temp局部值,它能保存两个半区
int mid=(high+low)/2;
int i=low,j=mid+1,k=low;
/////////////////////////////////////////////////////////////////////////////////////
if(low>=high) //递归出口
{
if(low==high) merge[low]=a[low];
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////
Sort(a,b,low,mid); //分成两个子数组,进行排序
Sort(a,b,mid+1,high);
/////////////////////////////////////////////////////////////////////////////////////
while((i<=mid)&&(j<=high)) //进行合并操作
{
if(b[i]<=b[j])
{
merge[k++]=b[i++];
}
else
{
merge[k++]=b[j++];
}
}
while(i<=mid)
{
merge[k++]=b[i++];
}
while(j<=high)
{
merge[k++]=b[j++];
}
return 0;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
int a[]={3,1,4,5,2,7,9,8,10};
int merge[100];
Sort(a,merge,0,8);
for(int i=0;i<9;i++)
cout<<merge[i]<<endl;
return 0;
}
代码2
其实,该算法是递归排序中套一个合并(merge),所以可以改成两个函数,一个是merge_sort(),一个是merge() 。这样代码分割比较好:
#include<iostream>
using namespace std;
void merge(int a[],int lo

最近更新

国培送教下乡培训总结优秀(5篇) 15页

夏洛的网600字心得 6页

婚内出轨补偿协议(3篇) 10页

学前班下学期教学计划四篇 9页

2025年糖尿病眼病预防与视网膜病变关注 22页

2025年病毒性脑炎护理实战解析王金芬深度探讨.. 55页

2025年牲畜繁殖系统解析 93页

2025年抑郁症防治知识普及讲座 14页

2025年慢性中耳炎反复发作治疗攻略 34页

2025年心脏冠状动脉疾病入门解读 21页

2025年RECIST实体瘤疗效评估革新指南 19页

2025年宝宝贫血预防与改善攻略 28页

2025年守护脊柱健康脊椎保养的必读攻略 34页

2025年孕期有害物质影响与胎儿畸形风险 69页

二零二五年度企业年会宣传册设计印制合同 9页

二零二五年度企业宣传片配音与字幕翻译合同 9页

二零二五年度企业增资补充协议书——跨境电商.. 7页

二零二五年度企业员工长期借款协议 8页

二零二五年度企业员工租赁车辆使用管理办法 8页

二零二五年度企业员工培训与发展咨询服务全面.. 9页

二零二五年度企业员工入股股权激励与绩效考核.. 7页

2025年华彩集团财务管理体系深度解析与优化策.. 31页

二零二五年度企业医院体检健康风险评估合同 9页

二零二五年度企业内部管理免责合同 7页

二零二五年度企业内部员工晋升及招聘合同 8页

最新部编版三年级下册语文全册教案 106页

2级经销商分销协议 5页

村后备干部笔试试题及答案 5页

土地整理项目技术交底教学内容 4页

中医技能知识考试题+答案 20页