宝藏速成秘籍（6）归并排序法

一、前言

1.1、概念

       归并排序（Merge Sort）是一种基于分治思想的排序算法。它将数组分成两个子数组，分别对这两个子数组进行排序，然后再将它们合并成一个有序的数组。归并排序是一种经典的分治算法，它的核心思想是将待排序的序列逐步划分成更小的子序列，然后将这些子序列两两合并成更大的有序子序列，最终得到一个完全有序的序列。

 1.2、排序步骤   

1.分割（Divide）：将数组递归地分成两个子数组，直到每个子数组只有一个元素。
2.合并（Merge）：将两个有序的子数组合并成一个有序的数组。

二、方法分析 

1. 划分: 将待排序的序列不断递归地划分成更小的子序列，直到每个子序列只剩下一个元素。

2. 合并: 将两个有序的子序列合并为一个有序的序列。在合并过程中，创建一个临时数组来存储合并后的结果。比较两个子序列的第一个元素，将较小的元素放入临时数组，并将对应子序列的指针向后移动。重复这个过程，直到其中一个子序列的元素全部合并完毕，然后将另一个子序列的剩余元素依次放入临时数组。

3. 递归: 通过递归地调用自身，将这些子序列合并成越来越大的有序子序列，直到最终合并成一个完全有序的序列。

三、举例说明  

假设我们有一个数组 [38, 27, 43, 3, 9, 82, 10]：

1.分割：
   - [38, 27, 43, 3, 9, 82, 10] 分成 [38, 27, 43] 和 [3, 9, 82, 10]
   - [38, 27, 43] 分成 [38] 和 [27, 43]
   - [27, 43] 分成 [27] 和 [43]
   - [3, 9, 82, 10] 分成 [3, 9] 和 [82, 10]
   - [3, 9] 分成 [3] 和 [9]
   - [82, 10] 分成 [82] 和 [10]

2.合并：
   - 合并 [27] 和 [43] 得到 [27, 43]
   - 合并 [38] 和 [27, 43] 得到 [27, 38, 43]
   - 合并 [3] 和 [9] 得到 [3, 9]
   - 合并 [82] 和 [10] 得到 [10, 82]
   - 合并 [3, 9] 和 [10, 82] 得到 [3, 9, 10, 82]
   - 最后合并 [27, 38, 43] 和 [3, 9, 10, 82] 得到 [3, 9, 10, 27, 38, 43, 82]

这样，我们就得到了最终排序后的数组。

 四、编码实现  

 下面是用Java实现的归并排序算法：

public class MergeSort {

    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }

        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) / 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[] arr = { 5, 9, 3, 1, 8, 6, 4, 2, 7 };
        mergeSort(arr);

        System.out.println("排序后的数组：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
 

 运行结果：

 五、方法评价  

       归并排序的时间复杂度为O(nlogn)，其中n是待排序序列的长度。这是因为每次划分序列的过程需要花费O(logn)的时间，而每次合并序列的过程需要花费O(n)的时间。同时，归并排序是稳定的排序算法，即保持相等元素的相对顺序不变。但是，归并排序的空间复杂度为O(n)，因为在合并过程中需要使用额外的临时数组。

 结语 

 成功没有捷径

如果有，那一定是上天对坚持不懈人的眷爱

！！！