超详细解析C++实现归并排序算法
什么是归并排序
归并排序是一种比较高效稳定的排序算法,其基本思想是将待排序序列分成若干个子序列,分别进行排序,再将已排序的子序列合并,依次进行,直到合并成一个完整的有序序列。
实现步骤
归并排序的实现步骤可以总结为以下几步:
步骤1:将序列分成两个子序列
选择一个中间位置,将待排序序列分成两个子序列。
步骤2:递归地对子序列进行排序
对左子序列进行归并排序,对右子序列进行归并排序,即递归调用归并排序函数。
步骤3:合并两个有序子序列
将排好序的左子序列和右子序列合并成一个完整的有序序列。
C++实现代码示例
以下是C++语言的归并排序实现代码示例:
#include <iostream>
using namespace std;
// merge两个已经排好序的子序列,合并成一个有序序列
void merge(int arr[], int l, int m, int r)
{
// 子序列1的长度为 m - l + 1
// 子序列2的长度为 r - m
int n1 = m - l + 1;
int n2 = r - m;
// 创建临时数组,用来存储合并后的有序序列
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int i = 0; i < n2; i++)
R[i] = arr[m + 1 + i];
// 归并排序算法的核心步骤,将两个子序列合并
int i = 0, j = 0, k = l;
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 l, int r)
{
if (l < r)
{
// 计算中间位置
int m = l + (r - l) / 2;
// 递归地排序左子序列和右子序列
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
// 合并两个排好序的子序列
merge(arr, l, m, r);
}
}
// main函数,程序入口
int main()
{
int arr[] = {5, 2, 8, 6, 1, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
mergeSort(arr, 0, n - 1);
cout << "\nSorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
示例说明
以下是对输入数组{5, 2, 8, 6, 1, 9}的排序过程进行的示例说明:
- 初始时,该数组并未有序,需要进行排序
- 调用mergeSort(arr, 0, n - 1)函数进行归并排序,其中n为数组长度
- 首先对整个数组进行分割,得到两个子序列{5, 2, 8}和{6, 1, 9}
- 对左子序列{5, 2, 8}递归处理,得到子序列{2, 5, 8}
- 对右子序列{6, 1, 9}递归处理,得到子序列{1, 6, 9}
- 将已排好序的子序列{2, 5, 8}和{1, 6, 9}合并成一个完整的有序序列{1, 2, 5, 6, 8, 9}
- 输出排序后的数组{1, 2, 5, 6, 8, 9}
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:超详细解析C++实现归并排序算法 - Python技术站