详解归并排序

归并排序的基本概念

归并排序（Merge Sort）是一种经典的分治算法。它将一个大问题分解成若干个小问题，递归地解决这些小问题，然后再合并成一个解决的大问题。归并排序的核心在于合并过程，即将两个已排序的子数组合并成一个有序的数组。

归并排序的详细步骤

1. 分解阶段

归并排序首先将数组分成两半，直到每个子数组中只有一个元素。对于每个子数组，显然它已经是“有序”的（因为一个元素是有序的）。这一步是递归进行的，直到数组被分割到最小的子数组。

举个例子，假设我们有一个数组：

[38, 27, 43, 3, 9, 82, 10]

• 第一步：将数组从中间拆分成两部分：

  [38, 27, 43] 和 [3, 9, 82, 10]
  

• 第二步：继续拆分，直到每个子数组只有一个元素：

  [38] 和 [27, 43] 和 [3, 9] 和 [82, 10]
  

• 继续拆分：

  [38] 和 [27] 和 [43] 和 [3] 和 [9] 和 [82] 和 [10]
  

此时每个子数组只有一个元素，递归的分解阶段就完成了。

2. 合并阶段

合并的过程是归并排序的核心。合并阶段的目的是将每两个已排序的子数组合并成一个新的有序数组。合并时，需要依次比较两个子数组的元素，选择较小的元素放入最终的数组中，直到两个子数组的元素都被合并到结果数组中。

合并时的步骤如下：

1. 合并 [27] 和 [43]：

   • 比较 27 和 43，先将较小的 27 放入合并数组中，接着将 43 放入合并数组中。
   • 结果：[27, 43]

2. 合并 [3] 和 [9]：

   • 比较 3 和 9，先将 3 放入合并数组中，接着将 9 放入合并数组中。
   • 结果：[3, 9]

3. 合并 [82] 和 [10]：

   • 比较 82 和 10，先将较小的 10 放入合并数组中，接着将 82 放入合并数组中。
   • 结果：[10, 82]

经过这些合并后，我们得到如下数组：

[38] 和 [27, 43] 和 [3, 9] 和 [10, 82]

接下来，我们继续合并数组：

• 合并 [38] 和 [27, 43]：

  • 比较 38 和 27，将 27 放入合并数组中，接着比较 38 和 43，将 38 放入合并数组中，然后将 43 放入合并数组中。
  • 结果：[27, 38, 43]

• 合并 [3, 9] 和 [10, 82]：

  • 比较 3 和 10，将 3 放入合并数组中，接着比较 9 和 10，将 9 放入合并数组中，然后将 10 和 82 依次放入合并数组中。
  • 结果：[3, 9, 10, 82]

最后，我们合并这两个数组：

• 合并 [27, 38, 43] 和 [3, 9, 10, 82]：
  • 比较 27 和 3，将 3 放入合并数组中，接着比较 27 和 9，将 9 放入合并数组中，再比较 27 和 10，将 10 放入合并数组中，然后依次放入 27、38、43 和 82。
  • 结果：[3, 9, 10, 27, 38, 43, 82]

到此为止，整个数组已经排好序了。

3. 归并排序的递归流程

归并排序的递归过程非常重要，以下是归并排序的基本逻辑：

1. 分解：将数组不断拆分，直到每个子数组的长度为 1。
2. 合并：将两个已排序的子数组合并成一个有序数组。

递归终止条件是数组的大小为 1，此时已经是有序的，我们就不需要进一步分解了。

时间复杂度分析

归并排序的时间复杂度主要由两个因素决定：

1. 分解阶段：每一次递归将数组分成两半，因此分解的深度是 log₂ n 。
2. 合并阶段：每次合并操作需要线性时间 O(n) ，即每个元素都需要被访问和合并一次。

因此，总的时间复杂度是 O(nlog₂ n) ，其中 n 是待排序数组的长度。这个时间复杂度在最坏、最好和平均情况下都是相同的。

空间复杂度分析

归并排序需要额外的空间来存储临时数组（用于合并操作）。每次合并操作需要使用一个大小为 O(n) 的临时数组，因此归并排序的空间复杂度是 O(n) ，这是它的一个缺点。

算法步骤

2-路归并排序

2-路归并排序将 R[low…high] 中的记录归并排序后放入T[low…high] 中。当序列长度等于1时，递归结束，否则：

1. 将当前序列一分为二，求出分裂点 mid = ⌊(low + high) / 2⌋ ；
2. 对子序列 R[low…mid] 递归进行归并排序，结果放入 S[low…mid] 中；
3. 对子序列 R[mid + 1…high] 递归进行归并排序，结果放入 S[mid + 1…high] 中；
4. 调用算法Merge，将有序的两个子序列 S[low…mid] 和 S[mid + 1…high] 归并为一个有序的序列 T[low…high] 。

代码分析

