归并排序是利用归并的思想实现的排序方法，该算法采用经典的分值策略，（分治法将问题分）成一些小的问题然后递归求解，而治的阶段就是将分的阶段得到的各答案“修补”在一起，即分而治之。
归并排序初始代码：
package DataStructures.sort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
int temp[] = new int[arr.length];//归并排序需要一个额外的空间
mergeSort(arr, 0, arr.length - 1, temp);
System.out.println("归并排序后：" + Arrays.toString(arr));
}
//分+合的方法
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, mid, right, temp);
}
}
//合并的方法
public static void merge(int[] arr, int left, int mid,int right, int[] temp) {
int i = left;//初始化i，左边有序序列的初始化索引
int j = mid + 1;//初始化j，右边有序序列的初始化索引
int t = 0;//指向temp数组的当前索引
//（一）
//先把左右两边的数据按照规则填充到temp数组中，
// 直到左右两边的有序序列，有一边处理完毕为止
while (i <= mid && j <= right) {
//继续做
//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
//即将左边的当前元素，拷贝到temp数组
//然后t++,i++后移
if(arr[i] <= arr[j]) {
temp[t] = arr[i];
t += 1;
i += 1;
} else {
//反之，右边的有序序列元素小于左边的有序序列元素
//将右边的有序序列填充到temp数组
temp[t] = arr[j];
t += 1;
j += 1;
}
}
//(二)
//把有剩余数据的一边的数据依次全部填充到temp
while (i <= mid) {//将左边有序序列剩余的数据，都填充到temp中去
temp[t] = arr[i];
t += 1;
i += 1;
}
while (j <= right) {//将右边有序序列剩余的数据，都填充到temp中去
temp[t] = arr[j];
t += 1;
j += 1;
}
//(三)
//将temp数组的元素拷贝到arr中去
//并不是每次都是全部数据都填充进入
t = 0;
int tempLeft = left;
//第一次合并tempLeft = 0;right = 1;tempLeft = 2 right =3 tL = 0 right = 3
//最后一次tempLeft =0；right = 7；
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
测试归排序时间的消耗：
package DataStructures.sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class MergeSort {
public static void main(String[] args) {
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000);//生成80000个随机数【0,80000000】
}
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String data1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间：" + data1Str);
//shellSort(arr);
//shellSort1(arr);;
//int arr[] = {8, 4, 5, 7, 1, 3, 6, 2};
int temp[] = new int[arr.length];//归并排序需要一个额外的空间
mergeSort(arr, 0, arr.length - 1, temp);
//System.out.println("归并排序后：" + Arrays.toString(arr));
mergeSort(arr, 0, arr.length - 1, temp);
Date data2 = new Date();
String data2Str = simpleDateFormat.format(data2);
System.out.println("排序后的时间：" + data2Str);
}
//分+合的方法
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, mid, right, temp);
}
}
//合并的方法
public static void merge(int[] arr, int left, int mid,int right, int[] temp) {
//System.out.println("***");
int i = left;//初始化i，左边有序序列的初始化索引
int j = mid + 1;//初始化j，右边有序序列的初始化索引
int t = 0;//指向temp数组的当前索引
//（一）
//先把左右两边的数据按照规则填充到temp数组中，
// 直到左右两边的有序序列，有一边处理完毕为止
while (i <= mid && j <= right) {
//继续做
//如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
//即将左边的当前元素，拷贝到temp数组
//然后t++,i++后移
if(arr[i] <= arr[j]) {
temp[t] = arr[i];
t += 1;
i += 1;
} else {
//反之，右边的有序序列元素小于左边的有序序列元素
//将右边的有序序列填充到temp数组
temp[t] = arr[j];
t += 1;
j += 1;
}
}
//(二)
//把有剩余数据的一边的数据依次全部填充到temp
while (i <= mid) {//将左边有序序列剩余的数据，都填充到temp中去
temp[t] = arr[i];
t += 1;
i += 1;
}
while (j <= right) {//将右边有序序列剩余的数据，都填充到temp中去
temp[t] = arr[j];
t += 1;
j += 1;
}
//(三)
//将temp数组的元素拷贝到arr中去
//并不是每次都是全部数据都填充进入
t = 0;
int tempLeft = left;
//第一次合并tempLeft = 0;right = 1;tempLeft = 2 right =3 tL = 0 right = 3
//最后一次tempLeft =0；right = 7；
//System.out.println("tempLeft="+tempLeft+"right="+right);
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t += 1;
tempLeft += 1;
}
}
}
