【排序算法】归并排序

释放双眼,带上耳机,听听看~!

  小编记得在老早以前就梳理过一期排序算法,可是小编从未精讲,这一次就单独拿出众所周知的归并排序来讲一讲吧。

【问题引入】

  在生活中,我们常常会看到一些数字,需要你来排序,当数字数量较大时,我们就会用到计算机来处理,那么如果是你,你会怎么写这个程序呢?

【题目分析】

  如果你有一定的基础,一定会想到使用排序算法,你会用什么呢?冒泡?插入?归并?快排?

  今天我们来精讲归并排序。

【归并排序】

1)使用思想:分治;

2)算法图解:

3)代码如下:

 1 #include<iostream>
 2 using namespace std;
 3 int data[1000],result[1000];
 4 void merge_compare(int l,int r)
 5 {
 6     int mid=(l+r)>>1;
 7     int left_start=l;
 8     int left_end=mid;
 9     int right_start=mid+1;
10     int right_end=r;
11     int result_start=l;
12     while(left_start<=left_end&&right_start<=right_end)//将两个子序列合并 
13     {
14         if(data[left_start]<data[right_start])
15         result[result_start++]=data[left_start++];
16         else
17         result[result_start++]=data[right_start++];
18     }
19     while(left_start<=left_end)//将左序列剩余放入数组中 
20     result[result_start++]=data[left_start++];
21     while(right_start<=right_end)//将右序列剩余放入数组中 
22     result[result_start++]=data[right_start++];
23 }
24 void merge_sort(int l,int r)
25 {
26     if(l==r) return;//只有一个数时返回 
27     if(r-l==1)
28     {
29         if(data[l]>data[r])
30         swap(data[l],data[r]);
31         return;//两个数时直接交换顺序 
32     }
33     int mid=(l+r)>>1;
34     merge_sort(l,mid);//划分左序列 
35     merge_sort(mid+1,r);//划分右序列 
36     merge_compare(l,r);//划分完成后合并 
37     for(int i=l;i<=r;i++)
38     data[i]=result[i];//将临时数组中的值赋给原数组 
39 }
40 int main()
41 {
42     int n;
43     cin>>n;
44     for(int i=1;i<=n;i++)
45     cin>>data[i];
46     merge_sort(1,n);
47     for(int i=1;i<=n;i++)
48     cout<<data[i]<<\" \";
49     return 0;
50 }

亲测能用:

4)优劣成都:

优:稳定,速度快

劣:空间复杂度较高

5)与快速排序的差别

个人认为归并排序很稳定,速度已经很快了,只不过空间复杂度较高。而快速排序极不稳定,时快时慢,最慢能成为冒泡排序一样,而归并却保持在O( n log n)的速度,所以平时最好用归并。

之前曾写过各路传奇排序,讲的种类较多,有兴趣的读者可以看一看。

人已赞赏
站长资讯

关于集合中一些常考的知识点总结

2020-11-9 3:41:25

站长资讯

微服务:如何优雅的使用Mybatis

2020-11-9 3:41:27

0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
购物车
优惠劵
今日签到
有新私信 私信列表
搜索