归并排序算法用c++实现
时间: 2023-11-10 20:02:01 浏览: 39
好的,归并排序是一种基于分治思想的排序算法,其实现过程如下:
```c
#include <stdio.h>
#include <stdlib.h>
void merge(int arr[], int left, int mid, int right) {
int *temp = (int *)malloc((right - left + 1) * sizeof(int));
int i = left, j = mid + 1, k = 0;
while (i <= mid && j <= right) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
}
else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= right) {
temp[k++] = arr[j++];
}
for (int i = 0; i < k; i++) {
arr[left + i] = temp[i];
}
free(temp);
}
void merge_sort(int arr[], int left, int right) {
if (left >= right) {
return;
}
int mid = left + ((right - left) >> 1);
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
merge(arr, left, mid, right);
}
int main() {
int arr[] = {5, 2, 4, 7, 1, 3, 2, 6};
int len = sizeof(arr) / sizeof(int);
merge_sort(arr, 0, len - 1);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
```