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页

《伤寒和副伤寒》 85页

企业文化建设在煤炭企业管理中的重要性 4页

企业存货内部控制问题研究——以硕鑫食品有限.. 4页

北京地铁七号线达官营站及湾达区间暗挖关键技.. 1页

办公室文件柜定制合同 9页

农药生产用水供应协议 9页

农业原料供应运输协议 9页

人力资源管理策略对组织绩效的影响研究 4页

人力资源管理的员工绩效考核 5页

人力资源管理核心机制创新模式CTC管理模式的建.. 4页

人力资源管理对企业经济效益的影响研究 4页

人力资源管理在企业管理中的作用和影响 4页

二零二五年度餐馆服务员劳动合同与劳动争议调.. 6页

二零二五年度跨省货车拉运货物安全协议范本 10页

二零二五年度警用车辆质押抵押借款合同 10页

人力资源培训员工关系管理 5页

二零二五年度股权委托代持与创业投资风险评估.. 9页

二零二五年度网络直播平台背景音乐作曲协议 9页

事业单位人力资源管理的信息化建设 8页

二零二五年度百货商品质量检测购销协议 10页

中小企业存货管理存在的问题及对策研究开题报.. 5页

带辅助靠泊平台的连续丁靠滚装码头平面布置研.. 2页

【毕业论文选题】旅游管理本科论文题目精选 6页

【2025最新】杨毅.开题报告(1) (4500字)word版.. 5页

《人力资源管理》教学大纲(本科) 6页

二零二五年度新能源产业厂房场地使用权转让协.. 8页

mba证券论文题目大全(推选100个) 4页

HRSSC人力资源服务共享中心实操分析 3页

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