图解归并排序，带你彻底了解清楚！
写在前面：
大家好，我是时光。
今天给大家带来的是排序算法中的归并排序，这种排序需要拆分归并。我采用图解方式讲解，争取写透彻。话不多说，开始！
思维导图：
1，归并排序的概念
1.1，算法介绍
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
1.2，基本思想
基本思路就是将数组分成二组 A，B，如果这二组组内的数据都是有序的，那么就可以 很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将 A，B 组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。
1.3，归并的定义
将两个或两个以上的有序序列合并成一个新的有序序列：
3路归并：将3个有序序列归并为一个新的有序序列，称为3路归并；
多路归并：将多个有序序列归并为一个新的有序序列；，称为多路归并；
1.4，如何合并有序序列
只要从比较两个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据一次取出即可。
2，算法思路
我们先搞清楚这个归并排序思想，先把逻辑搞清楚，不着急写代码。
我们首先有一个无序数组，比方说
int[] arr={4,2,8,0,5,7,1,3,9};
2.1，第一个步骤，拆分数组
我们采用2路归并，(start+end)/2处为临界点，将初始无序数组拆分成两个无序序列，然后依次循环拆分，最后再归并为一个新的有序序列；
首先我们来思考下判断条件，当start=end时，此时序列只有一个元素，所以这是临界点；然后就是分组，拆分，采用递归的方式。最后再把所有拆分好的元素进行归并！
拆分代码：
public static int[] Merge_Sort(int[] arr, int start, int end) {
//当start==end时，此时分组里只有一个元素，所以这是临界点
if (start < end) {
//分成左右两个分组，再进行递归
int mid = (start + end) / 2;
//左半边分组
Merge_Sort(arr, start, mid);
//右半边分组
Merge_Sort(arr, mid + 1, end);
//递归之后再归并归并一个大组
Merge(arr, start, mid, end);
}
return arr;
}
拆分到最后一步，每一个小序列都是单独的元素，在第二步我们再把这些元素进行归并。
2.2，第二个步骤，归并序列
拆完以后，我们需要将这些单独的元素放入一个额外空间储存，再进行排序。因此，归并排序是需要占用额外空间的。
我们这里以第一次拆分的两个分组为例，其实也就是归并的最后一步。第一次拆分之后的两个序列就是[4 2 8 0 5]和[7 1 3 9]了；但是大家要注意，我们在对这两个序列进行归并时，他们应该是早就排好序了！因为是递归拆分，在最后一次拆分的时候序列都是单独的元素，所以到归并的最后一步时，也就是左边的序列应该是[0 2 4 5 8]，右边的序列应该是[1 3 7 9]。
归并代码：
//归并方法
public static void Merge(int[] arr, int start, int mid, int end) {
//左边分组的起点i_start，终点i_end，也就是第一个有序序列
int i_start = start;
int i_end = mid;
//右边分组的起点j_start，终点j_end，也就是第二个有序序列
int j_start = mid + 1;
int j_end = end;
//额外空间初始化
int[] temp=new int[end-start+1];
int len = 0;
//合并两个有序序列
while (i_start <= i_end && j_start <= j_end) {
//当arr[i_start]<arr[j_start]值时，将较小元素放入额外空间，反之一样
if (arr[i_start] < arr[j_start]) {
temp[len] = arr[i_start];
len++;
i_start++;
} else {
temp[len] = arr[j_start];
len++;
j_start++;
}
}
}
这里有个代码小技巧，注意上面合并有序序列的这个循环里面的代码，其实只要一行代码就可以搞定：
//合并两个有序序列
while (i_start <= i_end && j_start <= j_end) {
temp[len++]=arr[i_start]<arr[j_start]?arr[i_start++]:arr[j_start++];
}
注意：这里还有个小问题，无论是第一个序列还是第二个序列，在比较元素大小最后的时候，有可能会多出来元素。比如说上面的第二个序列的元素9，它在与元素8比较，元素8被存入到额外空间之后，那么它自然就多出来了，我们默认把它放在额外空间的最末尾处；所以我们还需要添加以下代码，写在归并方法里面；
//i这个序列还有剩余元素
while(i_start<=i_end){
temp[len] = arr[i_start];
len++;
i_start++;
}
//j这个序列还有剩余元素
while(j_start<=j_end){
temp[len] = arr[j_start];
len++;
j_start++;
}
2.3，第三个步骤，额外空间覆盖原始空间
这第三个步骤就比较简单了，经过前面两个步骤之后我们就把一个无序数组拆分为两个序列，再把两个序列归并成一个有序的数组，并存放在我们开辟的额外空间里面。最后一步操作就是要把额外空间里面的元素覆盖到原空间输出即可。
我们先来看代码，再来分析：
//额外空间数据覆盖到原空间
for(int i=0;i<temp.length;i++){
arr[start+i]=temp[i];
}
循环我们很好理解，可能大家不太明白为什么arr数组里面是从start+i开始的，首先我们来分析下：
这个i只是temp里面元素的数组下标，而arr数组下标是从start开始，比如说当我们要把分好的两个序列覆盖到原空间：
所以元素覆盖要从start+i这个位置开始，而不是简单的i开始。
3，完整代码
import java.util.Arrays;
public class Merge_Sort {
public static void main(String[] args) {
int[] arr = {4,2,8,0,5,7,1,3,9};
System.out.println(Arrays.toString(Merge_Sort(arr, 0, arr.length - 1)));
}
/**
* @param arr 初始数组
* @param start 开始分组
* @param end 结束分组
* @return
*/
public static int[] Merge_Sort(int[] arr, int start, int end) {
//当start==end时，此时分组里只有一个元素，所以这是临界点
if (start < end) {
//分成左右两个分组，再进行递归
int mid = (start + end) / 2;
//左半边分组
Merge_Sort(arr, start, mid);
//右半边分组
Merge_Sort(arr, mid + 1, end);
//递归之后再归并归并一个大组
Merge(arr, start, mid, end);
}
return arr;
}
//归并方法
public static void Merge(int[] arr, int start, int mid, int end) {
//左边分组的起点i_start，终点i_end，也就是第一个有序序列
int i_start = start;
int i_end = mid;
//右边分组的起点j_start，终点j_end，也就是第二个有序序列
int j_start = mid + 1;
int j_end = end;
//额外空间初始化，数组长度为end-start+1
int[] temp=new int[end-start+1];
int len = 0;
//合并两个有序序列
while (i_start <= i_end && j_start <= j_end) {
//当arr[i_start]<arr[j_start]值时，将较小元素放入额外空间，反之一样
if (arr[i_start] < arr[j_start]) {
temp[len] = arr[i_start];
len++;
i_start++;
} else {
temp[len] = arr[j_start];
len++;
j_start++;
}
//temp[len++]=arr[i_start]<arr[j_start]?arr[i_start++]:arr[j_start++];
}
//i这个序列还有剩余元素
while(i_start<=i_end){
temp[len] = arr[i_start];
len++;
i_start++;
}
//j这个序列还有剩余元素
while(j_start<=j_end){
temp[len] = arr[j_start];
len++;
j_start++;
}
//辅助空间数据覆盖到原空间
for(int i=0;i<temp.length;i++){
arr[start+i]=temp[i];
}
}
}
运行结果：
4，算法分析
4.1，时间复杂度
归并排序把集合进行层层拆半分组。如果集合长度为n，那么拆半的层数就是logn，每一层进行归并操作的运算量是n。所以，归并排序的时间复杂度等于每一层的运算量×层级数，即O(nlogn)。
4.2，空间复杂度
归并排序是需要用到额外空间的，但是每次归并所创建的额外空间都会随着方法结束而释放，因此单次归并操作开辟的最大空间是n。所以，归并排序的空间复杂度是O(n)。
4.3，算法稳定性
归并排序是稳定的排序算法。temp[len++]=arr[i_start]<arr[j_start]?arr[i_start++]:arr[j_start++];，这行代码可以保证当左右两部分的值相等的时候，先复制左边的值，这样可以保证值相等的时候两个元素的相对位置不变。
-- End --