给定一个整数序列,请按非递减序输出采用二路归并排序(递归法)的各趟排序后的结果(每完成一次归并操作就输出归并后的结果)。 输入格式: 测试数据有多组,处理到文件尾。每组测试数据第一行输入一个整数n(1≤n≤100),第二行输入n个整数。 输出格式: 对于每组测试,输出若干行,每行是一趟排序后的结果,每行的每两个数据之间留一个空格。 输入样例: 6 73 12 27 98 81 64 输出样例: 12 73 27 98 81 64 12 27 73 98 81 64 12 27 73 81 98 64 12 27 73 64 81 98 12 27 64 73 81 98
时间: 2024-02-13 15:01:21 浏览: 61
用递归和非递归两种方式实现归并排序
好的,以下是题目要求的 C 语言代码实现,可以在本地编译运行:
```c
#include <stdio.h>
void merge_sort(int arr[], int l, int r) {
if (l >= r) {
return;
}
int mid = (l + r) / 2;
merge_sort(arr, l, mid);
merge_sort(arr, mid + 1, r);
int i = l, j = mid + 1, k = 0;
int temp[100];
while (i <= mid && j <= r) {
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) {
temp[k++] = arr[i++];
}
while (j <= r) {
temp[k++] = arr[j++];
}
for (i = 0; i < k; i++) {
arr[l + i] = temp[i];
}
printf("%d", arr[0]);
for (i = 1; i <= r; i++) {
printf(" %d", arr[i]);
}
printf("\n");
}
int main() {
int n, arr[100], i;
while (scanf("%d", &n) != EOF) {
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
merge_sort(arr, 0, n - 1);
}
return 0;
}
```
其中 `merge_sort` 函数实现二路归并排序(递归法),`main` 函数读入数据并调用 `merge_sort` 函数进行排序。在 `merge_sort` 函数中,每一次归并后输出当前数组的状态。
阅读全文