CSP-J 算法基础 归并排序
文章目录
- 前言
- 归并排序
- 归并排序（Merge Sort）的原理
- 例子：归并排序的运行过程
- 1. 分解阶段
- 2. 解决（递归排序）阶段
- 3. 合并阶段
- 总结
- 编程代码实现归并算法
- 总结
前言
归并排序（Merge Sort）是一种高效的排序算法，由John von Neumann于1945年提出。归并排序利用分治法（Divide and Conquer）将一个大规模问题分解成多个小规模问题，从而高效地完成排序任务。其基本思想是将待排序的数组分成两个大致相等的子数组，递归地对每个子数组进行排序，然后将两个已排序的子数组合并成一个最终的已排序数组。归并排序在实际应用中表现出色，特别是在处理大规模数据集时，因为它具有稳定的时间复杂度和简单的实现方式。
归并排序
归并排序（Merge Sort）的原理
归并排序是一种基于分治法（Divide and Conquer）的排序算法，其基本思想是将一个大的数组分解成多个小的子数组，分别对这些小的子数组进行排序，然后将这些已排序的子数组合并成一个大的已排序数组。具体的步骤如下：
-
分解（Divide）：
- 将待排序的数组分成两个大致相等的子数组。
-
解决（Conquer）：
- 递归地对这两个子数组进行排序。此步骤会进一步分解子数组，直到每个子数组只有一个元素或为空（此时子数组自然是有序的）。
-
合并（Merge）：
- 将已排序的子数组合并成一个大的已排序数组。合并过程会将两个已排序的子数组合并成一个新的已排序数组。
例子：归并排序的运行过程
假设我们要对数组 [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]
-
分成：[38] 和 [27, 43]
-
对 [27, 43] 进行分解：
- 分成：[27] 和 [43]
-
-
右半部分：[3, 9, 82, 10]
-
分成：[3, 9] 和 [82, 10]
-
对 [3, 9] 进行分解：
- 分成：[3] 和 [9]
-
对 [82, 10] 进行分解：
- 分成：[82] 和 [10]
-
2. 解决（递归排序）阶段
对每个子数组进行排序（实际上由于它们已经分解到最小单位，每个单独的元素都已排序）：
-
左半部分：
- 合并 [27] 和 [43] 得到 [27, 43]
- 合并 [38] 和 [27, 43] 得到 [27, 38, 43]
-
右半部分：
- 合并 [3] 和 [9] 得到 [3, 9]
- 合并 [82] 和 [10] 得到 [10, 82]
- 合并 [3, 9] 和 [10, 82] 得到 [3, 9, 10, 82]
3. 合并阶段
将已排序的左半部分和右半部分合并成一个大数组：
- 左半部分：[27, 38, 43]
- 右半部分：[3, 9, 10, 82]
合并过程：
- 比较并合并：[3]（最小）与 [27]（左半部分的第一个元素），得到 [3]
- 比较并合并：[9]（下一个）与 [27]，得到 [3, 9]
- 比较并合并：[10]（下一个）与 [27]，得到 [3, 9, 10]
- 继续合并剩下的元素：[27, 38, 43]，最终得到 [3, 9, 10, 27, 38, 43, 82]
最终已排序的数组为：[3, 9, 10, 27, 38, 43, 82]
总结
归并排序通过分解原始数组、递归地排序每个子数组，并在最后阶段将这些子数组合并，最终得到一个已排序的数组。它的时间复杂度为 O(n log n)，空间复杂度为 O(n)，适用于大多数排序任务，尤其是在处理大规模数据时表现出色。
编程代码实现归并算法
#include <stdio.h>
// 函数声明
void mergeSort(int arr[], int left, int right);
void merge(int arr[], int left, int mid, int right);
void printArray(int arr[], int size);
int main() {
int arr[] = { 38, 27, 43, 3, 9, 82, 10 };
int size = sizeof(arr) / sizeof(arr[0]);
printf("原始数组：");
printArray(arr, size);
mergeSort(arr, 0, size - 1);
printf("排序后的数组：");
printArray(arr, size);
return 0;
}
// 归并排序函数
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
printf("分解阶段：处理区间 [%d, %d]，中点：%d\n", left, right, mid);
// 递归排序左半部分
mergeSort(arr, left, mid);
// 递归排序右半部分
mergeSort(arr, mid + 1, right);
// 合并两个已排序的子数组
merge(arr, left, mid, right);
printf("合并后数组状态：");
printArray(arr + left, right - left + 1);
}
}
// 合并函数
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1; // 左半部分的长度
int n2 = right - mid; // 右半部分的长度
// 创建临时数组
int L[n1], R[n2];
// 复制数据到临时数组
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];
// 打印临时数组
printf("左临时数组：");
printArray(L, n1);
printf("右临时数组：");
printArray(R, n2);
// 合并临时数组到原始数组
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
}
else {
arr[k++] = R[j++];
}
}
// 复制剩余元素（如果有的话）
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
// 打印合并后的数组
printf("合并后数组状态：");
printArray(arr + left, right - left + 1);
}
// 打印数组函数
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
总结
归并排序的时间复杂度为
𝑂
(
𝑛
log
𝑛
)
O(nlogn)，无论在最佳、最坏还是平均情况下，这一复杂度都是一致的，这使得它在各种输入情况下都能表现出稳定的性能。归并排序的空间复杂度为
𝑂
(
𝑛
)
O(n)，主要由辅助数组和递归栈空间决定。尽管归并排序的空间复杂度相对较高，但它的稳定性和高效性使其在许多应用场景中成为排序任务的首选方法。通过将问题分解和合并两个已排序的子数组，归并排序不仅实现了高效的排序，还为各种排序算法提供了一个有力的参考模型。