当前位置：首页 > news >正文

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

news 2026/7/23 13:19:14

一、核心思想（分治算法）

归并排序两大阶段：分 + 治

分（分割）：不断把当前数组对半拆分成左右两个子数组，直到每个子数组只有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); // 递归拆分右区间 [mid+1, right] mergeSort(arr, mid + 1, right, temp); // 左右两个子区间都有序后，进行合并 merge(arr, left, mid, right, temp); } /** * 合并两个有序区间：[left,mid] 和 [mid+1,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(); } }