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

简介: 本文介绍了希尔排序算法的实现及相关知识。主要内容包括:- **任务描述**:实现希尔排序算法。- **相关知识**: - 排序算法基础概念,如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列(增量序列)的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧,如循环嵌套和索引计算。- **测试说明**:提供了测试输入和输出示例,帮助验证代码正确性。- **我的通关代码**:给出了完整的C++代码实现。- **测试结果**:展示了代码运行的测试结果。通过这些内容,读者可以全面了解希尔排序的原理和实现方法。

 

目录😋

任务描述

相关知识

1. 排序算法基础概念

2.插入排序知识

3. 间隔序列(增量序列)的概念

4. 算法的时间复杂度和空间复杂度分a析

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

测试说明

我的通关代码:

测试结果:


任务描述

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

相关知识

为了完成本关任务,你需要掌握:

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

1. 排序算法基础概念

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

2.插入排序知识

  1. 基本思想
  • 希尔排序是基于插入排序改进而来的。插入排序的基本思想是把待排序的元素插入到已经排好序的部分序列中合适的位置,直到整个序列都变为有序。就好比整理一手扑克牌,每次拿到一张新牌,将它插入到已经整理好顺序的那部分牌里合适的位置。
  • 具体步骤示例(以升序为例):
  • 首先,将数组的第一个元素看作是已经排好序的序列,长度为 1。
  • 然后从第二个元素开始,依次将后面的元素插入到前面已排好序的序列中。比如对于元素 arr[i]i 从 1 开始),将它与前面已排好序的元素 arr[j]ji - 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;
}
  • image.gif

3. 间隔序列(增量序列)的概念

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

4. 算法的时间复杂度和空间复杂度分析

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

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

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

image.gif


测试结果:

image.gif

image.gif

目录
相关文章
|
1月前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++ 芯片
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
70 19
|
1月前
|
存储 人工智能 算法
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
61 15
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
46 10
|
1月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
61 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1天前
|
编译器 C++ 开发者
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
|
1天前
|
安全 编译器 C语言
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
|
1天前
|
存储 程序员 C语言
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。
|
3天前
|
编译器 C语言 C++
类和对象的简述(c++篇)
类和对象的简述(c++篇)
|
1月前
|
存储 编译器 数据安全/隐私保护
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
51 13