归并排序

将两个或两个以上有序的数列(或有序表),合并成一个仍然有序的数列(有序表),这种操作称为归并操作。这样的方法经常用于多个有序的数据文件归并成一个有序的数据文件。若将两个有序表合并成一个有序表则称为二路归并,同理,有三路归并、四路归并等。二路归并比较简单,所以我们只讨论二路归并。例如有两个有序表: (7,10,13,15)和(4,8,19,20),归并后得到的有序表为: (4,7,8,10,13,15,19,20)。

        归并过程为:比较A[i]和A[j]的大小,若A[i]≤A[j],则将第一个有序表中的元素A[i]复制到R[k]中,并令i和k分别加1,即使之分别指问后一单元,否则将第二个有序表中的元素A[j]复制到R[k]中,并令j和k分别加1;如此循环下去,直到其中的一个有序表取完,然后再将另一个有序表中剩余的元素复制到R中从下标k到下标t的单元.

 1 #include<iostream>
 2 using namespace std;
 3 int a[10001],r[10001],n,i;        //a是待排序数组,r是临时数组
 4 void mergesort(int s,int t)     //对[s,t]区间的无序数据进行归并排序
 5 {    
 6     int m,i,j,k;
 7     if(s==t)  
 8     return;             //若区间只有一个数据就不用排了
 9     m=(s+t)/2;                    //取区间的中点
10     mergesort(s,m);            //以中点二分,对左边了区间进行排序
11     mergesort(m+1,t);              //以中点二分,对右边了区间进行排序
12     i=s;                     //以下是一次归并(合并)操作 
13     j=m+1;
14     k=s;
15     while(i<=m&&j<=t)   //二个子序列从小大到合并,直到有一列结束
16     {  
17         if(a[i]<=a[j])   
18         {r[k]=a[i];
19         i++;k++;
20         }
21         else
22         {
23         r[k]=a[j];
24         j++;k++;
25         }
26     }
27     while(i<=m)//*把左边子序列剩余的元素接入进来*
28     {
29         r[k]=a[i];
30         i++;
31         k++;
32     }
33     while (j<=t)             //把右边子序列剩余的元素接入进来
34     {
35         r[k]=a[j];
36         j++;
37         k++; 
38     }
39     for(i=s;i<=t;i++)            //把合并后的有序数据重新放回a数组
40     a[i]=r[i];
41 }
42 int main()
43 {  
44     cin>>n;
45     for(i=1;i<=n ;i++)                   //读入n个待排序数据
46     cin>>a[i];
47     mergesort(1,n);        //对[1,n]区间的无序数据进行归并排序
48     for (i=1;i<=n;i++)                   //输出n个有序的数据
49     cout<<a[i]<<" " ;
50     cout<<endl;
51 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AILearning

Map集合

Collection |--List:元素是有序的,元素可以重复,因为该集合体系有索引 |--ArrayList:底层的数据结构使用的是数据结构。特点:查询...

25860
来自专栏爱撒谎的男孩

冒泡排序算法

17830
来自专栏Bingo的深度学习杂货店

Q190 Reverse Bits

Reverse bits of a given 32 bits unsigned integer. For example: given input 43261...

34950
来自专栏PHP在线

Array数组函数(三)

array_keys — 返回数组中所有的键名 array_values — 返回数组中所有的值 array_key_exists — 检查给定的键名或索引是否...

36080
来自专栏柠檬先生

es6 Set 和Map 数据结构

ES6提供了新的数据结构Set,它类似于数组,但是成员的值都是唯一的,没有重复的值。   Set 本身是一个数据结构,用来生成Set 数据结构。     con...

19680
来自专栏微信公众号:Java团长

Java抽象类与接口的区别

很多常见的面试题都会出诸如抽象类和接口有什么区别,什么情况下会使用抽象类和什么情况你会使用接口这样的问题。本文我们将仔细讨论这些话题。

9100
来自专栏静默虚空的博客

[Java 基础]运算符和表达式

Java运算符 (1)赋值操作符 赋值操作符(=)表示:取右边的值(即右值),把它复制给左边(即左值)。 右值可以是任意的常量、变量或表达式(只要可以生成一个值...

20490
来自专栏深度学习与计算机视觉

Python3 一些与C++不一样的运算符

Python逻辑运算符 逻辑“与”运算符 and 逻辑表达式 a and b 如果变量a,b中有一个是Flase,那么a and b为Flase ...

21950
来自专栏黑泽君的专栏

调用Thread类的方法:public final String getName() 为什么得到的线程对象的名称默认是:Thread-0、Thread-1、Thread-2、...呢?

调用Thread类的方法:public final String getName() 为什么得到的线程对象的名称默认是:Thread-0、Thread-1、Th...

17920
来自专栏GreenLeaves

Array对象的判定

/* 关于JS对象类型的判断,最复杂的在于RegExp和Array了,判定RegExp的情形不较少,而Array就比较多了,下面就是判断Array的...

18550

扫码关注云+社区

领取腾讯云代金券