以下是归并排序的详细解析，包含基础实现、常见变体的完整代码示例，以及各变体的对比表格：
一、归并排序基础实现
原理
通过分治法将数组分为两半，递归排序子数组，最后合并有序子数组。
代码示例
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) | 稳定 | 合并多个有序块，适合外部排序 | 磁盘排序或处理超大数据集 |
四、关键选择原则
- 基础场景：优先使用基础归并排序，因其平衡性能和稳定性。
- 递归限制：自底向上变体适合处理超大数组或避免栈溢出。
- 内存限制：优化空间的变体仅在内存极小且时间允许时使用（如嵌入式设备）。
- 外部排序：多路归并适用于磁盘数据排序或内存无法容纳全部数据的情况。
- 稳定性需求：所有变体均稳定，适用于需要保持元素相对顺序的场景（如排序带键值的记录）。
通过选择合适的变体，可在特定场景下优化空间或适应不同硬件限制。例如，自底向上归并避免递归，而多路归并是处理外部数据的高效选择。