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

目录

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. 非递归版归并排序（迭代实现）

思路：

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 + " ");
}
}
}

核心说明

总结