下面我将为你提供一个通俗易懂的C++归并排序教程。
归并排序的概念
归并排序是一种采用分治法的经典排序算法。它的基本思想是将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个最终的有序数组。
归并排序的步骤可以总结为：
- 分解：将当前数组从中间分割成两个子数组
- 解决：递归地对两个子数组分别进行归并排序
- 合并：将排好序的两个子数组合并成一个有序数组
归并排序的时间复杂度是O(n log n)，这使它在处理大规模数据时非常高效。而且它是一种稳定的排序算法，即相等元素的相对顺序不会改变。
归并排序的实现代码
下面是C++实现的归并排序代码，包含详细注释：
#include <iostream>
#include <vector>
using namespace std;
// 合并两个已排序的子数组
void merge(vector<int>& arr, int left, int mid, int right) {
// 计算左右子数组的大小
int n1 = mid - left + 1;
int n2 = right - mid;
// 创建临时数组
vector<int> L(n1), R(n2);
// 复制数据到临时数组 L[] 和 R[]
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];
// 归并临时数组到 arr[left..right]
int i = 0; // 初始化左子数组的索引
int j = 0; // 初始化右子数组的索引
int k = left; // 初始归并子数组的索引
// 比较左右子数组的元素，将较小的元素放入原数组
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
// 复制 L[] 的剩余元素
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
// 复制 R[] 的剩余元素
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
// 归并排序主函数
void mergeSort(vector<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(const vector<int>& arr) {
for (int num : arr)
cout << num << " ";
cout << endl;
}
int main() {
vector<int> arr = {12, 11, 13, 5, 6, 7};
cout << "原数组: ";
printArray(arr);
// 执行归并排序
mergeSort(arr, 0, arr.size() - 1);
cout << "排序后的数组: ";
printArray(arr);
return 0;
}
代码解释
-
merge函数：该函数用于合并两个已排序的子数组。它首先创建两个临时数组来存储左右子数组的元素，然后比较这两个临时数组的元素，按顺序合并回原数组。
-
mergeSort函数：这是归并排序的主函数，它采用递归的方式将数组分解为更小的子数组，直到每个子数组只有一个元素（自然有序），然后再逐层合并这些子数组。
-
printArray函数：辅助函数，用于打印数组元素。
-
main函数：程序入口，创建测试数组，调用归并排序函数，并输出排序前后的数组。
归并排序的工作过程示例
假设我们有一个数组 [12, 11, 13, 5, 6, 7]，归并排序的工作过程如下：
-
分解阶段：
- 初始数组：[12, 11, 13, 5, 6, 7]
- 分成两半：[12, 11, 13] 和 [5, 6, 7]
- 进一步分解：[12], [11, 13] 和 [5, 6], [7]
- 再分解：[12], [11], [13] 和 [5], [6], [7]
-
合并阶段：
- 合并 [11] 和 [13] 为 [11, 13]
- 合并 [12] 和 [11, 13] 为 [11, 12, 13]
- 合并 [5] 和 [6] 为 [5, 6]
- 合并 [5, 6] 和 [7] 为 [5, 6, 7]
- 最后合并 [11, 12, 13] 和 [5, 6, 7] 为 [5, 6, 7, 11, 12, 13]
归并排序的优势在于其稳定的时间复杂度和稳定性，但它需要额外的空间来存储临时数组，这是它的一个缺点。
1 条评论
-
admin SU @ 2025-6-9 23:05:26
C++ 归并排序教程
一、归并排序简介
1.1 基本概念
归并排序（Merge Sort）是一种基于分治思想的高效排序算法，由计算机科学家约翰·冯·诺依曼于1945年提出。它的核心思想是：
"分而治之"（Divide and Conquer）
具体来说：
- 将一个数组分成两个子数组
- 对每个子数组递归地进行排序
- 然后将已排序的子数组合并成一个完整的有序数组
1.2 时间复杂度分析
情况 时间复杂度 最好情况 O(n log n) 最坏情况 平均情况 这是目前最稳定的O(n log n)时间复杂度的排序算法之一。
1.3 特点
- 是一种稳定排序算法
- 需要额外的存储空间（不是原地排序）
- 特别适合链表结构的数据排序
- 适用于大规模数据排序
二、归并排序原理详解
2.1 核心步骤
- 分割（Divide）：将数组分成两半
- 排序子数组（Conquer）：递归地对子数组排序
- 合并（Combine）：将两个有序子数组合并成一个有序数组
2.2 合并过程详解
合并是归并排序的关键操作，需要：
- 创建一个临时数组
- 比较两个子数组的元素
- 按顺序放入临时数组
- 将临时数组复制回原数组
三、C++ 实现代码及详细注释
#include <iostream> using namespace std; // 打印数组函数 void printArray(int arr[], int size) { for (int i = 0; i < size; i++) { cout << arr[i] << " "; } cout << endl; } /** * 合并两个子数组的函数 * arr[] 是原始数组 * l 是左边界 * m 是中间点 * r 是右边界 */ void merge(int arr[], int l, int m, int r) { // 子数组1的大小 = m - l + 1 int n1 = m - l + 1; // 子数组2的大小 = r - m int n2 = r - m; // 创建临时数组 int L[n1], R[n2]; // 复制数据到临时数组L[]和R[] for (int i = 0; i < n1; i++) L[i] = arr[l + i]; for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j]; // 初始化索引指针 int i = 0; // 遍历L[] int j = 0; // 遍历R[] int k = l; // 遍历主数组arr[] // 合并临时数组到arr[] while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } // 检查L[]是否有剩余元素 while (i < n1) { arr[k] = L[i]; i++; k++; } // 检查R[]是否有剩余元素 while (j < n2) { arr[k] = R[j]; j++; k++; } } /** * 归并排序函数 * arr[] 是待排序数组 * l 是起始索引 * r 是结束索引 */ void mergeSort(int arr[], int l, int r) { // 当只有一个元素时停止分割(基本条件) if (l >= r) { return; } // 找到中间点 int m = l + (r - l) / 2; // 递归排序左半部分 cout << "排序左半部分 [" << l << "," << m << "]: "; printArray(arr+l, m-l+1); mergeSort(arr, l, m); // 递归排序右半部分 cout << "排序右半部分 [" << m+1 << "," << r << "]: "; printArray(arr+m+1, r-(m+1)+1); mergeSort(arr, m + 1, r); // 合并两个有序数组 cout << "合并前左半部分 [" << l << "," << m << "]: "; printArray(arr+l, m-l+1); cout << "合并前右半部分 [" << m+1 << "," << r << "]: "; printArray(arr+m+1, r-(m+1)+1); merge(arr, l, m, r); cout << "合并后 [" << l << "," << r << "]: "; printArray(arr+l, r-l+1); } // 主函数测试归并排序 int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int n = sizeof(arr)/sizeof(arr[0]); cout << "原始数组: "; printArray(arr, n); mergeSort(arr, 0, n-1); cout << "排序后的数组: "; printArray(arr, n); return 0; }四、代码执行流程解析
我们以数组
{12, 11, 13, 5, 6, 7}为例来追踪执行流程：-
初始调用
mergeSort(arr, 0, 5)- 中间点 m = 2
- 进入左半部分排序
mergeSort(arr, 0, 2)
-
左半部分排序:
- 中间点 m = 1
- 进入左半部分排序
mergeSort(arr, 0, 1)
-
左半部分排序:
- 中间点 m = 0
- 进入左半部分排序
mergeSort(arr, 0, 0)(单个元素，直接返回) - 进入右半部分排序
mergeSort(arr, 1, 1)(单个元素，直接返回) - 合并 [0,0] 和 [1,1] -> 得到排序好的 [0,1]
-
返回上一层继续排序右半部分 [2,2] (单个元素，直接返回)
- 合并 [0,1] 和 [2,2] -> 得到排序好的 [0,2]
-
返回初始调用继续排序右半部分 [3,5]
- 类似上述过程，最终得到排序好的 [3,5]
-
最终合并 [0,2] 和 [3,5] 得到完整排序数组
五、示例输出
运行程序会输出：
原始数组: 12 11 13 5 6 7 排序左半部分 [0,2]: 12 11 13 排序左半部分 [0,1]: 12 11 排序左半部分 [0,0]: 12 排序右半部分 [1,1]: 11 合并前左半部分 [0,0]: 12 合并前右半部分 [1,1]: 11 合并后 [0,1]: 11 12 排序右半部分 [2,2]: 13 合并前左半部分 [0,1]: 11 12 合并前右半部分 [2,2]: 13 合并后 [0,2]: 11 12 13 排序右半部分 [3,5]: 5 6 7 排序左半部分 [3,4]: 5 6 排序左半部分 [3,3]: 5 排序右半部分 [4,4]: 6 合并前左半部分 [3,3]: 5 合并前右半部分 [4,4]: 6 合并后 [3,4]: 5 6 排序右半部分 [5,5]: 7 合并前左半部分 [3,4]: 5 6 合并前右半部分 [5,5]: 7 合并后 [3,5]: 5 6 7 合并前左半部分 [0,2]: 11 12 13 合并前右半部分 [3,5]: 5 6 7 合并后 [0,5]: 5 6 7 11 12 13 排序后的数组: 5 6 7 11 12 13六、优化建议
虽然基础实现已经很高效，但可以考虑以下优化：
-
小数组使用插入排序：当子数组长度小于某个阈值（如10）时，使用插入排序更高效
-
避免不必要的合并：在合并前检查
arr[m] <= arr[m+1]，如果已经有序可以直接返回 -
使用迭代实现：非递归版本可以减少函数调用开销
-
优化空间使用：提前分配一次临时数组，避免重复创建销毁
七、总结
归并排序是一种经典的排序算法，其分治思想对解决其他问题有重要启示。它保证了O(n log n)的时间复杂度，在处理大规模数据时表现优异。虽然需要O(n)的额外空间，但在现代计算机内存充足的环境下，这通常不是问题。
理解归并排序不仅有助于掌握排序算法，更能帮助我们理解和应用分治策略解决其他复杂问题。
- 1