头歌数据结构-排序的实现及其应用

发布时间：2026/10/20 2:23:28

头歌数据结构-排序的实现及其应用

第1关：直接插入排序

100

  • 学习内容
  • 参考答案
  • 记录
  • 评论
任务描述

本关任务：实现直接插入排序。

相关知识

为了完成本关任务，你需要掌握：1.顺序表的类型定义，2.直接插入排序。

顺序表的类型定义
  1. #define MAXSIZE 100
  2. typedef int KeyType; /*关键字类型*/
  3. typedef struct
  4. {
  5. KeyType key;
  6. /*InfoType otherinfo;*/
  7. }RedType; /*记录类型*/
  8. typedef struct
  9. {
  10. RedType r[MAXSIZE+1]; /*r[0]闲置或用作"监视哨"*/
  11. int length; /*length存放表长*/
  12. }SeqList; /*顺序表类型*/
直接插入排序

算法思想：先将第1个记录看成是一个有序的子序列；然后从第2个记录开始逐个进行插入；直至整个序列变成一个按关键字非递减有序序列为止。

编程要求

在右侧编辑器中补充代码，完成InsertSort函数，以实现直接插入排序。具体要求如下：

* InsertSort：采用直接插入排序法，将表中记录按关键字非递减排列。

测试说明

可在右侧文件夹中查看step1/Main.cpp文件，以便于你的操作。

输入说明： 输入若干记录的关键字，以-1标志结束。

输出说明： 第一行输出排序之前的各记录的关键字。 第二行输出排序之后的各记录的关键字。

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

测试输入:49 38 65 97 76 13 27 49 -1

预期输出：49 38 65 97 76 13 27 4913 27 38 49 49 65 76 97//末尾换行

开始你的任务吧，祝你成功！

