【数据结构排序算法篇】----归并排序【实战演练】

作为一名对技术充满热情的学习者，我一直以来都深刻地体会到知识的广度和深度。在这个不断演变的数字时代，我远非专家，而是一位不断追求进步的旅行者。通过这篇博客，我想分享我在某个领域的学习经验，与大家共同探讨、共同成长。请大家以开放的心态阅读，相信你们也会在这段知识之旅中找到启示。

前言

我们继续学习下一个排序，归并排序，这是一个重要的排序，排序思想也很重要，这种排序也很高效，希望同学们可以认真阅读。

一、什么是归并排序

归并排序（Merge Sort）是一种高效的排序算法，采用分治的策略来对数组或列表进行排序。基本思想是将原始数组分成若干子数组，对每个子数组进行排序，然后将它们合并成一个全部有序的数组。

归并排序算法的主要步骤如下：

1. 分解：递归地将当前数组分成两个长度差不多的子数组。
2. 解决：递归地对子数组进行归并排序，如果子数组长度是 1 或者更小，则不需要继绀做分解，因为长度为 1 的数组自然而然就是有序的。
3. 合并：将两个有序的子数组合并成一个有序的数组。

拿一个简单的数组 [38, 27, 43, 3, 9, 82, 10] 举例，归并排序的过程如下：

1. 分解数组为 [38, 27, 43, 3] 和 [9, 82, 10]。
2. 继续分解 [38, 27, 43, 3] 为 [38, 27] 和 [43, 3]，以及将 [9, 82, 10] 分解为 [9, 82] 和 [10]。
3. 进一步分解 [38, 27] 为 [38] 和 [27]，[43, 3] 为 [43] 和 [3]，以及 [9, 82] 为 [9] 和 [82]。因为每个数组只有一个元素，开始合并。
4. 合并 [38] 和 [27] 成 [27, 38]，合并 [43] 和 [3] 成 [3, 43]，以及 [9] 和 [82] 成 [9, 82]。
5. 将两个有序数组 [27, 38] 和 [3, 43] 合并成一个有序数组 [3, 27, 38, 43]，将 [9, 82] 和 [10] 合并成 [9, 10, 82]。
6. 最终，将 [3, 27, 38, 43] 和 [9, 10, 82] 合并成最终的有序数组 [3, 9, 10, 27, 38, 43, 82]。

归并排序需要额外的内存空间来存储临时数组，所以它不是一个原地排序算法。不过，归并排序特别适合处理大数据集，并且是稳定的排序算法，即具有相等键值的元素经排序后其相对位置不变。

归并排序算法的时间复杂度为 O(n log n)，其中 n 是数组或列表中元素的数量。

这个复杂度来自于两个主要步骤：

1. 分解步骤：数组被一分为二，直到每个子数组只有一个元素。分解数组的过程是对数阶的，即每次操作减少一半的问题规模，所以分解步骤大约需要 log n 层递归。
   
2. 合并步骤：在每一层递归中，都要合并子数组。虽然每层的合并操作涉及到整个数组，但由于有 log n 层，合并操作的总时间复杂度是线性对数阶的，即 O(n log n)。
   

总结起来：归并排序的时间复杂度主要由多次的切分（对数阶次数，即 log n）和在每个切分阶段执行的合并操作（每次操作需要线性时间，即 n）决定，所以总体上是 O(n log n)。这使得归并排序在最坏、平均和最好情况下的时间复杂度都是 O(n logn)，这是一种非常稳定的性能表现。

二、练习

简单练习

考虑以下整数数组：

[29, 10, 14, 37, 13]

让我们用归并排序一步步排序这个数组。

Step 1: 分割数组

首先，将整个数组分割成更小的部分，直到每个部分仅包含一个元素：

1. 初始数组: [29, 10, 14, 37, 13]
2. 分割为两部分: [29, 10] 和 [14, 37, 13]
3. 继续分割: [29], [10], [14], [37, 13]
4. 最后分割 [37, 13] 为: [37] 和 [13]

Step 2: 合并与排序

现在开始合并这些单个元素，组成排序好的子数组：

1. 合并 [29] 和 [10] 得到 [10, 29]
2. 合并 [37] 和 [13] 得到 [13, 37]
3. 由于 [14] 已经是排序好的，它可以直接与 [13, 37] 合并为 [13, 14, 37]

现在，我们有 [10, 29] 和 [13, 14, 37]，要合并它们成为一个排序好的大数组。

Step 3: 最终合并

1. 取 [10] 和 [13] 中较小的数，所以 [10] 是第一个。
2. [29] 与 [13] 比较，选择 [13] 为下一个数，接着是 [14]。
3. [29] 下一个与 [37] 比较，我们选 [29]。
4. 最后的数是 [37]。

合并后的数组是：[10, 13, 14, 29, 37]

较难练习

让我们对以下数组进行排序：

[34, -42, 0, 15, -9, 27, 51, 3, 12, 18]

Step 1: 分割数组

首先，分割数组直到每个子数组都是单个元素：

1. 初始数组: [34, -42, 0, 15, -9, 27, 51, 3, 12, 18]
2. 分割数组为两部分: [34, -42, 0, 15, -9] 和 [27, 51, 3, 12, 18]
3. 继续分割前半部分: [34, -42] 和 [0, 15, -9]
4. 继续分割后半部分: [27, 51] 和 [3, 12, 18]
5. 继续分割，直到每个子数组只包含一个元素，我们得到: [34], [-42], [0], [15], [-9], [27], [51], [3], [12], [18]

Step 2: 合并与排序

然后开始合并子数组，同时也排序这些数组：