#include <stdio.h>// 合并两个子数组
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;  // 计算左子数组的大小int n2 = right - mid;     // 计算右子数组的大小// 创建临时数组int leftArr[n1], rightArr[n2];// 将数据复制到临时数组for (int i = 0; i < n1; i++)leftArr[i] = arr[left + i];for (int j = 0; j < n2; j++)rightArr[j] = arr[mid + 1 + j];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++;}
}// 递归进行归并排序
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);}
}// 打印数组的函数
void printArray(int arr[], int size) {for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}int main() {int arr[] = {38, 27, 43, 3, 9, 82, 10};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组:\n");printArray(arr, n);mergeSort(arr, 0, n - 1);  // 调用归并排序printf("排序后的数组:\n");printArray(arr, n);return 0;
}

代码讲解

1. 合并两个子数组的函数 merge()

void merge(int arr[], int left, int mid, int right) {

• merge() 函数的目的是将两个已经排好序的子数组合并成一个有序的数组。
• arr[] 是待排序的数组，left 是左子数组的起始索引，mid 是中间索引，right 是右子数组的结束索引。

    int n1 = mid - left + 1;  // 计算左子数组的大小int n2 = right - mid;     // 计算右子数组的大小

• n1 和 n2 分别是左子数组和右子数组的元素个数。

    int leftArr[n1], rightArr[n2];

• leftArr[] 和 rightArr[] 是临时数组，用于存储左子数组和右子数组的元素。

    for (int i = 0; i < n1; i++)leftArr[i] = arr[left + i];for (int j = 0; j < n2; j++)rightArr[j] = arr[mid + 1 + j];

• 将 arr[] 数组中的数据分别复制到 leftArr[] 和 rightArr[] 中。

    int i = 0, j = 0, k = left;

• i 用于遍历 leftArr[]，j 用于遍历 rightArr[]，k 用于遍历原始数组 arr[]。

    while (i < n1 && j < n2) {if (leftArr[i] <= rightArr[j]) {arr[k] = leftArr[i];i++;} else {arr[k] = rightArr[j];j++;}k++;}

• 合并 leftArr[] 和 rightArr[] 的元素到 arr[] 中：
  • 比较 leftArr[i] 和 rightArr[j]，将较小的元素放入 arr[k] 中。
  • 如果左子数组的元素小或相等，就将左子数组的元素放入 arr[k]，否则将右子数组的元素放入。

    while (i < n1) {arr[k] = leftArr[i];i++;k++;}while (j < n2) {arr[k] = rightArr[j];j++;k++;}

• 如果左子数组或右子数组中还有剩余元素，继续将它们放入 arr[] 中。

2. 归并排序函数 mergeSort()

void mergeSort(int arr[], int left, int right) {

• mergeSort() 函数负责将数组不断分割并排序。它的作用是将数组拆分成越来越小的子数组，直到每个子数组只有一个元素，然后调用 merge() 合并已排序的子数组。

    if (left < right) {

• 递归终止条件：如果左边索引小于右边索引，说明子数组包含多于一个元素，继续分割和排序。

        int mid = left + (right - left) / 2;  // 计算中间点

• 计算中间点 mid，将数组分割成左右两部分。

        mergeSort(arr, left, mid);  // 递归排序左半部分mergeSort(arr, mid + 1, right);  // 递归排序右半部分

• 递归调用 mergeSort() 来分别排序左半部分和右半部分。

        merge(arr, left, mid, right);  // 合并已排序的部分

• 合并左右两部分，最终形成一个有序数组。

3. 打印数组的函数 printArray()

void printArray(int arr[], int size) {for (int i = 0; i < size; i++)printf("%d ", arr[i]);printf("\n");
}

• printArray() 用于打印数组中的元素。size 是数组的长度，arr[] 是待打印的数组。

4. 主函数 main()

int main() {int arr[] = {38, 27, 43, 3, 9, 82, 10};int n = sizeof(arr) / sizeof(arr[0]);

• 定义一个待排序的数组 arr[]，并通过 sizeof(arr) / sizeof(arr[0]) 计算数组的长度 n。

    printf("排序前的数组:\n");printArray(arr, n);

• 打印排序前的数组。

    mergeSort(arr, 0, n - 1);  // 调用归并排序

• 调用 mergeSort() 函数进行排序。

    printf("排序后的数组:\n");printArray(arr, n);

• 打印排序后的数组。

归并排序的稳定性

归并排序是一种稳定的排序算法。稳定性意味着如果两个元素的值相同，排序后它们在原数组中的相对顺序不会改变。

归并排序的优缺点

优点：

1. 时间复杂度稳定：归并排序的时间复杂度始终为 O(nlog₂ n) ，无论是最坏、平均还是最好情况都一样。
2. 稳定性：它是一种 稳定 的排序算法，对于相等的元素，能保持它们的相对顺序。
3. 适用于大数据集：归并排序在处理大数据集时非常有效，尤其是在外部排序中。

缺点：

1. 空间复杂度较高：归并排序需要 O(n) 的额外空间，这比其他一些排序算法如快速排序要高。
2. 不适用于小数据集：对于小规模数据，归并排序相比于插入排序、选择排序等简单的排序算法可能并不高效。
3. 合并操作需要额外时间：每次合并操作需要处理所有元素，因此合并阶段的时间开销相对较大。