/************************************************************* 直接插入排序 实现文件 更新于2026年10月18日 **************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "sort.h" void InsertSort(SeqList &L) /*直接插入排序*/ { int i,j; for(i=2;i<=L.length;i++){ // 请在这里补充代码，完成本关任务 /********** Begin *********/ KeyType key = L.r[i].key; j=i-1; while(j>=1 && L.r[j].key > key){ L.r[j+1].key=L.r[j].key; j--; } L.r[j+1].key = key; /********** End **********/ } } void SeqListInput(SeqList &L) /*输入若干记录的关键字，存放到顺序表L中*/ { int i=1; KeyType x; scanf("%d",&x); while(x!=-1) { L.r[i++].key=x; scanf("%d",&x); } L.length=i-1; } void SeqListOutput(SeqList L) /*输出顺序表L中各记录的关键字*/ { int i; for(i=1;i<=L.length;i++) printf("%d ",L.r[i].key); printf("\n"); }

第2关：希尔排序

200

  • 学习内容
  • 参考答案
  • 记录
  • 评论
任务描述

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

相关知识

为了完成本关任务，你需要掌握：1.顺序表的类型定义，2.希尔排序。

顺序表的类型定义
  1. #define MAXSIZE 100
  2. typedef int KeyType; /*关键字类型*/
  3. typedef struct
  4. {
  5. KeyType key;
  6. /*InfoType otherinfo;*/
  7. }RedType; /*记录类型*/
  8. typedef struct
  9. {
  10. RedType r[MAXSIZE+1]; /*r[0]闲置或用作"监视哨"*/
  11. int length; /*length存放表长*/
  12. }SeqList; /*顺序表类型*/
希尔排序

算法思想：先将待排记录序列按某个增量分割成若干个子序列，然后对各子序列分别进行直接插入排序，当整个序列中的记录 “基本有序” 时，再对全体记录进行一次直接插入排序。

编程要求

在右侧编辑器中补充代码，完成ShellInsert函数，以实现希尔排序。具体要求如下：

* ShellInsert：对顺序表L作一趟增量为d的希尔排序。

测试说明

可在右侧文件夹中查看step2/Main.cpp文件，以便于你的操作。

输入说明： 输入若干记录的关键字，以-1标志结束。

输出说明： 第一行输出排序之前的各记录的关键字。 第二行输出排序之后的各记录的关键字。

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

测试输入:49 38 65 97 76 13 27 49 -1

预期输出：49 38 65 97 76 13 27 4913 27 38 49 49 65 76 97//末尾换行

开始你的任务吧，祝你成功！

/************************************************************* 希尔排序 实现文件 更新于2026年10月18日 **************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "sort.h" void ShellInsert(SeqList &L, int d) /*对顺序表L作一趟增量为d的希尔插入排序*/ { // 请在这里补充代码，完成本关任务 /********** Begin *********/ int i,j; for(i=d+1;i<=L.length;i++){ if(L.r[i].key<L.r[i-d].key){ L.r[0]=L.r[i]; for(j=i-d;j>0 &&L.r[0].key<L.r[j].key;j-=d){ L.r[j+d]=L.r[j]; } L.r[j+d]=L.r[0]; } } /********** End **********/ } void ShellSort(SeqList &L) /*希尔排序*/ { int d; d=L.length/2; while(d!=0) /*调用一趟增量为d的希尔插入排序*/ { ShellInsert(L,d); d=d/2; } } void SeqListInput(SeqList &L) /*输入若干记录的关键字，存放到顺序表L中*/ { int i=1; KeyType x; scanf("%d",&x); while(x!=-1) { L.r[i++].key=x; scanf("%d",&x); } L.length=i-1; } void SeqListOutput(SeqList L) /*输出顺序表L中各记录的关键字*/ { int i; for(i=1;i<=L.length;i++) printf("%d ",L.r[i].key); printf("\n"); }

第3关：快速排序

200

  • 学习内容
  • 参考答案
  • 记录
  • 评论
任务描述

本关任务：实现快速排序。

相关知识

为了完成本关任务，你需要掌握：1.顺序表的类型定义，2.快速排序。

顺序表的类型定义
  1. #define MAXSIZE 100
  2. typedef int KeyType; /*关键字类型*/
  3. typedef struct
  4. {
  5. KeyType key;
  6. /*InfoType otherinfo;*/
  7. }RedType; /*记录类型*/
  8. typedef struct
  9. {
  10. RedType r[MAXSIZE+1]; /*r[0]闲置或用作"监视哨"*/
  11. int length; /*length存放表长*/
  12. }SeqList; /*顺序表类型*/
快速排序

算法思想：首先在待排记录中任取一个记录（通常取第一个记录）作为枢轴，将枢轴放入适当的位置后，待排记录被枢轴分割成两部分，并使得枢轴左边记录的关键字均小于枢轴，右边的均大于枢轴；然后分别对这两部分继续进行快速排序，以达到整个序列有序。

编程要求

在右侧编辑器中补充代码，完成QuickSort函数，以实现快速排序。具体要求如下：

* QuickSort：对顺序表L的子序列L.r[low…high]作快速排序。

测试说明

可在右侧文件夹中查看step3/Main.cpp文件，以便于你的操作。

输入说明： 输入若干记录的关键字，以-1标志结束。

输出说明： 第一行输出排序之前的各记录的关键字。 第二行输出排序之后的各记录的关键字。

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

测试输入:49 38 65 97 76 13 27 49 -1

预期输出：49 38 65 97 76 13 27 4913 27 38 49 49 65 76 97 //末尾换行

开始你的任务吧，祝你成功！

/************************************************************* 快速排序 实现文件 更新于2026年10月18日 **************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "sort.h" int Partition(SeqList &L, int low, int high) { KeyType pivotkey = L.r[low].key; L.r[0] = L.r[low]; while (low < high) { while (low < high && L.r[high].key >= pivotkey) high--; L.r[low] = L.r[high]; while (low < high && L.r[low].key <= pivotkey) low++; L.r[high] = L.r[low]; } L.r[low] = L.r[0]; return low; } void QuickSort(SeqList &L, int low, int high) /*对顺序表L的子序列L.r[low…high]作快速排序*/ { // 请在这里补充代码，完成本关任务 /********** Begin *********/ int i; if (low < high) { i = Partition(L, low, high); /********** End **********/ /*分别对左、右两部分进行递归排序*/ QuickSort(L,low,i-1);/*对左半区L.r[low..i-1]进行快速排序*/ QuickSort(L,i+1,high);/*对右半区L.r[i+1..high]进行快速排序*/ } } void SeqListInput(SeqList &L) /*输入若干记录的关键字，存放到顺序表L中*/ { int i=1; KeyType x; scanf("%d",&x); while(x!=-1) { L.r[i++].key=x; scanf("%d",&x); } L.length=i-1; } void SeqListOutput(SeqList L) /*输出顺序表L中各记录的关键字*/ { int i; for(i=1;i<=L.length;i++) printf("%d ",L.r[i].key); printf("\n"); }

第4关：堆排序

300

  • 学习内容
  • 参考答案
  • 记录
  • 评论
任务描述

本关任务：实现堆排序。

相关知识

为了完成本关任务，你需要掌握：1.顺序表的类型定义，2.堆，3.堆排序。

顺序表的类型定义
  1. #define MAXSIZE 100
  2. typedef int KeyType; /*关键字类型*/
  3. typedef struct
  4. {
  5. KeyType key;
  6. /*InfoType otherinfo;*/
  7. }RedType; /*记录类型*/
  8. typedef struct
  9. {
  10. RedType r[MAXSIZE+1]; /*r[0]闲置或用作"监视哨"*/
  11. int length; /*length存放表长*/
  12. }SeqList; /*顺序表类型*/
堆
  • 含有n个关键字的序列{ k1，k2，…，kn }，当且仅当满足以下性质(1)或(2)时，称之为堆：

(1) Ki​≤K2i​ 且 Ki​≤K2i+1​ ,i=1，2，...，⌊ n/2 ⌋，称为小顶堆；

(2) Ki​≥K2i​ 且 Ki​≥K2i+1​ ，i=1，2，...，⌊ n/2 ⌋，称为大顶堆。

  • 如果用一维数组存放该序列，并把此数组看成是一棵完全二叉树的顺序存储结构，则堆实质上是满足如下性质的完全二叉树：树中所有分支结点的关键字值 Ki​ 均不大于（或不小于）其左右孩子结点的关键字值 K2i​ 和K2i+1​。

  • 若序列{ k1，k2，…，kn }是堆，则堆顶元素必为序列中最小值（或最大值）。

堆排序

算法思想：首先将待排序列建成一个堆，得到关键字最小（或最大）的记录，输出堆顶的最小（大）值；然后将剩余的n-1个元素重新建成一个堆，得到次小值，输出堆顶；如此反复执行，便能得到一个有序序列。这一过程称为“堆排序”。

编程要求

在右侧编辑器中补充代码，完成HeapAdjust函数，以实现堆排序。具体要求如下：

* HeapAdjust：调整L.r[low].key，使L.r[low..high]成为一个新大顶堆。

测试说明

可在右侧文件夹中查看step4/Main.cpp文件，以便于你的操作。

输入说明： 输入若干记录的关键字，以-1标志结束。

输出说明： 第一行输出排序之前的各记录的关键字。 第二行输出排序之后的各记录的关键字。

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

测试输入:49 38 65 97 76 13 27 49 -1

预期输出：49 38 65 97 76 13 27 4913 27 38 49 49 65 76 97//末尾换行

开始你的任务吧，祝你成功！

/************************************************************* 堆排序 实现文件 更新于2026年10月18日 **************************************************************/ #include <stdio.h> #include <stdlib.h> #include <string.h> #include "sort.h" void HeapAdjust(SeqList &L, int low, int high) {/*已知L.r[low..high]中记录的关键字除L.r[low].key之外均满足堆的定义，*/ /*调整L.r[low].key，使L.r[low..high]成为一个新大顶堆。*/ // 请在这里补充代码，完成本关任务 /********** Begin *********/ int i = low, j = 2 * i; KeyType temp = L.r[i].key; while (j <= high) { if (j < high && L.r[j].key < L.r[j + 1].key) { j++; } if (temp >= L.r[j].key) { break; } L.r[i].key = L.r[j].key; i = j; j = 2 * i; } L.r[i].key = temp; /********** End **********/ } void HeapSort(SeqList &L) /*堆排序*/ { int i; for(i=L.length/2;i>0;i--)/*从最后一个分支结点(编号为L.length/2)开始调整，建立初始堆*/ HeapAdjust(L,i,L.length); for(i=L.length;i>1;i--) { L.r[0]=L.r[1];L.r[1]=L.r[i];L.r[i]=L.r[0];/*将堆顶L.r[1]和当前最后一个记录L.r[i]交换*/ HeapAdjust(L,1,i-1);/*将剩余记录L.r[1..i-1]重新调整为堆*/ } } void SeqListInput(SeqList &L) /*输入若干记录的关键字，存放到顺序表L中*/ { int i=1; KeyType x; scanf("%d",&x); while(x!=-1) { L.r[i++].key=x; scanf("%d",&x); } L.length=i-1; } void SeqListOutput(SeqList L) /*输出顺序表L中各记录的关键字*/ { int i; for(i=1;i<=L.length;i++) printf("%d ",L.r[i].key); printf("\n"); }

相关新闻

周红伟：WorkBuddy Claw 你的一号员工已上岗，openclaw的二次开发

周红伟：WorkBuddy Claw 你的一号员工已上岗，openclaw的二次开发

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/20 2:23:28 阅读更多 →
page_alloc page_alloc_sysctl_init

page_alloc page_alloc_sysctl_init

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/20 2:23:28 阅读更多 →
page_alloc alloc_contig_dump_pages

page_alloc alloc_contig_dump_pages

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/20 2:23:28 阅读更多 →

最新新闻

3、内存 - 计算机品牌排行榜

3、内存 - 计算机品牌排行榜

基于2026年全球DRAM原厂产能、消费级内存模组市场占有率及用户综合口碑&#xff0c;当前电脑内存品牌排行榜如下&#xff0c;‌金士顿以全球领先的市占率稳居第一‌&#xff0c;一线电竞品牌在超频性能上表现突出&#xff0c;国产高性价比品牌近年市场份额增长迅猛。 1. 金士顿…

2026/10/20 2:57:47 阅读更多 →
Java部署YOLOv8模型量化提速：从FP32到INT8完整实践

Java部署YOLOv8模型量化提速：从FP32到INT8完整实践

前阵子做个工业质检项目&#xff0c;跑的是YOLOv8检测模型&#xff0c;部署环境锁定在Java后端。代码写完之后发现推理速度一直上不去&#xff0c;GPU利用率不高&#xff0c;内存带宽倒是快吃满了。一开始怀疑是不是ONNX导出有问题&#xff0c;后来一条条排查&#xff0c;瓶颈最…

2026/10/20 2:57:47 阅读更多 →
Windows下用WSL源码编译自托管AI助手openclaw完整指南

Windows下用WSL源码编译自托管AI助手openclaw完整指南

最近社区里 openclaw 这个自托管 AI 助手框架的讨论度明显起来了。这个项目在同一个仓库里维护两套可执行程序&#xff1a;Clawdbot 是完整版&#xff0c;除了消息收发和会话管理&#xff0c;还内置插件系统、定时任务和知识库接口&#xff1b;Moltbot 是精简版&#xff0c;把插…

2026/10/20 2:57:47 阅读更多 →
regnety_080_tv.tv2_in1k训练配方深度解析：torchvision v2权重为何能拿下82.59% Top-1精度

regnety_080_tv.tv2_in1k训练配方深度解析：torchvision v2权重为何能拿下82.59% Top-1精度

【免费下载链接】regnety_080_tv.tv2_in1k 项目地址&#xff1a; https://ai.gitcode.com/hf_mirrors/timm/regnety_080_tv.tv2_in1k 点击查看 免费下载 regnety_080_tv.tv2_in1k 是 timm 库中的 RegNetY-8GF 图像分类模型&#xff0c;由 torchvision 官方训练配方&#xff08…

2026/10/20 2:57:47 阅读更多 →
GhostTrack 快速上手：IP 追踪、号码归属与用户名排查 5 分钟跑通

GhostTrack 快速上手：IP 追踪、号码归属与用户名排查 5 分钟跑通

GhostTrack 快速上手&#xff1a;IP 追踪、号码归属与用户名排查 5 分钟跑通 【免费下载链接】GhostTrack Useful tool to track location or mobile number 项目地址: https://gitcode.com/GitHub_Trending/gh/GhostTrack GhostTrack 是一个终端 OSINT 信息检索脚本&am…

2026/10/20 2:57:47 阅读更多 →
基于垂向加速度与MLP神经网络的路面摩擦系数估计

基于垂向加速度与MLP神经网络的路面摩擦系数估计

最近在做一个车辆底盘控制相关的项目&#xff0c;核心目标之一是实时估计路面附着上限&#xff0c;也就是轮胎和路面之间的最大摩擦系数&#xff08;Tire-Road Friction Coefficient&#xff0c;简称TRFC&#xff09;。这东西在ABS、ESP、自动紧急制动里都是关键变量&#xff0…

2026/10/20 2:56:47 阅读更多 →

日新闻

CLRC663芯片Pin-to-Pin替代实战：从评估到量产全记录

CLRC663芯片Pin-to-Pin替代实战：从评估到量产全记录

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/20 1:01:30 阅读更多 →
ESP32舵机控制指南：原理、多路驱动与避坑实战

ESP32舵机控制指南：原理、多路驱动与避坑实战

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/20 1:01:30 阅读更多 →
位移法实现一阶低通滤波：单片机ADC采样降噪实战

位移法实现一阶低通滤波：单片机ADC采样降噪实战

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/20 1:01:30 阅读更多 →

周新闻

基于GMM的语音识别系统原理与MATLAB实现详解

基于GMM的语音识别系统原理与MATLAB实现详解

说到基于高斯混合模型&#xff08;GMM&#xff09;的语音识别系统&#xff0c;很多人第一反应就是一堆数学公式&#xff0c;觉得门槛很高。但如果你真的在MATLAB里把它落地跑通&#xff0c;会发现核心其实就是三件事&#xff1a;把声音变成特征向量&#xff0c;用GMM给每个类别…

2026/10/19 10:02:04 阅读更多 →
数字图像处理入门：反白、灰度化、调色板修改与导出txt实践

数字图像处理入门：反白、灰度化、调色板修改与导出txt实践

数字图像处理这四个字听起来挺唬人&#xff0c;但落到具体操作上&#xff0c;无非就是让计算机按你的想法“摆弄”像素。我在一个模拟项目X里用了一套特别经典的基础处理流程&#xff1a;对图像做反白、改调色板、彩色转灰度&#xff0c;最后把像素数据导出成txt文件。单看每一…

2026/10/19 17:32:41 阅读更多 →
机器人大脑技术盘点：具身智能的感知、决策与数据闭环

机器人大脑技术盘点：具身智能的感知、决策与数据闭环

如果你的信息流最近也天天刷到“机器人大脑”这个词&#xff0c;你会发现一个很有意思的现象&#xff1a;每个人说的“大脑”根本不是同一个东西。有人指的是大语言模型&#xff0c;有人指的是运动控制系统&#xff0c;还有人指的是能理解物理世界的端到端模型。在2026年这个时…

2026/10/20 2:50:50 阅读更多 →

月新闻

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/19 2:54:50 阅读更多 →
Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/19 9:10:22 阅读更多 →
黑夜航拍船只数据集训练YOLOV5模型全流程解析

黑夜航拍船只数据集训练YOLOV5模型全流程解析

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

2026/10/18 12:16:16 阅读更多 →