归并排序的核心思想首先可以从一个问题入手：
如果我们在排序时遇到以下两个数组有序数组，有没有一种最快速的方法排序呢？
对我们而言，把两个数组合成有序数列如果用之前的方法在遍历一遍太过麻烦，最快速度方法应该是像榫卯结构一样直接插入
有了思路，接下来就是我们如何把这一思想转化为计算机语言了
我们先新建一个长度为上面两个数组长度之和的新数组,然后比较两个数组的第一个元素，在如图中，是1和2比较，我们把较小的数组1拿出来放在新数组的首个
接下来比较左面数组的第二个和右面数组的第一个，把较小数放在数组的第二个位置，以此比较，放置，排序完成。
我们先通过代码来实现这一步：
package demo4;
import java.util.Arrays;
/**
* 归并排序
*
*
* 2019年2月14日
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[]{1,3,5,7,9,2,4,6};
System.out.println(Arrays.toString(arr));
merge(arr,0,4,7);
System.out.println(Arrays.toString(arr));
}
//创造开始，中间，结束位置的变量，目的是把一个数组拆成两个
public static void merge(int[] arr,int low,int middle,int high){
//创造归并后的临时数组
int[] temp =new int[arr.length];
//记录第一个数组需要遍历的下标
int i =low;
//记录第二个数组需要遍历的下标
int j = middle+1;
//用于记录在临时数组中存放的下标
int index = 0;
System.out.println("i="+i+" "+"j="+j);
//遍历两个数组去除小弟数字，放入临时数组
while(i<=middle&&j<=high){
//第一个数组的数更小
if(arr[i]<arr[j]){
temp[index]=arr[i];
//下标后移
i++;
index++;
}else{//第二个数组更小
temp[index]=arr[j];
j++;
index++;
}
}
//处理多余的数据（两个数组不等长，一方比完跳出循环）
//直接把剩余元素追加到数组之后
while(j<=high){
temp[index]=arr[j];
j++;
index++;
}
while(i<=middle){
temp[index]=arr[i];
i++;
index++;
}
//把临时数组赋给原数组
for(int n=0;n<arr.length;n++){
arr[n]=temp[n];
}
}
}
运行结果无误，但是我们可不可以把这个方法给推广一下呢，对于任意混乱数组也可以使用此方法排序？
解决了以上的问题,我们就可以解释归并排序的核心思想：
就是先把数组拆分为两部分，再继续拆分下去，直到被拆为单个元素组成的数组，然后相邻的小数组进行比较，排序，合并，小数组就不断吸收其他元素，演变为两个中等数组的比较，最后变成数组的两部分之间的排序合并问题，问题就变成了我们刚才解决的问题了：
两个有序数组之间的合并排序？
那么对于单个元素，我们刚才的这个方法是否有效？
经检验，是可以的——
这样问题就转化为了如何利用递归的思想，让数组从单个元素的“小数组”一直排序到两部分的大数组。
先调用自身拍好左面的数组，在排好右面的，之后把两部分归并
// 归并排序
public static void mergeSort(int[] arr, int low, int high) {
int middle = (high + low) / 2;
if (low < high) {
mergeSort(arr, low, middle);
mergeSort(arr, middle + 1, high);
// 两个数组被拆分完成,进行归并的操作
merge(arr, low, middle, high);
}
}
运行结果如下：
全部代码如下：
package demo4;
import java.util.Arrays;
/**
* 归并排序
*
*
* 2019年2月14日
*/
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[] {5,7,6,9,4,2,3,8};
System.out.println("原数组" + Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1);
System.out.println("排序后" + Arrays.toString(arr));
}
// 归并排序
public static void mergeSort(int[] arr, int low, int high) {
int middle = (high + low) / 2;
if (low < high) {
mergeSort(arr, low, middle);
mergeSort(arr, middle + 1, high);
// 两个数组被拆分完成,进行归并的操作
merge(arr, low, middle, high);
}
}
// 创造开始，中间，结束位置的变量，目的是把一个数组拆成两个
public static void merge(int[] arr, int low, int middle, int high) {
// 创造归并后的临时数组
int[] temp = new int[high-low+1];
// 记录第一个数组需要遍历的下标
int i = low;
// 记录第二个数组需要遍历的下标
int j = middle + 1;
// 用于记录在临时数组中存放的下标
int index = 0;
// 遍历两个数组去除小弟数字，放入临时数组
while (i <= middle && j <= high) {
// 第一个数组的数更小
if (arr[i] < arr[j]) {
temp[index] = arr[i];
// 下标后移
i++;
index++;
} else {// 第二个数组更小
temp[index] = arr[j];
j++;
index++;
}
}
// 处理多余的数据（两个数组不等长，一方比完跳出循环）
// 直接把剩余元素追加到数组之后
while (j <= high) {
temp[index] = arr[j];
j++;
index++;
}
while (i <= middle) {
temp[index] = arr[i];
i++;
index++;
}
// 把临时数组赋给原数组
for (int n = 0; n < temp.length; n++) {
arr[n+low] = temp[n];
}
}
}