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页

《信用证典型纠纷案》 25页

关于企业人事管理工作中几个观念的浅析 2页

2025年昏迷急救处理与临床诊断策略 46页

关于Fx列系计算器在普测平差计算中应用的探讨.. 2页

关于(sI-A)~(-1)的一点探讨 2页

《压疮的分级和护理》 37页

公路工程项目设计阶段监理工作探讨 2页

2025年微创尿路重建术式探讨与进展 17页

全方位发展商品经济——西南地区发展战略的思.. 2页

2025年妊娠合并肺动脉高压诊疗策略探讨 53页

全国应用核技术寻找地下水源学术讨论会简讯 2页

光谱法研究联二萘酚与牛血清蛋白的相互作用 2页

2025年医院感染防控护理人员的核心角色 25页

2025年全身性原发性毛细血管扩张症研究 19页

2025年上肢神经阻滞麻醉技术探讨 49页

六年级毕业晚会主持词开场白(24篇) 45页

2025年输液问题处理技巧与故障排查指南 18页

关于小学德育工作计划范文汇编(3篇) 16页

写云朵的作文 12页

2025年脑电图入门原理与临床应用解析 28页

2025年脑卒中康复训练疗法 36页

四面山小学作文 2页

2025年大学中国新能源电动汽车消费者调研报告.. 24页

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

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

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

2022年首都经济贸易大学工商管理专业《管理学.. 22页

学生5mm坐标纸(虚线 word版)直接打印 2页

(完整版)天津大学非线性信息处理技术 12页