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

最近更新

仿射跳扩散模型下期权定价的稳健Fourier-Cos方.. 9页

“中国科学院化学情报网计算机应用交流会”在.. 2页

Y zY H型钎头的试验与应用 2页

X射线对产品内部结构和装配质量的分析 2页

WE型聚乙烯蜡在LLDPE挤出吹塑中的应用 2页

TY-43A数字面板表性能及应用 2页

2025年幼儿园大班教育随笔三篇 7页

SP-1多功能外加剂的性能及应用 2页

SK-35型潜孔钻机在日铁矿业公司的应用 2页

SDA脱硫工艺在烧结烟气脱硫中的应用 2页

2025年幼儿园保育工作计划精选5篇 13页

第三章保险法的基本原则 44页

PVC膜四碘络铋离子选择电极在金属分析中的应用.. 2页

Pr—Fe—B烧结永磁材料的研究 2页

不确定结构的拓扑优化设计及分析 3页

2025年幼儿园中班4月份工作总结 12页

PDC钻头切削齿工作角的设计方法 2页

北师大版数学五年级下册:数学与购物估计费用.. 20页

ND 5型机车主机油泵泵体的扫膛故障及修复方法.. 2页

Mn-V双相钢变形特性的研究 2页

2025年年度工作总结报告个人范文 18页

校园交通安全责任合同 6页

LPG低温储存装置管道泄漏风险分析 2页

LDC-2型失磁保护误动的情况分析 2页

2025年吕梁职业技术学院单招职业适应性测试题.. 74页

煤矿春季预防性电气试验试措施样板 18页

2025届高考模拟作文“时间管理”升格导写 5页

佛教用超度牌位(打印版) 5页

《于宏杰-到底神要的是什么呢》 5页

土方工程施工方案与技术措施MicrosoftWord文档.. 64页