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

Rossy Yan

修改于 2024-12-26 10:19:23

8200

代码可运行

文章被收录于专栏：C++C++【Educoder实训】头歌实践教学平台

运行总次数：0

代码可运行

任务描述

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

相关知识

为了完成本关任务，你需要掌握：

排序算法基础概念
插入排序知识
间隔序列（增量序列）的概念
算法的时间复杂度和空间复杂度分析
代码实现技巧（如循环嵌套、索引计算）

1. 排序算法基础概念排序算法是将一组数据按照特定的顺序（通常是升序或降序）进行重新排列的算法。常见的排序算法有冒泡排序、插入排序、选择排序、快速排序、归并排序等等。排序算法的稳定性也是一个重要概念，稳定排序是指在排序过程中，相等元素的相对顺序保持不变；不稳定排序则可能改变相等元素的相对顺序。其主要目的就是为了更方便地对数据进行查找、比较等操作，提高数据处理的效率。

2.插入排序知识

基本思想

希尔排序是基于插入排序改进而来的。插入排序的基本思想是把待排序的元素插入到已经排好序的部分序列中合适的位置，直到整个序列都变为有序。就好比整理一手扑克牌，每次拿到一张新牌，将它插入到已经整理好顺序的那部分牌里合适的位置。

具体步骤示例（以升序为例）：

首先，将数组的第一个元素看作是已经排好序的序列，长度为 1。
然后从第二个元素开始，依次将后面的元素插入到前面已排好序的序列中。比如对于元素 arr[i]（i 从 1 开始），将它与前面已排好序的元素 arr[j]（j 从 i - 1 开始，逐步往前递减）进行比较，如果 arr[i] 小于 arr[j]，就把 arr[j] 往后移一位，直到找到合适的位置（即 arr[i] 大于等于某个 arr[j]），将 arr[i] 插入进去。

代码示例：

#include <iostream>
#include <vector>
using namespace std;

// 插入排序函数
vector<int> insertion_sort(vector<int> arr) {
    for (size_t i = 1; i < arr.size(); ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
    return arr;
}

3. 间隔序列（增量序列）的概念在一些改进的排序算法（比如希尔排序）中会用到间隔序列（增量序列）。它是指在排序过程中，确定元素比较和移动的间隔大小的序列。比如希尔排序刚开始时，间隔可能比较大，这样可以让元素快速地大致移动到它最终位置的附近，然后随着排序的进行，间隔逐渐缩小，最后间隔为 1 时，就相当于进行普通的插入排序了。常用的增量序列有希尔本人提出的 N/2, N/4, N/8,..., 1（ N 为待排序元素个数）等不同形式，不同的增量序列对算法的效率等方面会有影响。
4. 算法的时间复杂度和空间复杂度分析

时间复杂度：用来衡量算法运行所需要的时间长短，通常用大 O 表示法来描述。它关注的是随着输入规模（比如数组元素个数 n）的增大，算法执行基本操作（如比较、交换、赋值等）的次数的增长趋势。例如插入排序在最坏情况下（数组是逆序的），时间复杂度是 O(n²)，因为对于每个元素，都可能需要和前面已经排好序的所有元素依次比较和移动；在最好情况下（数组已经有序），时间复杂度是 O(n)，只需要进行 n - 1 次比较操作即可。
空间复杂度：衡量算法在运行过程中临时占用的存储空间大小，同样用大 O 表示法。像插入排序，它只需要常数个额外的空间（比如用来暂存当前要插入的元素等），所以空间复杂度是 O(1)，属于原地排序算法，也就是不需要额外开辟大量和输入规模相关的存储空间就能完成排序。

5. 代码实现技巧（如循环嵌套、索引计算）

循环嵌套：在很多排序算法中都会用到循环嵌套。例如插入排序中，外层循环控制遍历整个数组（从第二个元素开始），内层循环用来在已排好序的部分序列里找到合适的插入位置，进行元素的比较和移动。合理运用循环嵌套可以按照设定的逻辑依次处理每个元素以及它们之间的关系，不过要注意循环的边界条件等设置，避免出现越界等错误。
索引计算：准确的索引计算对于排序算法的正确实现至关重要。比如在插入排序里，要通过索引准确地找到当前元素、前面已排好序的元素，以及在移动元素时更新正确的索引位置。像 arr[j + 1] = arr[j] 这样的语句中，通过正确的索引 j 和 j + 1 来实现元素的后移操作，而且在不同的循环条件下要确保索引始终处于合理的范围，保证算法逻辑的正确性。

测试说明

平台会对你编写的代码进行测试：
测试输入示例： 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;
}