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

最近更新

2025年缺铁性贫血防治攻略详解 29页

2025年紧急心理援助与干预策略 79页

【大学】化工原理 绪论多媒体教学 36页

【大学】法律的起源和发展 23页

基于CRISPR-Cas9技术探索敲除RAB7A增强肺癌对.. 9页

具有功率解耦的宽范围输入DC-AC变换器研究 9页

2025年神经系统与内分泌调节交互作用解析 36页

2025年社交心理学人际认知奥秘解析 52页

《综合费用的核算》 15页

《自动控制理论教学》第4章 线性定常系统的线.. 55页

2025年祛臭液项目建议书 70页

2025年米面机械合作协议书 60页

2025年绝缘制品项目合作计划书 52页

2025年胶板项目发展计划 57页

2025年航空地面试验设备项目发展计划 54页

2025年磁罗盘合作协议书 68页

《质量改进工具》 45页

2025年时尚插画人体头部绘制攻略 43页

2025年新生儿疫苗接种知识讲座 23页

2025年支气管镜在肺结核诊断中的运用与研究 22页

2025年手术室护理要点深度探讨 24页

2025年心脏肾脏交互病变解析 65页

2025年徒手心脏急救术攻略 23页

2025年子宫肌瘤治疗新法动脉栓塞术 30页

2025年天坛社区医疗中心全面解析 22页

2025年医护工作者年终工作汇报与成果展示 20页

2025年儿童肱骨髁上骨折治疗策略 19页

2025年五年级小学生科学探索人体的呼吸系统揭.. 29页

2025年高血压盐敏感性治疗药物精选指南 38页

2025年阿奇霉素临床应用与研究进展 32页