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

【java实现+4种变体完整例子】排序算法中【归并排序】的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格

backend 2025/5/20 3:22:46

以下是归并排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格：
在这里插入图片描述

一、归并排序基础实现

原理

通过分治法将数组分为两半，递归排序子数组，最后合并有序子数组。

代码示例

public class MergeSort {void sort(int[] arr) {if (arr.length < 2) return;int mid = arr.length / 2;int[] left = Arrays.copyOfRange(arr, 0, mid);int[] right = Arrays.copyOfRange(arr, mid, arr.length);sort(left); // 递归排序左半部分sort(right); // 递归排序右半部分merge(arr, left, right); // 合并结果}private void merge(int[] arr, int[] left, int[] right) {int i = 0, j = 0, k = 0;while (i < left.length && j < right.length) {if (left[i] <= right[j]) {arr[k++] = left[i++];} else {arr[k++] = right[j++];}}while (i < left.length) arr[k++] = left[i++];while (j < right.length) arr[k++] = right[j++];}
}

复杂度分析

时间复杂度：O(n log n)（所有情况）。
空间复杂度：O(n)（辅助数组）。
稳定性：稳定（相同值的元素相对顺序不变）。

二、常见变体及代码示例

1. 自底向上归并排序（迭代实现）

改进点：用循环替代递归，避免栈溢出风险。
适用场景：大数组或栈深度受限的场景。

public class IterativeMergeSort {void sort(int[] arr) {int n = arr.length;for (int size = 1; size < n; size *= 2) { // 合并子数组的大小for (int left = 0; left < n - 1; left += 2 * size) {int mid = Math.min(left + size, n);int right = Math.min(left + 2 * size, n);merge(arr, left, mid, right);}}}private void merge(int[] arr, int left, int mid, int right) {int[] temp = new int[right - left];int i = left, j = mid, k = 0;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, 0, arr, left, temp.length);}
}

2. 优化空间的归并排序

改进点：尝试减少辅助空间的使用（如原地合并）。
适用场景：内存受限场景，但可能牺牲时间效率。

public class InPlaceMergeSort {void sort(int[] arr) {int n = arr.length;for (int size = 1; size < n; size *= 2) {for (int left = 0; left < n; left += 2 * size) {int mid = left + size;int right = Math.min(left + 2 * size, n);if (mid >= n) continue;mergeInPlace(arr, left, mid, right);}}}private void mergeInPlace(int[] arr, int left, int mid, int right) {int i = left, j = mid;while (i < mid && j < right) {if (arr[i] <= arr[j]) i++;else {int temp = arr[j];for (int k = j; k > i; k--) {arr[k] = arr[k - 1];}arr[i++] = temp;mid++;j++;}}}
}

3. 多路归并排序

改进点：合并多个有序子数组，适用于外部排序或处理大量数据。
适用场景：磁盘排序或内存无法容纳整个数据时。

public class MultiwayMergeSort {void sort(int[] arr) {int n = arr.length;int runSize = 1; // 初始归并块大小while (runSize < n) {for (int left = 0; left < n; left += 2 * runSize) {int mid = left + runSize;int right = Math.min(left + 2 * runSize, n);merge(arr, left, mid, right);}runSize *= 2;}}private void merge(int[] arr, int left, int mid, int right) {int[] temp = new int[right - left];int i = left, j = mid, k = 0;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, 0, arr, left, temp.length);}
}

三、变体对比表格

变体名称	时间复杂度	空间复杂度	稳定性	主要特点	适用场景
基础归并排序	`O(n log n)`	`O(n)`	稳定	简单易实现，性能稳定	通用排序，需稳定性或数据较小
自底向上归并排序	`O(n log n)`	`O(n)`	稳定	避免递归栈溢出，适合大数组	大数据或栈深度受限的场景
优化空间的归并排序	`O(n²)`	`O(1)`	稳定	减少辅助空间，但时间复杂度可能退化	内存极度受限但时间允许的场景
多路归并排序	`O(n log n)`	`O(n)`	稳定	合并多个有序块，适合外部排序	磁盘排序或处理超大数据集