• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

【算法】排序02——归并排序介绍及其在分治算法思想上与快排的区别(含归并代码)

开发技术 开发技术 2周前 (07-26) 14次浏览

1、归并排序是什么?

归并排序快速排序一样,都采用了分治算法的思想,时间复杂度都为O[ nlog (n)],但其空间复杂度更大一点,为O[ log (n)],不过相对的,归并是一种稳定排序,这一点和快排是不同的。

归并排序的思想流程:


 

先分,我们先举例一个序列 [ 5 6 9 8 7 4 1 2 3 ],然后把它不断的二分到序列里只有1个元素时为止。

①                                    [ 5 6 9 8 7 4 1 2 3 ]     

                              /                               

②                 [ 5 6 9 8 7 ]                                 [ 4 1 2 3]

                        /                                                 /       

③        [ 5 6 9 ]         [ 8 7 ]                         [ 4 1 ]         [ 2 3 ]

              /                   /                               /                /      

④    [ 5 6 ]  [ 9 ]       [ 8 ] [ 7 ]                   [ 4 ]  [ 1 ]     [ 2 ] [ 3 ]

         /     

⑤  [ 5 ]  [ 6 ]

上面这样的操作就相当于分治算法中的“分”,但是我们只是“分”了,还没有“治”,所以我们要么做才能才能“治”呢?

其实很简单,我们只要反过来,从⑤到①逐项把这些小序列两两合并成有序的新序列就可以了。

后治

⑤  [ 5 ]  [ 6 ]

              /

④    [ 5 6 ] [ 9 ]        [ 8 ] [ 7 ]                   [ 4 ]  [ 1 ]     [ 2 ] [ 3 ]

                 /                    /                               /                /  

③       [5 6 9 ]            [ 7 8 ]                        [ 1 4 ]         [ 2 3 ]

                                 /                                               /

②              [ 5 6 7 8 9 ]                                    [ 1 2 3 4 ]

                                                                     /

①                                   [ 1 2 3 4 5 6 7 8 9 ]

 

动态图演示:


 

 

【算法】排序02——归并排序介绍及其在分治算法思想上与快排的区别(含归并代码)

手撕代码:


 

当然,在代码中,我们把两个序列合并成一个有序序列的时候,通常需要另外的内存空间(即代码中的reg数组)来辅助存储正在排序数据,当一个新序列排序完成后再把它导入回原来的内存空间(即代码中arr数组)。有些小伙伴们可能不是很理解这句话,那就从去看看一代码吧,相信你看完代码后就能明白了!

 1 import java.util.Arrays;
 2 
 3 public class Main {
 4 
 5     public static void merge_sort(int[] arr){
 6         //new 一个等大的临时空数组,用于排序时缓存数据
 7         int[] reg = new int[arr.length];
 8         recursive(arr,reg,0,arr.length-1);
 9     }
10 
11     public static void recursive(int[] arr,int[] reg,int begin,int end){
12         //若当前序列不足两个元素时就不必再分了
13         if(end-begin<1){return;}
14         //获取二分后两个序列的首尾下标,>>1是右移一位的位操作,比直接除以2要快
15         int left_begin = begin;
16         int left_end = (begin+end)>>1;
17         int right_begin = left_end+1;
18         int right_end = end;
19 
20         //递归调用
21         recursive(arr,reg,left_begin,left_end);
22         recursive(arr,reg,right_begin,right_end);
23 
24         //获取临时数组的下标指针
25         int pointer = begin;
26         while (left_begin<=left_end&&right_begin<=right_end){//注意细节,赋值后加一
27             if(arr[left_begin]<arr[right_begin]){
28                 reg[pointer] = arr[left_begin];
29                 left_begin++;
30             }else {
31                 reg[pointer] = arr[right_begin];
32                 right_begin++;
33             }
34             pointer++;
35         }
36         //上面的循环跳出后,左右两个序列中可能还有一个序列的一部分还没挪到reg上,把它挪过去
37         while (left_begin<=left_end){
38             reg[pointer] = arr[left_begin];
39             left_begin++;
40             pointer++;
41         }
42         while (right_begin<=right_end){
43             reg[pointer] = arr[right_begin];
44             right_begin++;
45             pointer++;
46         }
47 
48         //把reg上排序好的序列挪回到arr上
49         for(int i = begin ; i<=end ; i++){
50             arr[i] = reg[i];
51         }
52     }
53 
54     public static void main(String[] args) {
55         int[] arr = {2,5,6,7,3,8,1,0,9};
56         merge_sort(arr);
57         System.out.println(Arrays.toString(arr));
58     }
59 }

2、关于快排与归并排序的区别:

之前听到过不止一位小伙伴说在面试的时候,容易把快排和归并排序搞混淆了(毕竟都是分治思想)。博主觉得呢,如果只是单纯的硬记某种排序的话,我不太推荐这么做。我更建议小伙伴们纵向比较比较,你就会发现,快排和归并排序还是有两个主要区别的。

第一个区别在于,归并排序是先分后治,即先把一个大序列拆分成多个小序列再两两合一,而快排则是先治再分,即先把一个大序列治理成阈值左边数全小于右边的数的状态,再以阈值为界概念上二分这个序列(关于快排的更多介绍,可以点击这里看我的另一篇关于快排的博文)。

第二个区别在于,归并排序的二分是折半二分,分出子问题的过程更像是一个完全二叉树,但是快排的二分并不是折半的,它具有随机性的阈值影响,这种二分可能一边内容多一边内容少。

 

最后,如果小伙伴觉得这篇博文对你有帮助的话,就点个推荐吧【算法】排序02——归并排序介绍及其在分治算法思想上与快排的区别(含归并代码)

 


喜欢 (0)