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

最近更新

高中化学竞赛辅导讲座氮族元素 20页

《材料工艺》一九八○年总目录 2页

《地震地磁观测与研究》第十四卷1993年总目录.. 2页

《书评工作指导与探索》将出版 2页

“菜油磷脂在橡胶工业上的应用推广”通过技术.. 2页

“FRB”衬垫面CO 2气保焊工艺试验和应用 2页

α径迹测量在吉林东部山区找水的应用效果 2页

高一学生文理分科指导ppt 30页

高一化学《富集在海水中的元素-氯》PPT课件 28页

UV-Ⅰ型低温消化反应器的研制及应用 2页

TY290Q型柴油机水温过高的分析 2页

Toepler泵在金属有机化学中的应用 2页

TG-350型汽车起重机力矩限制器的数学模型分析.. 2页

SXJ型实验室洗涤机在南京通过技术鉴定 2页

初中生祖孙关系问卷的编制与初步应用 2页

SM—92织机织造停机挡分析 2页

PVC压延薄膜不包辊筒的原因及解决方法 2页

2025年幼儿园中班教师教学计划2025年 14页

餐饮业食品卫生监督与管理 49页

PC—1500型计算机在测井仪器刻度中的应用 2页

PASCAL语言结构的硬件实现方法 2页

创造并留住顾客——物竞天择适者生存(1) 72页

2025年年终工作总结通用 11页

2025年年度安全生产工作计划怎么写,安全生产工.. 18页

风险防范与医疗安全 69页

校企合作研发合同项目 7页

艺术舞蹈老师简历模板 1页

服装设计合作协议书 5页

煤炭资源地质勘查设计编写提纲 14页

硫酸铵生产硫酸钾的可行性方案 31页