如何用C++使用归并排序对一个数组中的元素进行排序
时间: 2024-04-29 12:21:16 浏览: 14
以下是使用C语言实现归并排序的示例代码:
```c
#include <stdio.h>
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++;
}
}
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[] = { 12, 11, 13, 5, 6, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
```
该程序的输出如下:
```
Original array: 12 11 13 5 6 7
Sorted array: 5 6 7 11 12 13
```
首先,`merge()`函数将两个子数组合并为一个已排序的数组。`mergeSort()`函数是递归的,将输入数组分成两半并对每个子数组进行递归调用,直到子数组只包含一个元素。然后,它将两个子数组合并为一个已排序的数组。最后,`main()`函数调用`mergeSort()`函数来对输入数组进行排序,并输出结果。