【数据结构——内排序】希尔排序（头歌实践教学平台习题）【合集】

目录😋

任务描述

测试说明

我的通关代码:

测试结果：

任务描述

本关任务：实现希尔排序算法。

测试说明

平台会对你编写的代码进行测试：

测试输入示例：
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;
}

测试结果：