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

最近更新

道德讲堂感恩父母标准流程 63页

114.3mm套管水平井试气用桥塞室内试验研究 2页

建筑机械搬迁运输协议3篇 45页

高校创新创业人才培养学制教学改革研究 3页

风险导向审计在企业审计中的应用 3页

雾流强化CO 2水合物形成特性实验研究 3页

细胞信号通路的调控机制-全面剖析 26页

2025黑龙江社区《网格员》模拟试题及答案 10页

化学矿开采技术革新-全面剖析 28页

运营商IP城域网向IPv6演进方案及策略探讨 3页

高三学生励志的演讲稿(5篇) 11页

辅助变压器在有载调压中的应用 3页

车内噪声主动控制发展综述及其在实车上的应用.. 3页

财务预算和会计核算体系协调研究 3页

试析计量检定工作中的人员误差及对策研究 3页

西方财务管理第六章 71页

螳螂川河流磷、氟污染与防治对策分析研究 3页

营改增对企业的影响与对策研究 3页

2025年度个人股份对外转让与投资合作合同 9页

船用液压滑动式水密门技术现状研究 3页

自聚焦棒透镜准直系统的装配误差引起的附加耦.. 4页

肉桂和八角精油联合抗菌作用研究 3页

翻译控制肿瘤蛋白及其生物学功能研究进展 3页

绿色电子制造用水基助焊剂的研究 3页

经济增加值与企业价值的相关性研究 3页

蔬菜植物的分类 14页

简谈冶金矿山土地复垦形势与对策 3页

营销案例之价值提炼 25页

科技企业员工思想动态调研及分析 3页

磁性水凝胶的制备及其在正渗透中的应用 3页