利用归并排序算法对以下数组进行排序。 c++
时间: 2024-10-11 07:12:52 浏览: 8
归并排序是一种基于分治策略的稳定排序算法,它的基本思想是将待排序序列不断分割成两个独立的子序列,直到每个子序列只有一个元素,然后逐层合并。以下是利用C++实现归并排序对数组进行排序的基本步骤:
```cpp
#include <iostream>
using namespace std;
// 归并函数
void merge(int arr[], int l, int m, int r) {
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 j = 0; j < n2; j++)
R[j] = arr[m + 1+ j];
// 合并临时数组回原数组
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k++] = L[i++];
} else {
arr[k++] = R[j++];
}
}
// 将剩余部分拷贝回原数组
while (i < n1) {
arr[k++] = L[i++];
}
while (j < n2) {
arr[k++] = R[j++];
}
}
// 归并排序主函数
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);
}
}
int main() {
int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10};
int size = sizeof(arr) / sizeof(arr[0]);
cout << "Original array: ";
for (int i=0; i<size; i++) {
cout << arr[i] << " ";
}
mergeSort(arr, 0, size-1);
cout << "\nSorted array: ";
for (int i=0; i<size; i++) {
cout << arr[i] << " ";
}
return 0;
}
```
在这个示例中,我们首先定义了一个`merge()`函数用于合并两个已排序的部分,然后在`mergeSort()`函数中递归地将数组分割,并调用`merge()`合并它们。最后在`main()`函数中创建一个测试数组,对其进行排序并打印结果。