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

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 ]

动态图演示：

手撕代码：

当然，在代码中，我们把两个序列合并成一个有序序列的时候，通常需要另外的内存空间（即代码中的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 }