Java归并排序

归并排序图示

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，采用了分治法（（Divide and Conquer））的思想。

大体分为 拆分 与 组合 两个步骤

拆分：将原始数组依次对半拆分，直至每个数组中只有一个数字，是分的过程。

组合：每两个数组中的数字排序后合并到一个数组中，直至合并成一个数组，是治的过程。

注意：拆分时，并不是真正的将原数组中的数取出来放入另一个数组，而是通过两个索引划分区段

程序运行时，先左递归拆分到最小单位，再右递归拆分到最小单位，然后递归组合，最终组合成的数组就是排序好的数组，如下图所示：

---

参考代码

拆分 /** * 归并排序算法 * * @param arr 待拆分数组 * @param startIndex 待拆分数组的起始索引 * @param endIndex 待拆分数组的最后索引 * @param temp 临时组合数组，提前分配临时数组，不用每次调用方法分配，提高效率 */ public static void mergeSort(int[] arr, int startIndex, int endIndex, int[] temp) { if (startIndex >= endIndex) return; // 不满足拆分条件，直接返回 int mid = (startIndex + endIndex) / 2; // 对半拆分，索引 mergeSort(arr, startIndex, mid, temp); // 左递归继续拆分 mergeSort(arr, mid + 1, endIndex, temp); // 右递归继续拆分 merge(arr, startIndex, mid, endIndex, temp); // 左右都递归拆分完后，进行组合 } 组合 /** * 合并方法：将两个数组中的元素排序后放入同一个数组中 * * @param arr 待排序数组 * @param startIndex 左边数组的起始索引 * @param mid 分开左右数组的中间索引 * @param endIndex 右边数组的最后索引 * @param temp 临时组合数组 */ public static void merge(int[] arr, int startIndex, int mid, int endIndex, int[] temp) { int left = startIndex; // 初始化左数组的指针，指向左数组的起点 int right = mid + 1; // 初始化右数组的指针，指向右数组的起点 int t = 0; // 指向临时存储数组，用于存放元素 // 左右两边的数组有任意一边的数组遍历完成退出循环 while (left <= mid && right <= endIndex) { if (arr[left] <= arr[right]) { // 左数组的数小，存入 temp temp[t] = arr[left]; t++; left++; } else { // 否则将右数组中的元素存入 temp temp[t] = arr[right]; t++; right++; } } // 如果左数组有剩余，依次存入 temp while (left <= mid) { temp[t] = arr[left]; t++; left++; } // 如果右数组有剩余，依次存入 temp while (right <= endIndex) { temp[t] = arr[right]; t++; right++; } // 上面数组合并完成后，将 temp 中排好的数字依次存入 arr 对应的位置 ⇒ 从 startIndex 到 endIndex t = 0; // 初始化 temp 的指针 while (startIndex <= endIndex) { arr[startIndex] = temp[t]; startIndex++; t++; } }

---

测试排序效果

public static void main(String[] args) { int[] arr = {3, 5, 8, 1, 2, 9, 4, 7, 6}; int[] temp = new int[arr.length]; System.out.println("排序前：" + Arrays.toString(arr)); mergeSort(arr, 0, arr.length - 1, temp); System.out.println("归并排序：" + Arrays.toString(arr)); } 归并排序涉及递归，所以将临时数组定义在外面，减少分配空间的次数，提高效率

1亿随机数测试排序时间

public static void main(String[] args) { int[] arrTime = new int[100000000]; for (int i = 0; i < 100000000; i++) { arrTime[i] = (int) (Math.random() * 100000000); } long former = System.currentTimeMillis(); merge(arrTime, 0, arrTime.length / 2, arrTime.length - 1, new int[arrTime.length]); long later = System.currentTimeMillis(); System.out.println("时间：" + (later - former) + " 毫秒"); }