算法系列（Algorithm）- 归并排序

1. 核心思想与工作原理

1.1 基本思想

归并排序的核心思想是"分而治之"。它将一个大的排序问题分解为若干小的子问题，分别解决这些子问题，然后将已排序的子问题合并成最终的有序序列。

具体来说，归并排序的工作流程可以分为三个主要步骤：

1. 分割（Divide）：将待排序的数组递归地分成两半，直到每个子数组只包含一个元素（一个元素的数组自然是有序的）
2. 排序（Conquer）：对最小的子数组进行排序（实际上单个元素不需要排序）
3. 合并（Merge）：将两个已排序的子数组合并成一个更大的有序数组

1.2 算法执行过程

通过一个具体例子来理解归并排序的过程：

假设有未排序数组：{6, 202, 100, 301, 38, 8, 1}

第一次分割与合并：

• 分割：{6, 202, 100, 301} 和 {38, 8, 1}
• 继续分割左半部分：{6, 202} 和 {100, 301}
• 继续分割右半部分：{38, 8} 和 {1}
• 合并最小单元：{6, 202} → {6, 202}（已有序）
• 合并：{100, 301} → {100, 301}
• 合并：{38, 8} → {8, 38}
• 合并：{1} → {1}

第二次合并：

• 合并左半部分：{6, 202} 和 {100, 301} → {6, 100, 202, 301}
• 合并右半部分：{8, 38} 和 {1} → {1, 8, 38}

第三次合并：

• 合并最终结果：{6, 100, 202, 301} 和 {1, 8, 38} → {1, 6, 8, 38, 100, 202, 301}

整个过程中，比较次数为：3 + 4 + 4 = 11次。

2. Java实现

2.1 基础递归实现

public class MergeSort { /** * 归并排序的主方法 * @param arr 待排序的数组 */ public static void mergeSort(int[] arr) { if (arr == null || arr.length <= 1) { return; } // 创建临时数组，用于存储合并过程中的中间结果 int[] temp = new int[arr.length]; mergeSortHelper(arr, 0, arr.length - 1, temp); } /** * 递归辅助方法 * @param arr 待排序数组 * @param left 左边界索引 * @param right 右边界索引 * @param temp 临时数组 */ private static void mergeSortHelper(int[] arr, int left, int right, int[] temp) { // 递归终止条件：当子数组只有一个元素时 if (left < right) { int mid = left + (right - left) / 2; // 计算中间位置，避免溢出 // 递归排序左半部分 mergeSortHelper(arr, left, mid, temp); // 递归排序右半部分 mergeSortHelper(arr, mid + 1, right, temp); // 合并两个已排序的子数组 merge(arr, left, mid, right, temp); } } /** * 合并两个有序子数组 * @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 = left; // 临时数组的指针 // 比较两个子数组的元素，将较小的放入临时数组 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++]; } // 将临时数组中合并后的结果复制回原数组 for (int p = left; p <= right; p++) { arr[p] = temp[p]; } } /** * 测试方法 */ public static void main(String[] args) { int[] arr = {64, 34, 25, 12, 22, 11, 90}; System.out.println("排序前的数组："); printArray(arr); mergeSort(arr); System.out.println("排序后的数组："); printArray(arr); } public static void printArray(int[] arr) { for (int i : arr) { System.out.print(i + " "); } System.out.println(); } }

2.2 小数组使用插入排序

对于小规模数组，插入排序可能比归并排序更快。可以在递归到一定深度时切换到插入排序：

private static void mergeSortHelper(int[] arr, int left, int right, int[] temp) { // 当子数组长度小于等于10时，使用插入排序 if (right - left <= 10) { insertionSort(arr, left, right); return; } if (left < right) { int mid = left + (right - left) / 2; mergeSortHelper(arr, left, mid, temp); mergeSortHelper(arr, mid + 1, right, temp); merge(arr, left, mid, right, temp); } } /** * 插入排序（用于小规模数组） */ private static void insertionSort(int[] arr, int left, int right) { for (int i = left + 1; i <= right; i++) { int key = arr[i]; int j = i - 1; while (j >= left && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }

2.3 降序排序实现

如果需要实现降序排序，只需修改合并过程中的比较条件：

private static void mergeDescending(int[] arr, int left, int mid, int right, int[] temp) { int i = left; int j = mid + 1; int k = left; // 修改比较条件：将较小的改为较大的 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++]; } for (int p = left; p <= right; p++) { arr[p] = temp[p]; } }

3. 性能分析

3.1 时间复杂度

归并排序的时间复杂度在所有情况下都是O(n log n)：

• 最坏情况：O(n log n)
• 平均情况：O(n log n)
• 最好情况：O(n log n)

这种稳定的时间复杂度使得归并排序在处理大规模数据时表现优异。递归关系可以表示为：T(n) = 2T(n/2) + O(n)，通过主定理求解得到O(n log n)。

3.2 空间复杂度

归并排序需要额外的O(n)空间来存储临时数组。这是因为在合并过程中需要创建一个与原数组同样大小的辅助数组。这使得归并排序是非原地排序算法。

3.3 稳定性

归并排序是一种稳定的排序算法。这意味着如果两个元素的值相等，它们在排序后的相对顺序保持不变。这一特性在某些应用场景中非常重要，比如当需要按多个关键字排序时。

4. 归并排序的优缺点

4.1 优点

1. 时间复杂度稳定：无论输入数据如何，时间复杂度都是O(n log n)，性能可预测
2. 稳定性好：保持相等元素的相对顺序，适用于需要稳定排序的场景
3. 适合外部排序：当数据量太大无法全部加载到内存时，归并排序是理想选择
4. 适合链表排序：归并排序天然适合链表数据结构，不需要随机访问

4.2 缺点

1. 需要额外空间：需要O(n)的额外存储空间
2. 对小规模数据效率不高：当数据规模较小时，常数因子较大，可能不如插入排序等简单算法
3. 递归调用开销：递归实现需要额外的函数调用开销