排序算法‌ 之‌ 归并排序（Merge Sort）

排序算法‌ 之‌ 归并排序（Merge Sort）

1. 基础概念

1.1 定义

归并排序是一种基于分治法的排序算法。其核心思想是将数组递归地分为两部分，分别排序后合并成一个有序数组。分治步骤分为两个阶段：

• 分解（Divide）：将数组分成两个子数组。
• 合并（Conquer）：合并两个有序数组，得到排序后的数组。

1.2 特点

• 时间复杂度为O(n log n)，效率稳定。
• 空间复杂度为O(n)，需要额外的存储空间。
• 稳定排序，保持相等元素的原始顺序。
• 适用于链表等结构，因为合并过程不依赖随机访问。

1.3 使用场景

• 大规模数据排序。
• 需要稳定排序的场景，例如涉及多字段排序的场景。
• 对链表等不支持随机访问的数据结构排序。

2. 实现与操作

2.1 核心操作实现

以下使用C语言实现归并排序的核心功能，包括分解数组、合并有序数组。

#include <stdio.h> #include <stdlib.h> // 合并两个子数组 void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; // 创建临时数组 int *L = (int *)malloc(n1 * sizeof(int)); int *R = (int *)malloc(n2 * sizeof(int)); // 拷贝数据到临时数组 for (int i = 0; i < n1; i++) L[i] = arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; int i = 0, j = 0, k = left; // 合并两个子数组 while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // 拷贝剩余元素 while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } // 释放临时数组 free(L); free(R); } // 递归实现归并排序 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[] = {12, 11, 13, 5, 6, 7}; int arrSize = sizeof(arr) / sizeof(arr[0]); printf("原数组: "); printArray(arr, arrSize); mergeSort(arr, 0, arrSize - 1); printf("排序后数组: "); printArray(arr, arrSize); return 0; } </stdlib.h></stdio.h>

2.2 代码详解

• merge：合并两个有序子数组，采用双指针比较元素并放入原数组。
• mergeSort：递归分割数组，并调用merge进行排序。
• main：初始化测试数组，调用mergeSort排序，最后打印结果。

3. 时间与空间复杂度分析

3.1 时间复杂度

• 分解：每次分解需要O(log n)次递归。
• 合并：每次合并需要O(n)时间。
• 总复杂度：O(n log n)。

3.2 空间复杂度

归并排序需要额外的临时数组存储数据，空间复杂度为O(n)。对于链表实现，空间复杂度可以优化为O(1)。

4. 优缺点与局限性

4.1 优点

• 性能稳定，时间复杂度为O(n log n)。
• 适合大规模数据的排序。
• 稳定排序，适合对多字段排序的场景。

4.2 缺点与局限性

• 需要额外的存储空间，空间复杂度为O(n)。
• 不适合对小规模数据排序（如n较小时选择插入排序更高效）。

5. 常见应用场景

5.1 实际应用

归并排序常用于外部排序（例如大文件排序）和链表排序。

6. 代码编译与运行

6.1 编译命令

使用以下命令编译代码：

gcc merge_sort.c -o merge_sort -Wall

6.2 测试用例

测试用例：

输入：12, 11, 13, 5, 6, 7  
输出：5, 6, 7, 11, 12, 13