目录😋
任务描述
测试说明
我的通关代码:
测试结果:
任务描述
本关任务:实现二路归并算法。
测试说明
平台会对你编写的代码进行测试:
测试输入示例:
11
18 2 20 34 12 32 6 16 5 8 1
(说明:第一行是元素个数,第二行是待排序的原始关键字数据。)
输出示例:
排序前:18 2 20 34 12 32 6 16 5 8 1
第1趟归并:2 18 20 34 12 32 6 16 5 8 1
第2趟归并:2 18 20 34 6 12 16 32 1 5 8
第3趟归并:2 6 12 16 18 20 32 34 1 5 8
第4趟归并:1 2 5 6 8 12 16 18 20 32 34
排序后:1 2 5 6 8 12 16 18 20 32 34
开始你的任务吧,祝你成功!
我的通关代码:
#include <malloc.h>
#include <stdio.h>
#define MAXL 100 //最大长度
typedef int KeyType; //定义关键字类型为int
typedef char InfoType;
typedef struct {
KeyType key; //关键字项
InfoType data; //其他数据项,类型为InfoType
} RecType; //查找元素的类型
int count = 1; //全局变量,记录第几趟归并
void CreateList(RecType R[], KeyType keys[], int n) //创建顺序表
{
for (int i = 0; i < n; i++) // R[0..n-1]存放排序记录
R[i].key = keys[i];
}
void DispList(RecType R[], int n) //输出顺序表
{
for (int i = 0; i < n; i++)
printf("%d ", R[i].key);
printf("\n");
}
//一次归并:将两个有序表R[low..mid]和R[mid+1..high]归并为一个有序表R[low..high]中
void Merge(RecType R[], int low, int mid, int high) {
/********** Begin *********/
RecType *R1 = (RecType *)malloc((high - low + 1) * sizeof(RecType));
int i = low, j = mid + 1, k = 0;
while (i <= mid && j <= high) {
if (R[i].key <= R[j].key)
R1[k++] = R[i++];
else
R1[k++] = R[j++];
}
while (i <= mid)
R1[k++] = R[i++];
while (j <= high)
R1[k++] = R[j++];
for (k = 0, i = low; i <= high; i++, k++)
R[i] = R1[k];
free(R1);
/********** End **********/
}
void MergePass(RecType R[], int length, int n) //实现一趟归并
{
/********** Begin *********/
int i;
for (i = 0; i + 2 * length - 1 < n; i += 2 * length)
Merge(R, i, i + length - 1, i + 2 * length - 1);
if (i + length - 1 < n)
Merge(R, i, i + length - 1, n - 1);
/********** End **********/
}
void MergeSort(RecType R[], int n) //二路归并排序算法
{
/********** Begin *********/
int length = 1;
printf("排序前:");
DispList(R, n);
while (length < n) {
MergePass(R, length, n);
printf("第%d趟归并:", count++);
DispList(R, n);
length *= 2;
}
printf("排序后:");
DispList(R, n);
/********** End **********/
}
int main() {
/********** Begin *********/
int n;
scanf("%d", &n);
KeyType keys[MAXL];
RecType R[MAXL];
for (int i = 0; i < n; i++)
scanf("%d", &keys[i]);
CreateList(R, keys, n);
MergeSort(R, n);
/********** End **********/
return 0;
}