? ? ? ?
????????归并排序基于归并思想采用分治策略，先将数据利用递归分解成单独一个数，然后利用递归的回调机制进行排序合并，需要额外的开创一个大小与待排序的数据相同的空间用来填充，然后再将有序的序列替换掉待排序的数组的无序序列，是典型的利用空间来换时间的算法。
1、算法实现思想和过程图
????????其实看完算法的实现图之后，对归并算法的思想应该有所理解了，代码实现的话需要一定的技巧和思路的，这里代码实现可以分为两个部分，一个是分解递归，另一个就是合并了。
? ? ? ? 合并的时候就是利用递归的回调机制，当我们不断进行分解时，分解到最后数据单独存在的个体后，递归就开始回调，在我们提前创建好的临时数组上进行填充，直至填充结束。
????????
? ? ? ? 在此索引范围的临时数组temp内的数据是已经有序了的，这是需要将我们的待排数组arr中在此范围内的数据替换成临时数组的有序序列，如下图所示：
?
?
2、分解过程思路和代码
? ? ? ? 分解过程可以用简单的递归实现，这里我们先进行左递归后，在进行右递归，直至数据为单独一个个体时，递归开始回调，进入合并函数merge。
?
? ? ? ? 实现代码：
/**
*
* @param arr 待归并排序数组
* @param left 待合并数组的最左边索引
* @param right 待合并数组的最右边索引
* @param temp 临时数组-用于存放有序数据
*/
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;//中间索引
//分解
mergeSort(arr, left, mid, temp);//左递归
mergeSort(arr, mid + 1, right, temp);//右递归
//合并
merge(arr, left, right, mid, temp);
}
}
????????
3、合并过程思路和代码
? ? ? ? 合并过程思路可以分为三个简单的部分：
? ? ? ? （1）有序排序的合并：对两个待合并的数组进行元素判断，分别从最左边开始进行比较，当哪边的数据符合条件，则将该数据填充进temp数组中，随后temp数组的索引往后移一位，然后继续比较，填充，直至其中的一个或两个的待合并的数组的数据已经填充完了。
//1、先有序的合并两组数据
while (i <= mid && j<=right) {
if (arr[i] < arr[j]) {//左边数组数据填入
temp[t_index] = arr[i];
i++;
} else {//右边数组数据填入
temp[t_index] = arr[j];
j++;
}
t_index++;
}? ? ? ? （2）剩余数据的合并：先进行判断待合并数组中是否有数据还没填充进去temp数组中，如果有则将剩余数据依次填充进temp中即可。
//2、将某一组剩余的数据依次填入数组中
while (t_index <= right) {//t_index>right 说明数组temp还没填到两组合并后的数据量，其中有一组剩余有数据
if(i<=mid){
temp[t_index] = arr[i];
i++;
}
if(j<=right){//右边数组填入
temp[t_index] = arr[j];
j++;
}
t_index++;
}? ? ? ? （3）序列替换：此时在范围 left-rigth 索引的temp数组中的数据是已经排序好了的，将arr数组中该范围的数据替换成temp数组的有序数据即可。
?
//将temp的数据拷贝到arr中（范围:left-right）
int copy_index=left;//arr和temp数组索引下标
while(copy_index<=right){
arr[copy_index]=temp[copy_index];//已经排序好的数据复制给arr
copy_index++;
}4、归并排序算法实现代码
import java.util.Arrays;
import java.util.Date;
public class MergeSort {
public static void main(String[] args) {
int []arr={9,8,5,4,7,2};
int []temp=new int[arr.length];
mergeSort(arr,0,arr.length-1,temp);
System.out.println(Arrays.toString(arr));
}
/**
*
* @param arr 待归并排序数组
* @param left 待合并数组的最左边索引
* @param right 待合并数组的最右边索引
* @param temp 临时数组-用于存放有序数据
*/
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;//中间索引
//分解
mergeSort(arr, left, mid, temp);//左递归
mergeSort(arr, mid + 1, right, temp);//右递归
//合并
merge(arr, left, right, mid, temp);
}
}
/**
*
* @param arr 待归并排序数组
* @param left 待合并数组的最左边索引
* @param right 待合并数组的最右边索引
* @param mid 待合并两数组的总-中间索引
* @param temp 临时数组-用于存放有序数据
*/
public static void merge(int[] arr, int left, int right, int mid, int[] temp) {
int t_index = left;//临时数组temp的合并起始索引
int i=left;//左边数组的第一个元素索引
int j=mid+1;//右边数组第一个元素的索引
//1、先有序的合并两组数据
while (i <= mid && j<=right) {
if (arr[i] < arr[j]) {//左边数组数据填入
temp[t_index] = arr[i];
i++;
} else {//右边数组数据填入
temp[t_index] = arr[j];
j++;
}
t_index++;
}
//2、将某一组剩余的数据依次填入数组中
while (t_index <= right) {//t_index>right 说明数组temp还没填到两组合并后的数据量，其中有一组剩余有数据
if(i<=mid){
temp[t_index] = arr[i];
i++;
}
if(j<=right){//右边数组填入
temp[t_index] = arr[j];
j++;
}
t_index++;
}
//将temp的数据拷贝到arr中（范围:left-right）
int copy_index=left;//arr和temp数组索引下标
while(copy_index<=right){
arr[copy_index]=temp[copy_index];//已经排序好的数据复制给arr
copy_index++;
}
}
}
?测试结果截图：
