归并排序 Java 实现 + 思路详解

一、核心思想分治算法归并排序两大阶段分 治分分割不断把当前数组对半拆分成左右两个子数组直到每个子数组只有1 个元素单个元素天然有序。治合并将两个已经有序的子数组合并成一个有序数组不断向上合并最终整个数组有序。算法特性面试重点时间复杂度稳定 O (nlogn)最好、最坏、平均都一样不受原始数组顺序影响空间复杂度O(n)需要额外辅助数组稳定排序缺点需要开辟额外内存不适合超大数量级内存紧张场景二、完整代码实现java运行public class MergeSort { public static void main(String[] args) { int[] arr {8, 4, 5, 7, 1, 3, 6, 2}; System.out.println(排序前); printArr(arr); // 创建临时数组避免递归反复创建优化性能 int[] temp new int[arr.length]; mergeSort(arr, 0, arr.length - 1, temp); System.out.println(排序后); printArr(arr); } /** * 递归分割数组 * param arr 原始数组 * param left 当前区间左边界 * param right 当前区间右边界 * param temp 合并使用的临时数组 */ public static void mergeSort(int[] arr, int left, int right, int[] temp) { // 递归终止条件区间只有一个元素 if (left right) { return; } // 中间分割点 int mid left (right - left) / 2; // 递归拆分左区间 [left, mid] mergeSort(arr, left, mid, temp); // 递归拆分右区间 [mid1, right] mergeSort(arr, mid 1, right, temp); // 左右两个子区间都有序后进行合并 merge(arr, left, mid, right, temp); } /** * 合并两个有序区间[left,mid] 和 [mid1,right] */ public static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i left; // 左有序数组起始指针 int j mid 1; // 右有序数组起始指针 int t 0; // temp数组指针 // 依次比较左右两个有序数组小的放入临时数组 while (i mid j right) { if (arr[i] arr[j]) { temp[t] arr[i]; } else { temp[t] arr[j]; } } // 左边剩余元素移入temp while (i mid) { temp[t] arr[i]; } // 右边剩余元素移入temp while (j right) { temp[t] arr[j]; } // 将temp中有序数据拷贝回原数组对应区间 t 0; while (left right) { arr[left] temp[t]; } } // 打印数组 public static void printArr(int[] arr) { for (int num : arr) { System.out.print(num ); } System.out.println(); } }三、流程简单推演数组[8,4,5,7,1,3,6,2]不断对半拆分[8,4,5,7]和[1,3,6,2]继续拆分直到单元[8] [4] [5] [7] [1] [3] [6] [2]两两合并[8][4]→[4,8][5][7]→[5,7][1][3]→[1,3][6][2]→[2,6]继续向上合并[4,8] [5,7]→[4,5,7,8][1,3] [2,6]→[1,2,3,6]最终合并两大块[4,5,7,8] [1,2,3,6]→[1,2,3,4,5,6,7,8]四、面试对比小结快排不稳定原地排序少量额外空间平均性能最好最坏 O (n²)归并排序稳定必须 O (n) 辅助空间复杂度稳定 O (nlogn)堆排序不稳定O (1) 额外空间O (nlogn)拓展Java 底层Arrays.sort()基础类型使用双轴快排 引用类型使用归并排序保证稳定。