文档内容
~ 2 0 2 4 年 教 师 资 格 ~
《 信 息技术( 科技) 》
数 据 结 构与算法 5 / 5
讲师：阿彬
更多干货关注 粉笔教师教育 粉笔教师第六节 查找和排序算法P295
一、数据查找算法
一、顺序查找
➢ 定义：在序列中依次与给定值进行比较。
➢ 实例：在（2，45，36，17，6，86，62，87，91，25）中，查找数值“6”。P296
（二）二分查找
定义：前提有序（升序），先与中间值进行比较，若比中间值小则在前半段继续折半查找。
◆
实例：在（8，15，23，37，46，63，66，71，80，86，88，101）中，查找“71”
◆书上无
试题巩固
用对分查找法和顺序查找法在数字序列“1，2，3，5，10，13，21，34，55”中查找数
字13，两种方法都能访问到的数字有（ ）。
A.34
B.5
C.21
D.10了解出题
试题巩固
（2022 上 · 初中）一年级某班学生排队，按照身高从低到高，从左到右依次排列。
已知第 一排八位学生的身高分别为：122,126,124,128,118,130,135,132（单位：
厘米）。 如果使用 冒泡排序法对八位学生的身高进行升序排序，请你写出第一轮排
序后的结果并简要说明冒泡排序算法的基本思想。
（2022 下 · 初中）学校运动会举行1分钟跳绳比赛，5个人一组，需要编写一个程
序，输入小组内同学的跳绳次数，程序自动按次数由多到少的顺序输出，如输入
126、80、204、158、98，输出204、158、126、98、80。如果用冒泡的排序
算法完成此过程，需要多少轮排序才能完成？请写出上述输入数据在第二趟排序后
得到的数据结果。了解出题
试题巩固
（2022 上 · 高中）某排序程序在运行时，其每趟排序的结果如下图所示。请问此
过程体现 的是哪种排序 ? 此种排序算法的基本思想是什么 ?P297
二、数据排序算法
（一）插入排序-1. 直接插入排序
➢思想：将记录插入已经排好序的有序表中，若记录值小，则比其大的数依次后移
➢实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
9 1 5 8 3 7 4 6 2P298
（一）插入排序
1.直接插入排序
➢实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
待排元素 需插入位置 排序结果
第 0 趟 9 第一个位置 9 默认第一个值，是有序的
第一趟 1 9的前面 1 9
第二趟 5 1和9之间 1 5 9
第三趟 8 5和9之间 1 5 8 9
第四趟 3 1和5之间 1 3 5 8 9
第五趟 7 5和8之间 1 3 5 7 8 9
第六趟 4 3和5之间 1 3 4 5 7 8 9
第七趟 6 5和7之间 1 3 4 5 6 7 8 9
第八趟 2 1和3之间 1 2 3 4 5 6 7 8 9P298
（一）插入排序
2. 希尔排序
➢ 思想：按增量分成多个子序列，对其排序，再缩短增量。（增量m= n/2 ，m= 𝑚/2 ，直至m=1）
➢实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
1 2 3 4 5 6 7 8 9
9 1 5 8 3 7 4 6 2
1 2 3 4 5 6 7 8 9P298
（一）插入排序
2. 希尔排序
➢ 思想：按增量分成多个子序列，对其排序，再缩短增量。（增量m= n/2 ，m= 𝑚/2 ，直至m=1）
➢实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
1 2 3 4 5 6 7 8 9
2 1 4 6 3 7 5 8 9
1 2 3 4 5 6 7 8 9P298
（一）插入排序
2. 希尔排序
➢ 思想：按增量分成多个子序列，对其排序，再缩短增量。（增量m= n/2 ，m= 𝑚/2 ，直至m=1）
➢实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
1 2 3 4 5 6 7 8 9
2 1 3 6 4 7 5 8 9
1 2 3 4 5 6 7 8 9P300
（二）交换排序
1. 冒泡排序
➢思想1：从前往后两两比较，如果前者大则交换顺序，以此类推，第一趟结果找到最大值在最后。
➢实例：用冒泡排序法将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
趟数 排序结果
原序列 9 1 5 8 3 7 4 6 2
第一趟
第二趟
第三趟
……P300
（二）交换排序
1. 冒泡排序
➢实例：用冒泡排序法将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
趟数 排序结果 结论
第一趟 1 5 8 3 7 4 6 2 9 找到第一个最大的值，放在最后
第二趟 1 5 3 7 4 6 2 8 9 找到第两个最大的值，放在最后
第三趟 1 3 5 4 6 2 7 8 9 找到第三个最大的值，放在最后
第四趟 1 3 4 5 2 6 7 8 9 找到第四个最大的值，放在最后
第五趟 1 3 4 2 5 6 7 8 9 找到第五个最大的值，放在最后
第六趟 1 3 2 4 5 6 7 8 9 找到第六个最大的值，放在最后
第七趟 1 2 3 4 5 6 7 8 9 找到第七个最大的值，放在最后
第八趟 1 2 3 4 5 6 7 8 9 找到第八个最大的值，放在最后P300
（二）交换排序
1. 冒泡排序
➢思想2：从后往前两两比较，如果后者小则交换顺序，以此类推，第一趟结果找到最小值在最前。
➢实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
趟数 排序结果
原序列 9 1 5 8 3 7 4 6 2
第一趟
第二趟
第三趟
……书上无
试题巩固
（2022下·初中）学校运动会举行1分钟跳绳比赛，5个人一组，需要编写一个程序，输入
小组内同学的跳绳次数，程序自动按次数由多到少的顺序输出，如输入126、80、204、
158、98，输出204、158、126、98、80。如果用冒泡的排序算法完成此过程，需要多少
轮排序才能完成？请写出上述输入数据在第二趟排序后得到的数据结果。P301
（二）交换排序
2. 快速排序
结论：① 枢纽值 PK 最远值；②后续趟数：左右两部分同时递归排序
➢思想：第一趟时，第一个数为枢纽，最终找到枢纽的位置，使前面值比其小，后面值比其大
➢实例：将序列 50、10、90、30、70、40、80、60 和 20，按升序排列。
第 一 趟 比较数 操作 执行过程
初始状态 确定枢纽值：50 50 10 90 30 70 40 80 60 20
第一次
第二次
第三次
第四次
第五次
第六次
第七次
第八次书上无
试题巩固
（单选）给定的整数序列（54、73、21、35、67、78、63、24、89）进行从小到大的排
序时，采用快速排序的第一趟扫描的结果是（ ）。
A.（24、21、35、54、67、78、63、73、89）
B.（24、35、21、54、67、78、63、73、89）
C.（24、21、35、54、67、63、73、78、89）
D.（21、24、35、54、63、67、73、78、89）
54 73 21 35 67 78 63 24 89P303
（三）选择排序
1. 简单选择排序
➢思想：找无序序列最小的数与无序序列第一个互换位置，该数成为有序序列的最后一个数。
➢实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
排序结果
原始状态 9 1 5 8 3 7 4 6 2
第一趟
第二趟
第三趟
第四趟P303
（三）选择排序
1. 简单选择排序
➢思想：找无序序列最小的数与无序序列第一个互换位置，该数成为有序序列的最后一个数。
➢实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
预设最小值 实际最小值 操作 排序结果
第一趟 9 1 9和1互换位置 1 9 5 8 3 7 4 6 2
第二趟 9 2 9和2互换位置 1 2 5 8 3 7 4 6 9
第三趟 5 3 5和3互换位置 1 2 3 8 5 7 4 6 9
第四趟 8 4 8和4互换位置 1 2 3 4 5 7 8 6 9
第五趟 5 5 不交换 1 2 3 4 5 7 8 6 9
第六趟 7 6 7和6互换位置 1 2 3 4 5 6 8 7 9
第七趟 8 7 8和7互换位置 1 2 3 4 5 6 7 8 9
第八趟 8 8 不交换 1 2 3 4 5 6 7 8 9书上无
试题巩固
（2022 上 · 高中）某排序程序在运行时，其每趟排序的结果如下图所示。请问此过程体
现 的是哪种排序 ? 此种排序算法的基本思想是什么 ?P304
（三）选择排序
2.堆排序
➢堆是完全二叉树
90 10
20
70 40
80
30 70 80 50
60 10 40 50
90 60
30 20
大顶堆 小顶堆
根节点＞左/右子树 根节点＜左/右子树P304
（三）选择排序
2. 堆排序
➢实例：将序列 50、10、90、30、70、40、80、60 和 20，按升序排列。
90
70
80
60 10 40 50
30 20
第一步：构造初始堆 → 调整成大顶堆（从第一个非叶子节点往上逐步调整）P304
（三）选择排序
2. 堆排序
➢实例：将序列 50、10、90、30、70、40、80、60 和 20，按升序排列。
90 20
70 70
80 80
60 10 40 50 60 10 40 50
30 20 30 90
第二步： 根与最后一个元素互换位置→ 并将最后一个元素断开连接P305
（三）选择排序
2. 堆排序
➢实例：将序列 50、10、90、30、70、40、80、60 和 20，按升序排列。
20
80
70
80
70
50
60 10 40 50
60 10 40 20
30 90
30 90
第三步：继续调整成大顶堆（从根节点往下） → 重复第二步P305
（三）选择排序
2. 堆排序
➢实例：将序列 50、10、90、30、70、40、80、60 和 20，按升序排列。
70
30
60
70 50
50
30 10 40 20
60 10 40 20
80 90
80 90
第三步：继续调整成大顶堆（从根节点往下） → 重复第二步P305
（三）选择排序
2. 堆排序
➢实例：将序列 50、10、90、30、70、40、80、60 和 20，按升序排列。
10
20
30
40 50 60 70
80 90
最后，依次输出序列即可。P306
（四）归并排序
➢思想：先分解（最终分成一个或两个数），然后再两两合并
➢实例：将序列50、10、90、30、70、40、80、60 和 20，按升序排列【补充】
性能总结
排序 趟数 比较次数
直接插入排序 n-1 最好情况是(n-1)、最坏情况是n(n-1)/2
冒泡排序 n-1 n(n-1)/2
快速排序 - 最好情况是(nlogn)、最坏情况是n(n-1)/2
简单选择排序 n-1 n(n-1)/2书上无
试题巩固
（2021下·高中）对长度为n的线性表做快速排序，在最坏情况下的比较次数是（ ）。
A.n
B.n-1
C.(n-1)/2
D.n(n-1)/2第七节 程序基础P307
一、相关术语
（一）程序 – 计算机程序
➢由人事先规定的让计算机完成某项工作的操作步骤
➢程序=算法+数据结构
（二）程序设计 – 过程
➢分析阶段 → 设计阶段 → 编码阶段 → 测试阶段 → 调试和运行阶段
（三）程序设计语言 - 计算机语言
➢一组用来定义计算机程序的语法规则P308
二、计算机语言
1.机器语言
0000 代表加载LOAD
0001 代表暂存器 B
000000000001 代表地址为1的内存
2.汇编语言
标号 指令 说明
START GET7； 把7送进累加器ACC中
ADD8； 累加器ACC+8送进ACC中
3.高级语言
四角度：A.书写方法； B.执行效率； C.可读性； D.可移植性总结下
二、计算机语言
书写方法 执行效率 可读性 可移植性
机器语言 二进制 好，直接执行 差 差
汇编语言 英文+数字 差，需要编译 较好 差
高级语言
第一个 单词+数学公式 最差，需要翻译 最好 好
FortranP309
一、相关术语
翻译分为编译和解释两种
➢编译过程：
编译
源程序 目标文件 可执行程序 结果
.obj .exe
链接
➢解释：解释程序又称直译程序，边翻译边执行。
解释程序
源程序 结果书上无
试题巩固
1. C 语言属于（ ）语言。
A. 机器语言 B. 汇编语言
C. 高级语言 D. 面向对象的语言
2. 编译程序的最终目标是（ ）。
A. 发现源程序中的语法错误
B. 改正源程序中的语法错误
C. 将源程序翻译成目标程序
D. 将某一高级语言程序翻译成另一高级语言程序P309
三、程序设计方法
（一）结构化程序设计（面向过程）
➢以过程为中心，重在分解步骤，重视细节
➢如，C语言
➢原则：自顶向下、逐步求精、单入单出
（二）面向对象程序设计
➢以对象为中心，重在分解对象及其行为，忽视细节
➢如，C++、Java、Python、VB
➢对象、类、消息；
➢特征：封装性、继承性、多态性书上无
试题巩固
（ ）是一种信息隐蔽技术，它体现于类的说明，是对象的重要特性。
A. 封装
B. 继承
C. 多态
D. 对象下
节
内
容
2024FENBI
