归并排序介绍及算法含归并代码

归并排序的思想流程:

先分，我们先举例一个序列 [ 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]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、关于快排与归并排序的区别：
之前听到过不止一位小伙伴说在面试的时候，容易把快排和归并排序搞混淆了（毕竟都是分治思想）。博主觉得呢，如果只是单纯的硬记某种排序的话，我不太推荐这么做。我更建议小伙伴们纵向比较比较，你就会发现，快排和归并排序还是有两个主要区别的。
第一个区别在于，归并排序是先分后治，即先把一个大序列拆分成多个小序列再两两合一，而快排则是先治再分，即先把一个大序列治理成阈值左边数全小于右边的数的状态，再以阈值为界概念上二分这个序列（关于快排的更多介绍，可以点击这里看我的另一篇关于快排的博文）。
第二个区别在于，归并排序的二分是折半二分，分出子问题的过程更像是一个完全二叉树，但是快排的二分并不是折半的，它具有随机性的阈值影响，这种二分可能一边内容多一边内容少。