排序算法之归并排序详细解读（附带Java代码解读）

本文主要是介绍排序算法之归并排序详细解读（附带Java代码解读），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

归并排序（Merge Sort）是一种稳定的排序算法，采用分治法（Divide and Conquer）的思想。它将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将两个已排序的子数组合并成一个有序的数组。归并排序是一种高效的排序算法，尤其适合处理大规模数据。

算法思想

分解：将待排序的数组分成两个子数组，直到每个子数组只有一个元素（单个元素自然有序）。
解决：递归地对每个子数组进行排序。
合并：将两个已排序的子数组合并成一个有序的数组。

过程示例

假设有一个待排序的数组：[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, 3]
      - [38] 和 [27]
      - [43] 和 [3]
    - [9] 和 [82, 10]
      - [82] 和 [10]

步骤 2: 合并

将每对已排序的子数组合并成一个有序数组：

合并 [38] 和 [27]：[27, 38]
合并 [43] 和 [3]：[3, 43]
合并 [82] 和 [10]：[10, 82]
合并 [27, 38] 和 [3, 43]：[3, 27, 38, 43]
合并 [9] 和 [10, 82]：[9, 10, 82]
最终合并 [3, 27, 38, 43] 和 [9, 10, 82]：[3, 9, 10, 27, 38, 43, 82]

算法复杂度

时间复杂度:
- 最坏情况: O(n log n)
- 平均情况: O(n log n)
- 最佳情况: O(n log n)（即使数组已经排序，归并排序也会执行相同的操作）
空间复杂度: O(n) 归并排序需要额外的存储空间来保存合并结果。

优点

稳定性：归并排序是稳定的，即相等的元素在排序后相对位置不变。
时间复杂度优良：无论数据初始状态如何，归并排序的时间复杂度始终为 O(n log n)。
适用于大规模数据：适合大规模数据的排序，尤其是当数据不能完全加载到内存中时。

缺点

空间复杂度高：需要额外的 O(n) 空间来存储临时数组。
实现较复杂：相比其他简单排序算法（如插入排序），归并排序的实现较复杂。

Java代码解读

public class MergeSort {// 主方法：执行归并排序public static void mergeSort(int[] arr) {if (arr.length < 2) {return; // 数组长度小于2，直接返回}int mid = arr.length / 2;int[] left = new int[mid];int[] right = new int[arr.length - mid];// 分割数组System.arraycopy(arr, 0, left, 0, mid);System.arraycopy(arr, mid, right, 0, arr.length - mid);// 递归排序mergeSort(left);mergeSort(right);// 合并已排序的子数组merge(arr, left, right);}// 合并两个已排序的子数组private static void merge(int[] arr, int[] left, int[] right) {int i = 0, j = 0, k = 0;// 合并过程while (i < left.length && j < right.length) {if (left[i] <= right[j]) {arr[k++] = left[i++];} else {arr[k++] = right[j++];}}// 复制剩余元素while (i < left.length) {arr[k++] = left[i++];}while (j < right.length) {arr[k++] = right[j++];}}public static void main(String[] args) {int[] arr = {38, 27, 43, 3, 9, 82, 10};System.out.println("排序前的数组:");for (int num : arr) {System.out.print(num + " ");}System.out.println();mergeSort(arr);System.out.println("排序后的数组:");for (int num : arr) {System.out.print(num + " ");}}
}

代码说明

mergeSort方法:
- 递归地将数组分成两部分，分别对其进行排序。
- 使用 System.arraycopy 方法将数组分割成两个子数组 left 和 right。
- 递归调用 mergeSort 对这两个子数组进行排序。
- 调用 merge 方法将排序后的子数组合并。
merge方法:
- 合并两个已排序的子数组 left 和 right。
- 使用三个指针 i、j 和 k 分别跟踪 left、right 和 arr 数组的位置。
- 将较小的元素放入 arr 中，并移动对应的指针。
- 处理 left 和 right 中剩余的元素。
main方法:
- 创建一个待排序的数组 arr。
- 调用 mergeSort 方法对数组进行排序。
- 输出排序前和排序后的数组。