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

归并排序 Java 实现（递归 + 非递归）

news 2026/5/28 13:12:29

1. 递归版归并排序（最常用）

2. 非递归版归并排序（迭代实现）

核心说明

总结

归并排序是分治思想的经典实现，核心是：拆分数组→合并有序子数组。时间复杂度：O(n log n)，空间复杂度：O(n)，稳定排序。

下面直接给你可直接运行的 Java 代码，包含递归版和非递归（迭代）版。

1. 递归版归并排序（最常用）

思路：

把数组从中间拆分成左右两部分
递归排序左右子数组
合并两个有序子数组为一个有序数组

public class MergeSort { // 对外暴露的排序方法 public static void mergeSort(int[] arr) { if (arr == null || arr.length <= 1) { return; } // 临时数组，避免递归中频繁创建数组 int[] temp = new int[arr.length]; sort(arr, 0, arr.length - 1, temp); } // 递归拆分 + 排序 private static void sort(int[] arr, int left, int right, int[] temp) { // 递归终止条件：子数组只有一个元素 if (left >= right) { return; } int mid = left + (right - left) / 2; // 防止溢出 sort(arr, left, mid, temp); // 排序左半部分 sort(arr, mid + 1, right, temp); // 排序右半部分 merge(arr, left, mid, right, temp); // 合并两个有序子数组 } // 合并两个有序区间 [left, mid] 和 [mid+1, right] private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; // 左数组起始指针 int j = mid + 1; // 右数组起始指针 int k = left; // 临时数组指针 // 把两个有序子数组按顺序放入 temp while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } // 拷贝左数组剩余元素 while (i <= mid) { temp[k++] = arr[i++]; } // 拷贝右数组剩余元素 while (j <= right) { temp[k++] = arr[j++]; } // 把 temp 中排好序的部分复制回原数组 System.arraycopy(temp, left, arr, left, right - left + 1); } // 测试 public static void main(String[] args) { int[] arr = {8, 4, 5, 7, 1, 3, 6, 2}; System.out.println("排序前："); for (int num : arr) { System.out.print(num + " "); } mergeSort(arr); System.out.println("\n递归归并排序后："); for (int num : arr) { System.out.print(num + " "); } } }

2. 非递归版归并排序（迭代实现）

思路：

从最小子数组长度 = 1开始，两两合并
子数组长度翻倍（1→2→4→8…）
直到合并成整个数组无递归，避免栈溢出，适合大数据量

public class MergeSortNonRecursive { public static void mergeSortNonRecursive(int[] arr) { if (arr == null || arr.length <= 1) { return; } int n = arr.length; int[] temp = new int[n]; int mergeSize = 1; // 初始合并单元长度：1 while (mergeSize < n) { // 每次从左到右依次合并两个长度为 mergeSize 的子数组 for (int left = 0; left < n; left += mergeSize * 2) { int mid = left + mergeSize - 1; // 右边界不能越界 int right = Math.min(left + mergeSize * 2 - 1, n - 1); // 只有左半边，无需合并 if (mid >= right) { break; } // 合并逻辑和递归版完全一样 merge(arr, left, mid, right, temp); } // 子数组长度翻倍 mergeSize *= 2; } } // 合并方法和递归版完全相同 private static void merge(int[] arr, int left, int mid, int right, int[] temp) { int i = left; int j = mid + 1; int k = left; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } System.arraycopy(temp, left, arr, left, right - left + 1); } // 测试 public static void main(String[] args) { int[] arr = {8, 4, 5, 7, 1, 3, 6, 2}; System.out.println("排序前："); for (int num : arr) { System.out.print(num + " "); } mergeSortNonRecursive(arr); System.out.println("\n非递归归并排序后："); for (int num : arr) { System.out.print(num + " "); } } }