每日算法 — 使用java实现归并排序：分治策略与链表归并实现

归并排序（Merge Sort）是计算机科学中最经典的分治算法之一，由约翰·冯·诺依曼于1945年提出。它的核心思想是将数组递归地分成两半，分别排序后再合并。归并排序不仅具有稳定的 O(n log n) 时间复杂度，而且是少数几个稳定的高效排序算法之一。本文将介绍基于数组的标准实现，以及基于链表的内存优化版本。

算法原理

归并排序遵循分治（Divide and Conquer）范式，包含三个步骤：

1. 分解（Divide）：将当前区间从中间分成两个子区间。
2. 解决（Conquer）：递归地对两个子区间进行归并排序。
3. 合并（Merge）：将两个已排序的子区间合并成一个有序区间。

合并过程是归并排序的关键：使用两个指针分别指向两个已排序子数组的起始位置，每次选取较小者放入临时数组，直至某个子数组耗尽，再将剩余元素依次复制。

Java 实现

import java.util.Arrays;

/**
 * 归并排序完整实现，包含数组版本与链表版本
 */
public class MergeSort {

    /**
     * 对外接口：启动归并排序
     *
     * @param arr 待排序数组
     */
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        int[] temp = new int[arr.length]; // 预分配临时数组，避免递归中重复创建
        sort(arr, 0, arr.length - 1, temp);
    }

    /**
     * 递归分解区间
     *
     * @param arr  原数组
     * @param left 区间左边界（含）
     * @param right 区间右边界（含）
     * @param 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]
     *
     * @param arr   原数组
     * @param left  左区间起点
     * @param mid   左区间终点（右区间起点前一位）
     * @param right 右区间终点
     * @param temp  临时数组
     */
    private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left;      // 左区间指针
        int j = mid + 1;   // 右区间指针
        int 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++];
        }

        // 将临时数组中排好序的元素写回原数组
        k = 0;
        while (left <= right) {
            arr[left++] = temp[k++];
        }
    }

    // ==================== 链表版本 ====================

    /**
     * 链表节点定义
     */
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    /**
     * 链表归并排序：利用链表天然支持 O(1) 插入的特性
     * 无需额外数组，空间复杂度优化为 O(log n)（递归栈）
     *
     * @param head 链表头节点
     * @return 排序后的链表头节点
     */
    public static ListNode mergeSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 使用快慢指针找到链表中点
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 断开链表为两半
        ListNode mid = slow.next;
        slow.next = null;

        // 递归排序左右两部分
        ListNode left = mergeSortList(head);
        ListNode right = mergeSortList(mid);

        // 合并两个有序链表
        return mergeList(left, right);
    }

    /**
     * 合并两个有序链表
     */
    private static ListNode mergeList(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0); // 虚拟头节点简化边界处理
        ListNode cur = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }

        cur.next = (l1 != null) ? l1 : l2; // 拼接剩余部分
        return dummy.next;
    }

    public static void main(String[] args) {
        // 测试数组版本
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("原始数组: " + Arrays.toString(arr));
        mergeSort(arr);
        System.out.println("归并排序后: " + Arrays.toString(arr));

        // 测试链表版本
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);

        ListNode sorted = mergeSortList(head);
        System.out.print("链表排序结果: ");
        while (sorted != null) {
            System.out.print(sorted.val + " ");
            sorted = sorted.next;
        }
        System.out.println();
    }
}

复杂度分析

链表版本的空间优势在于不需要额外的 O(n) 临时数组，仅需递归栈空间。归并排序是外部排序的理想选择，因为它可以方便地处理无法一次性载入内存的大规模数据。

适用场景

归并排序特别适合以下场景：数据量巨大且需要稳定排序；链表排序（天然 O(1) 空间）；外部排序（数据无法全部放入内存）；以及作为其他算法（如求逆序对数量）的子过程。