归并排序

2021-03-20 09:25

阅读:389

标签:loading   bit   nbsp   有序表   ref   code   int   alt   style   

归并排序

我终于看了归并排序了!!!其实我很久之前就准备把瑞士轮给做了,但是,我发现用STL里的sort过不了过后我就没再管它了,今天又看到了这道题,我还是决定看一看神奇的归并排序。

由于不喜欢看好多好多字,我们先放一张图(简单易懂

技术图片  

我当时看到这图过后就恍pang然ran大da悟wu了,突然就懂了它的基本思想:归并排序是建立在归并操作上的一种有效,稳定的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。(感谢百度百科)(说人话就是采用一个分治的思想,然后在分成的每一小段内进行排序,因为每一段都是有序的,在后来的每一步合并操作之中就都很方便了,只需要考虑四种情况,最后的最后,将它们合并成一个整体的操作)

所以代码怎么实现?因为我没想出来,就去网上看了看其他大神写的模版,然后我又突然就懂了(什么,又懂了?

首先我们从main函数开始倒着往回推

1 int main(){
2     int n,a[10005];
3     cin>>n;
4     for(int i=0;i>a[i];
5     mergesort(a,0,n);
6     for(int i=0;ia[i];
7     return 0;
8 }

 

就是一个很简单的输入输出,加一个mergesort操作,由于输入的时候数组只有0~n-1有真正的值,我们就又要需要一个来解决这个简单的问题lalala

1 void mergesort(int a[],int l,int r){
2     merge_sort(a[],l,r-1);
3 }

所以这个真正的merge_sort()函数是在干什么呢?其实实质上就是个简单的二分(纯二分

1 void merge_sort(int a[],int l,int r){
2     if(l>=r) return;
3     int mid=(l+r)/2;
4     merge_sort(a,l,mid);
5     merge_sort(a,mid+1,r);
6     merge(a,l,r,mid); 
7 }

看这个奇妙的二分函数我们又要引入一个函数merge()了,终于切入正题了。。。

 1 void merge(int a[],int l,int r,int mid){
 2     int b[r-l+1];
 3     for(int k=l;ka[k];
 4     int i=l,j=mid+1;
 5     for(int k=l;k){
 6         if(i>mid) a[k]=b[j-l],j++;
 7         else if(j>r) a[k]=b[i-l],i++;
 8         else if(b[i-l]>b[j-l]) a[k]=b[j-l],j++;
 9         else a[k]=b[i-l],i++;
10     }
11 }

这就是我刚刚提到的四种情况,因为在这里,整个l~r被分成了两个部分:l~mid&mid+1~r,所以我们就从l和mid+1开始比较,先考虑边界(l>mid和j>r),解决了这问题就是一个分类讨论,还只有两种情况,因为i和j是头,分别是现存的两个部分里最小的,所以只需要比较i和j在数组中的值就可以确定结果数组的后一位数了

瞎扯了认真分析了一大堆,完整代码如下:

 1 //归并排序模版 
 2 #include 3 using namespace std;
 4 
 5 void merge(int a[],int l,int r,int mid){
 6     int b[r-l+1];
 7     for(int k=l;ka[k];
 8     int i=l,j=mid+1;
 9     for(int k=l;k){
10         if(i>mid) a[k]=b[j-l],j++;
11         else if(j>r) a[k]=b[i-l],i++;
12         else if(b[i-l]>b[j-l]) a[k]=b[j-l],j++;
13         else a[k]=b[i-l],i++;
14     }
15 }
16 
17 void merge_sort(int a[],int l,int r){
18     if(l>=r) return;
19     int mid=(l+r)/2;
20     merge_sort(a,l,mid);
21     merge_sort(a,mid+1,r);
22     merge(a,l,r,mid); 
23 }
24 
25 void mergesort(int a[],int l,int r){
26     merge_sort(a[],l,r-1);
27 }
28 
29 int main(){
30     int n,a[10005];
31     cin>>n;
32     for(int i=0;i>a[i];
33     mergesort(a,0,n);
34     for(int i=0;ia[i];
35     return 0;
36 }

全文完。。。所以我还写不写其他排序的分析呢?(手 动 问 号 )

 

归并排序

标签:loading   bit   nbsp   有序表   ref   code   int   alt   style   

原文地址:https://www.cnblogs.com/001A/p/13926467.html


评论


亲,登录后才可以留言!