目录😋
任务描述
测试说明
我的通关代码:
测试结果:
任务描述
本关任务:实现希尔排序算法。
测试说明
平台会对你编写的代码进行测试:
测试输入示例:
10
9 8 7 6 5 4 3 2 1 0
(说明:第一行是元素个数,第二行是待排序的原始关键字数据。)
输出示例:
排序前:9 8 7 6 5 4 3 2 1 0
d=5: 4 3 2 1 0 9 8 7 6 5
d=2: 0 1 2 3 4 5 6 7 8 9
d=1: 0 1 2 3 4 5 6 7 8 9
排序后:0 1 2 3 4 5 6 7 8 9
开始你的任务吧,祝你成功!
我的通关代码:
#include <malloc.h>
#include <stdio.h>
#define MAXL 100 //最大长度
typedef int KeyType; //定义关键字类型为int
typedef char InfoType;
typedef struct {
KeyType key; //关键字项
InfoType data; //其他数据项,类型为InfoType
} RecType; //查找元素的类型
// 创建顺序表
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");
}
// 显示一趟划分后的结果(这里在希尔排序中主要用于展示每趟按不同间隔排序后的结果)
void disppart(RecType R[], int s, int t) {
for (int i = 0; i < s; i++)
printf(" ");
for (int i = s; i <= t; i++)
printf("%3d ", R[i].key);
printf("\n");
}
// 希尔排序算法主体
void ShellSort(RecType R[], int n) {
int d, i, j;
RecType tmp;
// 初始化间隔序列,这里采用常用的Hibbard间隔序列(2^k -
// 1),从n/2开始逐步缩小间隔
for (d = n / 2; d > 0; d /= 2) {
printf(" d=%d: ", d);
// 对每个间隔下的子序列进行插入排序
for (i = d; i < n; i++) {
tmp = R[i];
j = i - d;
while (j >= 0 && R[j].key > tmp.key) {
R[j + d] = R[j];
j -= d;
}
R[j + d] = tmp;
}
// 输出当前间隔下排序后的结果
DispList(R, n);
}
}
int main() {
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);
printf("排序前:");
DispList(R, n);
ShellSort(R, n);
printf("排序后:");
DispList(R, n);
return 0;
}