1. 介绍
归并排序（Merge Sort）是一种采用分治法（Divide and Conquer）策略的排序算法。该算法首先将已有序的子序列合并，得到完全有序的序列。在归并排序中，合并操作是将两个有序表合并成一个有序表的过程。
归并排序的原理是将数组不断分成两半，直到每个子数组只有一个元素，然后将这些子数组合并成一个有序的数组。合并操作需要两个子数组都是有序的，因此归并排序需要先对数组进行分解，然后再进行合并。
以下是归并排序的实现步骤：
- 将待排序的数组不断分成两半，直到每个子数组只有一个元素。这一步被称为分解。
- 对每个子数进行排序，可以使用任何有效的排序算法。这一步被称为求解。
- 将所有已排序的子数组合并成一个有序的数组。这一步被称为合并。
归并排序的时间复杂度是 O(n log n)，其中 n 是数组的大小。这是因为它需要将数组分解成两半，然后再合并成一个有序的数组。归并排序的空间复杂度是 O(n)，因为在合并过程中需要额外的空间来存储临时变量。
2. 代码实现
#include <iostream>
using namespace std;
// 归并操作，将有序数组a和b合并成一个有序数组c
void merge(int a[], int b[], int c[], int m, int n) {
int i = 0, j = 0, k = 0; // i、j、k分别指向数组a、b、c的起始位置
while (i < m && j < n) { // 比较a和b中的元素，将较小的元素放入c中
if (a[i] <= b[j]) {
c[k++] = a[i++];
} else {
c[k++] = b[j++];
}
}
while (i < m) { // 将数组a中剩余的元素放入c中
c[k++] = a[i++];
}
while (j < n) { // 将数组b中剩余的元素放入c中
c[k++] = b[j++];
}
}
// 归并排序函数，将数组a中的元素进行排序
void mergeSort(int a[], int n) {
if (n <= 1) { // 如果数组只有一个元素或为空，直接返回
return;
}
int mid = n / 2; // 计算数组的中间位置
int left[mid]; // 存储数组a左边部分的元素
int right[n - mid]; // 存储数组a右边部分的元素
for (int i = 0; i < mid; i++) { // 将数组a左边部分的元素放入left数组中
left[i] = a[i];
}
for (int i = mid; i < n; i++) { // 将数组a右边部分的元素放入right数组中
right[i - mid] = a[i];
}
mergeSort(left, mid); // 对left数组进行归并排序
mergeSort(right, n - mid); // 对right数组进行归并排序
merge(left, right, a, mid, n - mid); // 将left和right两个有序数组合并成一个有序数组a
}
// 测试归并排序函数
int main() {
int a[] = {38, 27, 43, 36, 16, 25, 6, 22}; // 待排序的数组
int n = sizeof(a) / sizeof(a[0]); // 数组的大小
mergeSort(a, n); // 对数组进行归并排序
for (int i = 0; i < n; i++) { // 输出排序后的数组元素
cout << a[i] << " ";
}
cout << endl;
return 0;
}
