pta归并排序C++
时间: 2025-01-03 20:37:10 浏览: 47
### 关于PTA平台C++实现归并排序
#### 归并排序算法简介
归并排序是一种分治算法,其核心思想是将数组分成较小的子数组,分别对这些子数组进行排序,再将有序的子数组合并成一个完整的有序数组。该方法的时间复杂度为O(n log n),其中n表示待排序元素的数量。
#### 示例代码及解析
下面是一个使用C++在PTA平台上实现归并排序的例子:
```cpp
#include <iostream>
using namespace std;
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
/* 创建临时数组 */
int L[n1], R[n2];
/* 将数据复制到临时数组L[] 和 R[] */
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
/* 合并两个临时数组回到arr[l..r]*/
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++;
}
/* 复制剩余的L[]中的元素, 如果有 */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* 复制R[]中剩余的元素,如果有 */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/* l 是左端索引,而 r 是右端索引 */
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);
}
}
```
这段程序定义了一个`mergeSort`函数用于执行归并排序,并通过辅助函数`merge`来完成实际的合并工作[^1]。
为了验证此功能,在主函数中可以添加测试用例:
```cpp
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);
cout << "Given array is \n";
for(int i=0; i<arr_size; i++)
cout << arr[i] << " ";
mergeSort(arr, 0, arr_size - 1);
cout << "\nSorted array is \n";
for(int i=0; i<arr_size; i++)
cout << arr[i] << " ";
return 0;
}
```
上述代码展示了如何创建、初始化以及调用归并排序函数,最后打印排序后的结果。
阅读全文
相关推荐


















