算法之归并排序：分而治之的艺术与稳定性的典范

紫风

发布于 2025-10-14 15:16:02

1500

代码可运行

运行总次数：0

代码可运行

一、算法本质

归并排序如同精密的交响乐编排：

分乐章：将无序数组递归拆分为最小单元（单元素自然有序）
排小节：逐步合并相邻有序片段，如同编排乐谱小节
合全曲：最终合并所有有序片段得到完整有序数组

整个过程体现了"化整为零→有序重组"的哲学，是分治策略的经典实践。

二、Java实现（优化版）

public class MergeSort {
    public static void sort(int[] arr) {
        int[] temp = new int[arr.length]; // 预分配临时空间
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    private static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, temp);     // 左半乐章
            mergeSort(arr, mid + 1, right, temp); // 右半乐章
            merge(arr, left, mid, right, temp);  // 合并乐章
        }
    }

    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;    // 左序列指针
        int j = mid + 1; // 右序列指针
        int t = 0;       // 临时数组指针

        // 有序合并
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) temp[t++] = arr[i++];
            else temp[t++] = arr[j++];
        }

        // 处理剩余元素
        while (i <= mid) temp[t++] = arr[i++];
        while (j <= right) temp[t++] = arr[j++];

        // 拷贝回原数组
        t = 0;
        while (left <= right) arr[left++] = temp[t++];
    }

    public static void main(String[] args) {
        int[] data = {38, 27, 43, 3, 9, 82, 10};
        sort(data);
        System.out.println(Arrays.toString(data)); // [3, 9, 10, 27, 38, 43, 82]
    }
}

三、性能分析

指标	数值	说明
时间复杂度	O(n log n)	稳定高效
空间复杂度	O(n)	需要额外存储空间

核心优势：

稳定排序（保持相同元素相对位置）
适合外排序（处理超大规模数据）
可并行化优化（MapReduce理论基础）

四、应用场景

大数据排序：Hadoop分布式文件系统排序阶段
版本控制系统：Git的三路合并算法基础
数据库优化：MySQL的ORDER BY在内存不足时使用归并策略
音视频处理：多轨音频合成的时序对齐

工业案例：

Java集合框架的Collections.sort()底层实现（TimSort）
基因组测序中的序列比对
金融交易系统的日志合并分析

五、学习路线

新手必练：

手动模拟合并过程（画图理解）
实现降序版本（修改比较条件）
统计比较次数与移动次数

// 降序实现（仅需修改比较符号）
if (arr[i] >= arr[j]) temp[t++] = arr[i++];

高手进阶：

迭代法实现（避免递归栈溢出）
多路归并优化（k-way merge）
内存映射文件实现外排序

// 迭代版归并排序
public static void iterativeSort(int[] arr) {
    int n = arr.length;
    int[] temp = new int[n];
    
    for (int size = 1; size < n; size *= 2) {
        for (int left = 0; left < n; left += 2*size) {
            int mid = Math.min(left + size - 1, n-1);
            int right = Math.min(left + 2*size - 1, n-1);
            merge(arr, left, mid, right, temp);
        }
    }
}