← 返回首页 📖 📖 Wiki知识库
📐 学习维度 本篇是 📖 📖 Wiki知识库 🏠 首页 🛤️ 学习路径 📚 全部文章

Java排序算法面试手写精讲 - 三、归并排序

本文是 Java排序算法面试手写精讲 的分章阅读版。

三、归并排序

核心思想

分治+合并:将数组递归拆分为单个元素,然后两两合并有序子数组。

基础版(面试快写)


public static void mergeSort(int[] arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

private static void merge(int[] arr, int left, int mid, int right) {
    int[] tmp = new int[right - left + 1];
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];

    System.arraycopy(tmp, 0, arr, left, tmp.length);
}

生产级归并排序(含优化)


public class MergeSort {

    // 优化1:提前分配临时数组,避免每次merge都new
    // 优化2:小数组切换插入排序
    // 优化3:如果两个子数组已经有序则跳过merge

    private static final int INSERTION_THRESHOLD = 16;

    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        int[] tmp = new int[arr.length];  // 只分配一次
        sort(arr, tmp, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int[] tmp, int lo, int hi) {
        if (lo >= hi) return;

        // 优化2:小数组用插入排序
        if (hi - lo + 1 < INSERTION_THRESHOLD) {
            insertSort(arr, lo, hi);
            return;
        }

        int mid = (lo + hi) >>> 1;  // 无符号右移,防止溢出
        sort(arr, tmp, lo, mid);
        sort(arr, tmp, mid + 1, hi);

        // 优化3:已有序则跳过merge
        if (arr[mid] <= arr[mid + 1]) return;

        merge(arr, tmp, lo, mid, hi);
    }

    private static void merge(int[] arr, int[] tmp, int lo, int mid, int hi) {
        // 拷贝到临时数组
        System.arraycopy(arr, lo, tmp, lo, hi - lo + 1);

        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                // 左半已耗尽
                arr[k] = tmp[j++];
            } else if (j > hi) {
                // 右半已耗尽
                arr[k] = tmp[i++];
            } else if (tmp[i] <= tmp[j]) {
                // 稳定性关键:相等时取左边
                arr[k] = tmp[i++];
            } else {
                arr[k] = tmp[j++];
            }
        }
    }

    private static void insertSort(int[] arr, int lo, int hi) {
        for (int i = lo + 1; i <= hi; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= lo && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

三个优化的意义:

特点: 稳定排序、时间复杂度恒定O(nlogn)、但需要O(n)额外空间。适合大数据量外部排序(归并段写磁盘)。


相关页面