1. 合并 [34] 和 [-42] 得到 [-42, 34]
2. 合并 [0] 和 [15] 得到 [0, 15]
3. [-9] 已经是单个元素，因此它暂时保持不变
4. 合并 [27] 和 [51] 得到 [27, 51]
5. 合并 [3] 和 [12] 得到 [3, 12]
6. [18] 已经是单个元素，因此它暂时保持不变

现在有，[-42, 34]，[0, 15]，[-9]，[27, 51]，[3, 12] 和 [18]。

继续合并剩余的数组：

1. 合并 [-42, 34] 和 [0, 15] 得到 [-42, 0, 15, 34]
2. 合并 [-9] 和上一步中已经排序的数组 [-42, 0, 15, 34] 得到 [-42, -9, 0, 15, 34]
3. 合并 [27, 51] 和 [3, 12] 得到 [3, 12, 27, 51]
4. 合并 [18] 和上一步中的 [3, 12, 27, 51] 得到 [3, 12, 18, 27, 51]

现在，我们有 [-42, -9, 0, 15, 34] 和 [3, 12, 18, 27, 51]。

Step 3: 最终合并

1. 比较 [-42, -9, 0, 15, 34] 和 [3, 12, 18, 27, 51] 中的第一个元素，取出 -42。
2. 比较 -9 和 3，接下来选择 -9。
3. 接着是 0。
4. 之后 3 比 15 小，所以选择 3。
5. 继续这样比较并取出元素直到两个数组都空了。

最终合并排序后的数组是：

[-42, -9, 0, 3, 12, 15, 18, 27, 34, 51]

这样，通过一系列的分割、合并和排序步骤，我们完成了复杂整数数组的归并排序。

三、经典面试题

• 面试题:
  假设你有一个整数数组，数组中的一些数可能重复。请实现一个归并排序的版本，该版本除了排序数组外，还能统计数组中每个数字出现的次数。最后输出排序后的数组以及一个包含每个数字及其出现次数的映射（Map）。

这个问题的复杂之处在于，在对数组进行排序的同时，你还需要跟踪每个数字的出现次数。

• 解法:

以下是一个可能的Java解决方案，其中包含了详细的注释来解释各部分代码的功能。

首先，实现一个标准的归并排序过程:

public static void mergeSort(int[] array, int left, int right, Map<Integer, Integer> frequencyMap) {
    if (left < right) {
        // 找到中间位置，分割数组为两部分
        int mid = left + (right - left) / 2;
        // 对两个子数组递归调用归并排序
        mergeSort(array, left, mid, frequencyMap);
        mergeSort(array, mid + 1, right, frequencyMap);
        // 合并两个已排序的子数组
        merge(array, left, mid, right, frequencyMap);
    }
}
private static void merge(int[] array, int left, int mid, int right, Map<Integer, Integer> frequencyMap) {
    // 创建临时数组存放左右两边的数组
    int[] leftArray = new int[mid - left + 1];
    int[] rightArray = new int[right - mid];
    // 填充这两个临时数组
    for (int i = 0; i < leftArray.length; ++i)
        leftArray[i] = array[left + i];
    for (int j = 0; j < rightArray.length; ++j)
        rightArray[j] = array[mid + 1 + j];
    // 合并临时数组回原数组中
    int i = 0, j = 0;
    int k = left;
    while (i < leftArray.length && j < rightArray.length) {
        if (leftArray[i] <= rightArray[j]) {
            array[k] = leftArray[i];
            updateFrequencyMap(frequencyMap, leftArray[i]);
            i++;
        } else {
            array[k] = rightArray[j];
            updateFrequencyMap(frequencyMap, rightArray[j]);
            j++;
        }
        k++;
    }
    // 处理剩下的元素
    while (i < leftArray.length) {
        array[k] = leftArray[i];
        updateFrequencyMap(frequencyMap, leftArray[i]);
        i++;
        k++;
    }
    while (j < rightArray.length) {
        array[k] = rightArray[j];
        updateFrequencyMap(frequencyMap, rightArray[j]);
        j++;
        k++;
    }
}
private static void updateFrequencyMap(Map<Integer, Integer> frequencyMap, int key) {
    frequencyMap.put(key, frequencyMap.getOrDefault(key, 0) + 1);
}

在上面的代码中，我们用 mergeSort 方法递归地将数组分成更小的片段，直到片段只包含单一元素。然后，通过 merge 方法将这些片段合并回去，从而得到排序好的数组。我们也增加了 updateFrequencyMap 辅助方法，用于在合并过程中更新数字的出现次数。

这样的实现能够在排序过程中，忽略额外的遍历，即时地构建频率映射。调用 mergeSort 函数时，应传入一个空的 Map 用来存放数字频率，例如：

Map<Integer, Integer> frequencyMap = new HashMap<>();
int[] array = {4, 5, 6, 4, 6, 3};
mergeSort(array, 0, array.length - 1, frequencyMap);
System.out.println(Arrays.toString(array));         // 输出排序后的数组
System.out.println(frequencyMap.toString());        // 输出数字及其频率的映射

这个方法在一遍归并排序过程中，就填入了数字频率的信息，既高效又简洁。面试时，这种能力展示出你有能力处理复杂问题，并能优雅地在现有算法框架中添加额外功能。

四、思考

在 updateFrequencyMap 方法中，为什么要使用 frequencyMap.getOrDefault(key, 0) + 1 而不是直接使用 frequencyMap.get(key) + 1？

总结

博主持续输出排序算法，更加偏向Java方面，对于面试题的学习，希望同学们有Java基础，才能更好的吸收知识。

感谢大家抽出宝贵的时间来阅读博主的博客,新人博主,感谢大家关注点赞,祝大家未来的学习工作生活一帆风顺,加油!!!