c++归并排序代码（c 归并排序）

# 简介在计算机科学中，排序算法是基础且重要的内容之一。归并排序是一种高效的分而治之的排序算法，其时间复杂度为O(n log n)，在处理大规模数据时表现出色。本文将详细介绍C++实现归并排序的方法，并通过具体代码示例帮助读者理解其工作原理和应用场景。---## 一、归并排序的基本原理### 1. 分治法思想 归并排序的核心思想是“分而治之”： -

分解

：将数组不断划分为更小的部分。 -

解决

：对每个部分递归地应用归并排序。 -

合并

：将排序好的子数组合并成一个完整的有序数组。### 2. 工作流程 1. 将数组分成左右两半。 2. 对左右两半分别进行归并排序。 3. 将两个已排序的子数组合并为一个有序数组。---## 二、C++实现归并排序代码以下是基于C++的归并排序完整代码：```cpp #include using namespace std;// 合并两个有序数组 void merge(int arr[], int left, int mid, int right) {// 计算左右两个子数组的大小int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组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, 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++;} }// 归并排序主函数 void mergeSort(int arr[], int left, int right) {if (left >= right)return; // 数组只有一个元素或为空时直接返回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++)cout << arr[i] << " ";cout << endl; }// 测试程序 int main() {int arr[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr) / sizeof(arr[0]);cout << "给定数组: ";printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);cout << "排序后的数组: ";printArray(arr, arr_size);return 0; } ```---## 三、代码详解### 1. `merge` 函数 该函数用于合并两个已排序的子数组。它首先创建两个临时数组存储左右子数组的内容，然后比较这两个数组中的元素，逐步将较小的元素放入原数组中。### 2. `mergeSort` 函数 这是归并排序的核心递归函数： - 如果当前数组只有一个元素，则无需排序。 - 否则，找到中间点，递归调用`mergeSort`对左右两部分排序。 - 最后调用`merge`函数合并两个有序子数组。### 3. `printArray` 函数 此函数用于打印数组内容，便于观察排序结果。---## 四、运行结果假设输入数组为 `{12, 11, 13, 5, 6, 7}`，程序输出如下：``` 给定数组: 12 11 13 5 6 7 排序后的数组: 5 6 7 11 12 13 ```---## 五、归并排序的特点与适用场景### 1. 时间复杂度 - 最坏情况时间复杂度：O(n log n) - 平均时间复杂度：O(n log n)### 2. 空间复杂度 由于需要额外的空间存储临时数组，空间复杂度为O(n)。### 3. 适用场景 归并排序适用于以下场景： - 数据量较大且对稳定性有要求的情况。 - 需要在线处理或外部存储的场景（如磁盘排序）。---## 六、总结归并排序是一种高效且稳定的排序算法，尤其适合处理大规模数据。本文通过C++代码详细展示了归并排序的实现过程，并分析了其优缺点及适用场景。希望读者能够通过本文掌握归并排序的基本原理和实践方法，为后续的学习和开发打下坚实的基础。

简介在计算机科学中，排序算法是基础且重要的内容之一。归并排序是一种高效的分而治之的排序算法，其时间复杂度为O(n log n)，在处理大规模数据时表现出色。本文将详细介绍C++实现归并排序的方法，并通过具体代码示例帮助读者理解其工作原理和应用场景。---

一、归并排序的基本原理

1. 分治法思想 归并排序的核心思想是“分而治之”： - **分解**：将数组不断划分为更小的部分。 - **解决**：对每个部分递归地应用归并排序。 - **合并**：将排序好的子数组合并成一个完整的有序数组。

2. 工作流程 1. 将数组分成左右两半。 2. 对左右两半分别进行归并排序。 3. 将两个已排序的子数组合并为一个有序数组。---

二、C++实现归并排序代码以下是基于C++的归并排序完整代码：```cpp

include using namespace std;// 合并两个有序数组 void merge(int arr[], int left, int mid, int right) {// 计算左右两个子数组的大小int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组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, 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++;} }// 归并排序主函数 void mergeSort(int arr[], int left, int right) {if (left >= right)return; // 数组只有一个元素或为空时直接返回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++)cout << arr[i] << " ";cout << endl; }// 测试程序 int main() {int arr[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr) / sizeof(arr[0]);cout << "给定数组: ";printArray(arr, arr_size);mergeSort(arr, 0, arr_size - 1);cout << "排序后的数组: ";printArray(arr, arr_size);return 0; } ```---

三、代码详解

1. `merge` 函数 该函数用于合并两个已排序的子数组。它首先创建两个临时数组存储左右子数组的内容，然后比较这两个数组中的元素，逐步将较小的元素放入原数组中。

2. `mergeSort` 函数 这是归并排序的核心递归函数： - 如果当前数组只有一个元素，则无需排序。 - 否则，找到中间点，递归调用`mergeSort`对左右两部分排序。 - 最后调用`merge`函数合并两个有序子数组。

3. `printArray` 函数 此函数用于打印数组内容，便于观察排序结果。---

四、运行结果假设输入数组为 `{12, 11, 13, 5, 6, 7}`，程序输出如下：``` 给定数组: 12 11 13 5 6 7 排序后的数组: 5 6 7 11 12 13 ```---

五、归并排序的特点与适用场景

1. 时间复杂度 - 最坏情况时间复杂度：O(n log n) - 平均时间复杂度：O(n log n)

2. 空间复杂度 由于需要额外的空间存储临时数组，空间复杂度为O(n)。

3. 适用场景 归并排序适用于以下场景： - 数据量较大且对稳定性有要求的情况。 - 需要在线处理或外部存储的场景（如磁盘排序）。---

六、总结归并排序是一种高效且稳定的排序算法，尤其适合处理大规模数据。本文通过C++代码详细展示了归并排序的实现过程，并分析了其优缺点及适用场景。希望读者能够通过本文掌握归并排序的基本原理和实践方法，为后续的学习和开发打下坚实的基础。