文档内容
2023下 粉笔 教资
《 信 息技术》
数 据 结 构与算法 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 上 · 高中）某排序程序在运行时，其每趟排序的结果如下图所示。请问此过程体现
的是哪种排序 ? 此种排序算法的基本思想是什么 ?本页目的：了解出题方式即可
（2022 上 · 初中）一年级某班学生排队，按照身高从低到高，从左到右依次排列。已知第
一排八位学生的身高分别为：122,126,124,128,118,130,135,132（单位：厘米）。 如果使用
冒泡排序法对八位学生的身高进行升序排序，请你写出第一轮排序后的结果并简要说明冒泡
排序算法的基本思想。
（2022 下 · 初中）学校运动会举行1分钟跳绳比赛，5个人一组，需要编写一个程序，输入小
组内同学的跳绳次数，程序自动按次数由多到少的顺序输出，如输入126、80、204、158、
98，输出204、158、126、98、80。如果用冒泡的排序算法完成此过程，需要多少轮排序才
能完成？请写出上述输入数据在第二趟排序后得到的数据结果。二、数据排序算法 P297
（一）插入排序
1.直接插入排序
✓ 思想：将记录插入已经排好序的有序表中，若记录值小，则比其大的数依次后移
✓ 实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
9 1 5 8 3 7 4 6 2（一）插入排序 P298
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 9（一）插入排序 P299
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 9（一）插入排序 P299
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 9（二）交换排序 P300
1.冒泡排序
➢思想1：从前往后两两比较，如果前者大则交换顺序，以此类推，第一趟结果找到最大值在最后。
➢实例：用冒泡排序法将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
趟数 排序结果
原序列 9 1 5 8 3 7 4 6 2
第一趟
第二趟
第三趟
……（二）交换排序 P300
1.冒泡排序
➢思想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.快速排序
➢思想：第一趟时，第一个数为枢纽，最终找到枢纽的位置，使前面值比其小，后面值比其大
➢实例：将序列 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）（三）选择排序 P303
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，按升序排列。
排序结果
第一趟 1 9 5 8 3 7 4 6 2
第二趟 1 2 5 8 3 7 4 6 9
第三趟 1 2 3 8 5 7 4 6 9
第四趟 1 2 3 4 5 7 8 6 9
第五趟 1 2 3 4 5 7 8 6 9
第六趟 1 2 3 4 5 6 8 7 9
第七趟 1 2 3 4 5 6 7 8 9
第八趟 1 2 3 4 5 6 7 8 9书上无
（2022 上 · 高中）某排序程序在运行时，其每趟排序的结果如下图所示。请问此过程体现
的是哪种排序 ? 此种排序算法的基本思想是什么 ?（三）选择排序 P304
2.堆排序
90 10
70 20
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
第三步：继续调整成大顶堆（从上往下） → 移根到最后（三）选择排序 P306
2.堆排序
➢实例：将序列 50、10、90、30、70、40、80、60 和 20，按升序排列。
10
20
30
40 50 60 70
80 90
最后，依次输出序列即可。（四）归并排序 P307
➢思想：先分解（最终分成一个或两个数），然后再两两合并
➢实例：将序列50、10、90、30、70、40、80、60 和 20，按升序排列性能总结 【补充】
排序 比较次数 稳定性
直接插入排序 最好情况是(n-1)、最坏情况是n(n-1)/2 稳定
冒泡排序 n(n-1)/2 稳定
快速排序 最好情况是(nlogn)、最坏情况是n(n-1)/2 不稳定
简单选择排序 n(n-1)/2 不稳定
➢稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记
录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定的
2 3 2 1书上无
（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.可移植性二、计算机语言 补充下
书写方法 执行效率 可读性 可移植性
机器语言 二进制 好，直接执行 差 差
汇编语言 英文+数字 差，需要编译 较好 差
高级语言
单词+数学公式 最差，需要翻译 最好 好
第一个Fortran二、计算机语言 P309
翻译分为编译和解释两种
➢编译过程：
编译
源程序 目标文件 可执行程序 结果
.obj .exe
链接
➢解释：解释程序又称直译程序，边翻译边执行。
解释程序
源程序 结果三、程序设计方法 P310
（一）结构化程序设计（面向过程）
➢以过程为中心，重在分解步骤，重视细节
➢如，C语言
➢原则：自顶向下、逐步求精、单入单出
（二）面向对象程序设计
➢以对象为中心，重在分解对象及其行为，忽视细节
➢如，C++、Java、Python、VB
➢对象、类、消息；
➢特征：封装性、继承性、多态性下
节
内
容
