12.归并排序：分治思想的稳定排序算法

一、什么是归并排序？

归并排序（Merge Sort）是一种基于分治思想的稳定排序算法，由 John von Neumann 在 1945 年提出。它的核心思想是先将数组递归拆分成单个元素，再将有序的子数组两两合并，最终得到完全有序的数组。

简单来说，归并排序就像 “拆积木再拼起来”：

• 把复杂的大数组拆成一个个小数组，直到每个子数组只有一个元素（天然有序）；
• 再把这些有序的子数组两两合并，逐步拼成一个完整的有序数组。

二、归并排序的核心步骤

归并排序的核心步骤可以分为以下两步：

三、归并排序的代码实现

1. Python 版本（直观易懂）

def merge_sort(arr, left, right):
# 递归终止条件：子数组只有一个元素
if left >= right:
return
# 1. 拆分：从中间分成两个子数组
mid = (left + right) // 2
merge_sort(arr, left, mid)
merge_sort(arr, mid + 1, right)
# 2. 合并：将两个有序子数组合并
merge(arr, left, mid, right)

def merge(arr, left, mid, right):
# 定义左右子数组
L = arr[left:mid+1]
R = arr[mid+1:right+1]
# 定义三个指针：i遍历左子数组，j遍历右子数组，k遍历原数组
i = j = 0
k = left
# 比较左右子数组的元素，将较小的元素放入原数组
while i < len(L) and j < len(R):
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1
# 处理左子数组剩余的元素
while i < len(L):
arr[k] = L[i]
i += 1
k += 1
# 处理右子数组剩余的元素
while j < len(R):
arr[k] = R[j]
j += 1
k += 1

# 测试
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
merge_sort(arr, 0, n – 1)
print("排序后的数组：", arr) # 输出：[5, 6, 7, 11, 12, 13]

2. 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];
}
// 定义三个指针：i遍历左子数组，j遍历右子数组，k遍历原数组
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 merge_sort(int arr[], int left, int right) {
if (left < right) {
// 1. 拆分：从中间分成两个子数组
int mid = left + (right – left) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
// 2. 合并：将两个有序子数组合并
merge(arr, left, mid, right);
}
}

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

int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);

printf("排序前：");
printArray(arr, n);

merge_sort(arr, 0, n – 1);

printf("排序后：");
printArray(arr, n); // 输出：5 6 7 11 12 13

return 0;
}

四、归并排序的时间复杂度和空间复杂度

• 时间复杂度：O (n log n)，因为每次拆分将数组分成两部分，递归深度为 log n，每层合并的时间复杂度为 O (n)；
• 空间复杂度：O (n)，需要额外的临时数组存储子数组；
• 稳定性：稳定，因为合并时会优先选择左子数组的元素，保持相同元素的相对位置。

五、归并排序的优化

为了提高归并排序的效率，可以进行以下优化：

六、归并排序的实际应用场景

归并排序是一种稳定、高效的排序算法，常见场景包括：

七、总结

归并排序是一种基于分治思想的稳定排序算法，它的核心思想是先将数组递归拆分成单个元素，再将有序的子数组两两合并，最终得到完全有序的数组。

归并排序的时间复杂度为 O (n log n)，空间复杂度为 O (n)，是一种稳定的排序算法，适合大规模数据排序和稳定性要求高的场景。

希望这篇文章能帮助你理解归并排序的原理和实现！