用c++写一个合并算法
时间: 2023-01-31 22:03:24 浏览: 72
归并排序是一种分治算法,它将一个序列递归地分成两半,然后将两个有序的子序列合并成一个有序的序列。在这里,我们将提供一个C语言实现的示例:
```
#include <stdio.h>
#include <stdlib.h>
// 合并两个有序数组
void merge(int* arr, int* left, int leftSize, int* right, int rightSize) {
int i = 0, j = 0, k = 0;
while (i < leftSize && j < rightSize) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
}
else {
arr[k++] = right[j++];
}
}
// 复制剩余元素
while (i < leftSize) {
arr[k++] = left[i++];
}
while (j < rightSize) {
arr[k++] = right[j++];
}
}
// 归并排序
void mergeSort(int* arr, int size) {
if (size < 2) {
return;
}
int mid = size / 2;
int* left = malloc(mid * sizeof(int));
int* right = malloc((size - mid) * sizeof(int));
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = arr[i];
}
mergeSort(left, mid);
mergeSort(right, size - mid);
merge(arr, left, mid, right, size - mid);
free(left);
free(right);
}
int main() {
int arr[] = {5, 2, 4, 7, 1, 3, 2, 6};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, size);
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```
上面的代码实现了一个归并排序算法,它通过递归地将序列分成两半,然后将两个有序的子序列合并成一个有序的序列。它使用了一个