1、归并排序
Merge Sort：采用“分治法”思想的一种排序算法；步骤：
分：将数组分成多级子序列；合：逐级合并子序列，每次操作都保证合并后的组合序列有序；稳定性：稳定；复杂度：O(n log n) ，执行速度仅次于快速排序算法；
2、Java代码
package Algorithm.Sort;
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
/**
* @author yhx
* @date 2020/10/09
*/
public class MergeSort {
private static final int NUM = 80000;
public static void main(String[] args) {
// 定义待排序数组
int[] arr1 = {8, 4, 5, 7, 1, 3, 6, 2, 111};
int[] arr2 = new int[NUM];
for (int i = 0; i < NUM; i++) {
arr2[i] = (int) ((Math.random() * 2 - 1) * NUM);
}
// 临时数组
int[] temp1 = new int[arr1.length];
int[] temp2 = new int[arr2.length];
// 排序测试
System.out.println("归并排序简单测试：");
MergeAndSort mergeAndSort = new MergeAndSort();
mergeAndSort.sort(arr1, 0, arr1.length - 1, temp1);
System.out.println("arr1[] = " + Arrays.toString(arr1));
System.out.println();
// 用大量数据测试归并排序的排序速度
System.out.println("归并排序效率测试：");
// 时间标记精确到毫秒
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss:SSS");
// Date()函数用于标记时间
Date date1 = new Date();
String date1Str = simpleDateFormat.format(date1);
System.out.println("arr2[]排序前的时间是：" + date1Str);
mergeAndSort.sort(arr2, 0, arr2.length - 1, temp2);
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println("arr2[]排序后的时间是：" + date2Str);
// System.out.println("arr2[] = " + Arrays.toString(arr2));
}
}
class MergeAndSort {
/**
* 数组的排序
*
* @param arr 待排序数组
* @param left 数组左边索引
* @param right 数组右边索引
* @param temp 中转数组
*/
public void sort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
// 向左递归分解
sort(arr, left, mid, temp);
// 向右递归分解
sort(arr, mid + 1, right, temp);
// 合并
merge(arr, left, mid, right, temp);
}
}
/**
* 数组的合并
*
* @param arr 待排序数组
* @param left 左边有序序列的初始索引
* @param mid 中间索引
* @param right 右边索引
* @param temp 中转数组
*/
public void merge(int[] arr, int left, int mid, int right, int[] temp) {
// 初始化i，左边有序序列的初始索引
int i = left;
// 初始化j，右边有序序列的初始索引
int j = mid + 1;
// 指向temp数组的当前索引
int t = 0;
/*
1、先把左右两边有序的数据按规则填充到temp数组，直到左右两边的有序序列有一边处理完毕为止
2、把有剩余数据的一边的数据依次全部填充到temp
3、将temp数组的元素拷贝到arr
*/
// --1--
while (i <= mid && j <= right) {
// 如果左边有序序列的当前元素小于等于右边有序序列的当前元素，就将左边当前元素填充到temp数组中，然后t和i后移
if (arr[i] <= arr[j]) {
temp[t] = arr[i];
t++;
i++;
}
// 反之，将右边当前元素填充到temp数组中，然后t和j后移
else {
temp[t] = arr[j];
t++;
j++;
}
}
// --2--
// 左边
while (i <= mid) {
temp[t] = arr[i];
t++;
i++;
}
// 右边
while (j <= right) {
temp[t] = arr[j];
t++;
j++;
}
// --3--
t = 0;
int tempLeft = left;
while (tempLeft <= right) {
arr[tempLeft] = temp[t];
t++;
tempLeft++;
}
}
}
3、运行结果
归并排序简单测试：
arr1[] = [1, 2, 3, 4, 5, 6, 7, 8, 111]
归并排序效率测试：
arr2[]排序前的时间是：2020-10-09 08:51:48:402
arr2[]排序后的时间是：2020-10-09 08:51:48:413
