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

最近更新

关于创造良好的建筑创作环境讨论(摘要) 2页

关于农产品成本调查分析中的几个问题 2页

关于六氢邻苯二甲酸环氧合成的研究 2页

关于优化我国固定资产投资规模的思考 2页

《新会计准则介绍》 116页

2025年晚期癌症的舒缓治疗策略 33页

2025年探讨肱骨远端骨折治疗经验 62页

2025年护理职业规范与技能提升培训 89页

关于CA-340型翻斗式散装水泥车的改造问题 2页

2025年感染性心内膜炎护理查房要点解析 30页

六倍体小黑麦与普通小麦杂交细胞遗传的研究 2页

八十年代美国在边界层过程研究方面的重点任务.. 2页

全球平衡增长研究中的若干理论问题探讨 2页

2025年寰枢椎半脱位治疗及康复护理攻略 15页

全国首届科技写作教师培训班在中国科学技术大.. 2页

全国财经院校研究生会计学术讨论综述 2页

2025年孤立性纤维瘤诊疗指南与最新研究进展 32页

全国生物教学研究会第二届学术年会在庐山召开.. 2页

2025年大学生心理调适情绪掌控与自我管理攻略.. 24页

全国并条工艺、设备技术经验交流会在南昌召开.. 2页

2025年垂体瘤合并鞍区生殖细胞瘤诊治探讨 61页

全国中、小平板玻璃厂的一次技术交流会 2页

兔右房超速驱动后阻抑机制的初步探讨 2页

2025年呼吸机操作与保养全攻略 37页

2025年吉兰巴雷综合症治疗与护理攻略 27页

光电外观动态检验中零件跳动对测量精度影响的.. 2页

艺术舞蹈老师简历模板 1页

服装设计合作协议书 5页

煤炭资源地质勘查设计编写提纲 14页

硫酸铵生产硫酸钾的可行性方案 31页