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

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

一、归并排序基础实现

原理

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

代码示例

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

三、变体对比表格

四、关键选择原则

1. 基础场景：优先使用基础归并排序，因其平衡性能和稳定性。
2. 递归限制：自底向上变体适合处理超大数组或避免栈溢出。
3. 内存限制：优化空间的变体仅在内存极小且时间允许时使用（如嵌入式设备）。
4. 外部排序：多路归并适用于磁盘数据排序或内存无法容纳全部数据的情况。
5. 稳定性需求：所有变体均稳定，适用于需要保持元素相对顺序的场景（如排序带键值的记录）。

通过选择合适的变体，可在特定场景下优化空间或适应不同硬件限制。例如，自底向上归并避免递归，而多路归并是处理外部数据的高效选择。