用C语言实现n元素数组归并排序

在C语言中实现n元素数组的归并排序，首先需要了解归并排序的基本步骤：分治法，将数组分为两半，分别对它们进行排序，然后合并这两个已排序的部分。以下是递归版本的归并排序算法示例：
#include <stdio.h>
#include <stdlib.h>

// 归并两个已排序的数组到临时数组
void merge(int arr[], int temp[], int left, int mid, int right) {
int i = left, j = mid + 1, k = 0;
while (i <= mid &amp;&amp; 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 (i = left; i <= right; i++) {
arr[i] = temp[i];
}
}

// 主函数：归并排序
void mergeSort(int arr[], int n) {
if (n > 1) {
int mid = n / 2;
int *temp = (int*)malloc(n * sizeof(int)); // 分配临时数组

// 递归地对左右部分进行排序
mergeSort(arr, mid);
mergeSort(arr + mid, n - mid);

// 合并左右部分
merge(arr, temp, 0, mid - 1, n - 1);

free(temp); // 释放临时内存
}
}

// 测试
int main() {
int arr[] = {5, 2, 8, 6, 9, 4, 1, 7};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, n);
printf("Sorted array: \n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
登录后复制