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年度钢结构施工安全监理与咨询服务合同 10页

2025年度路面施工项目环境影响评价及验收合同.. 10页

2025年度苗木供应链金融支持与采购合同 9页

2025年度美容院美容项目入股合作协议书 10页

2025年度简易解聘产品代销合同 10页

2025年度白酒品牌区域独家代理合作协议 8页

2025年度环保节能型租房合同安全规范示例 8页

第1单元·集合与逻辑·最新高考+模拟doc高中数.. 18页

2025年度民法典合同解除中的合同效力审查合同.. 8页

2025年度智能化门卫劳务服务合同 10页

2025年度新型防火门购销合同汇编指南 9页

2025年度教育培训机构课程定制合作协议 9页

2025年度房屋拆除项目安全管理及协议书 8页

2025年度建筑工程用挖掘机租赁及施工合作合同.. 9页

初识电子邮件 12页

2025年度安全防护纺织品国际贸易代理合同 9页

2025年度外派至海外企业的技术咨询服务合同 8页

酒店接听电话服务标准 23页

2025年度吊装运输设备租赁及搬运合同 9页

有关公司成立合同书 6页

2025年度写字楼租赁续约及设施维护合同 9页

部编本一年级语文上册《乌鸦喝水》课件 24页

2025年度住宅小区水暖系统智能化升级合同 9页

2025年度仓储物流租赁合同续租模板 8页

智慧停车服务项目合同 6页

发送医院护理质量考核评价2 90页

通信导论第五章电波传播 43页

新房购买合同细则 6页

新型合同种类展望:五大合同趋势 6页

教育基地租赁合同 6页