当前位置：首页 > article >正文

【唐叔学算法】第20天：归并之道-二路归并与多路归并排序的Java实现及性能解析

article 2024/12/28 0:56:09

引言

归并排序（Merge Sort）是一种经典的分治算法，其核心思想是将一个复杂问题分解为多个子问题，分别解决后再将结果合并。归并排序在排序领域中以其稳定的性能和优雅的分治思想而著称。本文将深入探讨两种典型的归并排序算法：二路归并排序和多路归并排序，分析它们的原理、实现细节、时间复杂度和空间复杂度，并通过Java代码进行具体实现。

二路归并排序：分而治之的经典排序算法

算法原理

二路归并排序（Two-way Merge Sort）是一种基于分治思想的排序算法。其核心思想是将待排序的序列分成两个子序列，分别对这两个子序列进行排序，然后将排序后的子序列合并成一个有序序列。

算法步骤

分解：将待排序的序列递归地分解为两个子序列，直到每个子序列只包含一个元素。
排序：对每个子序列进行排序（单个元素本身就是有序的）。
合并：将两个有序的子序列合并为一个有序序列。

时间复杂度与空间复杂度

时间复杂度：O(n log n)，其中n是序列的长度。每次分解和合并的时间复杂度都是O(n)，而分解的层数是O(log n)。
空间复杂度：O(n)，归并排序需要额外的存储空间来存储合并过程中的临时数据。

Java实现

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            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 n1 = mid - left + 1; // 左子序列的长度
        int n2 = right - mid; // 右子序列的长度

        // 创建临时数组
        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        // 复制数据到临时数组
        for (int i = 0; i < n1; i++) {
            leftArr[i] = arr[left + i];
        }
        for (int i = 0; i < n2; i++) {
            rightArr[i] = arr[mid + 1 + i];
        }

        // 合并两个有序子序列
        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // 复制剩余元素
        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }
        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

多路归并排序：扩展归并排序的应用场景

算法原理

多路归并排序（Multi-way Merge Sort）是二路归并排序的扩展，其核心思想是将待排序的序列分成多个子序列，分别对这些子序列进行排序，然后将排序后的子序列合并为一个有序序列。多路归并排序通常用于外部排序（如处理大规模数据时）。

算法步骤

分解：将待排序的序列递归地分解为多个子序列，直到每个子序列只包含一个元素。
排序：对每个子序列进行排序（单个元素本身就是有序的）。
合并：将多个有序的子序列合并为一个有序序列。

时间复杂度与空间复杂度

时间复杂度：O(n log_k n)，其中n是序列的长度，k是归并的路数。相比于二路归并，多路归并的分解层数更少，但每层的合并操作更复杂。
空间复杂度：O(n)，多路归并排序同样需要额外的存储空间来存储合并过程中的临时数据。

Java实现

以下是一个简单的三路归并排序的实现：

public class MultiWayMergeSort {
    public static void multiWayMergeSort(int[] arr, int left, int right, int k) {
        if (left < right) {
            int[] midPoints = new int[k - 1];
            for (int i = 0; i < k - 1; i++) {
                midPoints[i] = left + (right - left) * (i + 1) / k;
            }

            // 递归排序每个子序列
            for (int i = 0; i < k; i++) {
                int subLeft = (i == 0) ? left : midPoints[i - 1] + 1;
                int subRight = (i == k - 1) ? right : midPoints[i];
                multiWayMergeSort(arr, subLeft, subRight, k);
            }

            // 合并多个有序子序列
            merge(arr, left, midPoints, right);
        }
    }

    private static void merge(int[] arr, int left, int[] midPoints, int right) {
        // 合并多个有序子序列的逻辑较为复杂，此处省略具体实现
        // 实际应用中可以使用优先队列（堆）来优化合并过程
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7, 8, 9, 1, 2};
        multiWayMergeSort(arr, 0, arr.length - 1, 3); // 三路归并
        System.out.println("Sorted array: ");
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}

对比与总结

二路归并排序 vs 多路归并排序

特性	二路归并排序	多路归并排序
时间复杂度	O(n log n)	O(n log_k n)
空间复杂度	O(n)	O(n)
适用场景	内部排序	外部排序（大规模数据）
实现复杂度	简单	复杂