文档内容
~ 2025年教师资格证·《信息技术》~
数 据 结 构 与 算 法 5 / 5
主讲老师 孙珍珍
粉笔教师教育 粉笔教师二、排序算法 P296【了解出题方式】
（2022 上 · 初中）一年级某班学生排队，按照身高从低到高，从左到右依次排列。已知第一排八
位学生的身高分别为：122,126,124,128,118,130,135,132（单位：厘米）。 如果使用冒泡排序法
对八位学生的身高进行升序排序，请你写出第一轮排序后的结果并简要说明冒泡排序算法的基本思想。
（2022 下 · 初中）学校运动会举行1分钟跳绳比赛，5个人一组，需要编写一个程序，输入小组内
同学的跳绳次数，程序自动按次数由多到少的顺序输出，如输入126、80、204、158、98，输出
204、158、126、98、80。如果用冒泡的排序算法完成此过程，需要多少轮排序才能完成？请写出
上述输入数据在第二趟排序后得到的数据结果。【了解出题方式】
（2022 上 · 高中）某排序程序在运行时，其每趟排序的结果如下图所示。请问此过程体现的是哪
种排序 ? 此种排序算法的基本思想是什么 ?P296
（一）插入排序
1. 直接插入排序
Ø思想：将记录插入已经排好序的有序表中，若记录值小，则比其大的数依次后移
Ø实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
待排元素 需插入位置 排序结果
第 0 趟 9 第一个位置 9 默认第一个值，是有序的
第一趟 1
第二趟 5
第三趟 8
第四趟
……P296
（一）插入排序
①插入值 PK 已排好序的末尾值；
1.直接插入排序
②n个数值，需要n-1趟；
Ø将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
③最好情况：有序且同序，共比较n-1次
④最坏情况：有序且逆序，共比较n(n-1)/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 9P299
（二）交换排序
1. 冒泡排序
Ø思想1：从前往后两两比较，如果前者大则交换顺序，以此类推，第一趟结果找到最大值在最后。
Ø实例：用冒泡排序法将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
趟数 排序结果 结论
原序列 9 1 5 8 3 7 4 6 2 乱序
第一趟
第二趟
……P299
（二）交换排序
1. 冒泡排序 ①两两相邻的值 PK；
②n个数值，需要n-1趟
Ø将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
③无最好/坏之分，共比较 n(n-1)/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 找到第八个最大的值，放在最后P299
（二）交换排序
1. 冒泡排序
Ø思想2：从后往前两两比较，如果后者小则交换顺序，以此类推，第一趟结果找到最小值在最前。
Ø实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
第一趟排序书上无
试题巩固
（2022下·初中）学校运动会举行1分钟跳绳比赛，5个人一组，需要编写一个程序，输入小组内同
学的跳绳次数，程序自动按次数由多到少的顺序输出，如输入126、80、204、158、98，输出204、
158、126、98、80。如果用冒泡的排序算法完成此过程，需要多少轮排序才能完成？请写出上述输
入数据在第二趟排序后得到的数据结果。P300
（二）交换排序
2. 快速排序 枢纽值 PK 最远值；
Ø思想：第一趟时，第一个数为枢纽，最终找到枢纽的位置，使前面值比其小，后面值比其大
Ø实例：将序列 5、1、9、3、7、4、8、6 和 2，按升序排列。
第 一 趟 比较数 操作 执行过程
初始状态 确定枢纽值：5 5 1 9 3 7 4 8 6 2
第一次
第二次
第三次
第四次
第五次
第六次
第七次
第八次P300
（二）交换排序
2. 快速排序
① 枢纽值 PK 最远值；
②后续趟数：左右同时递归排序；
③最好：枢纽均分序列；
Ø将序列 5、1、9、3、7、4、8、6 和 2，按升序排列。
④最坏：有序，共比较 n(n-1)/2 次
后续趟数 执行过程
待排 2 1 4 3 5 7 8 6 9
第二趟
结果 1 2 4 3 5 6 7 8 9
第三趟 结果 1 2 3 4 5 6 7 8 9书上无
试题巩固
给定的整数序列（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）P302
（三）选择排序
1. 简单选择排序
Ø思想：第一趟，假设第一个数最小，然后找出后面最小的数与其互换位置。以此类推。
Ø实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
预设最小值 实际最小值 操作 排序结果
第一趟 9
第二趟
第三趟
第四趟
……P302
（三）选择排序
1. 简单选择排序 ①选择最值，与第一个值互换顺序；
②n个数值，需要n-1趟
Ø实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
③无最好/坏之分，共比较 n(n-1)/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 上· 高中）某排序程序在运行时，其每趟排序的结果如下图所示。请问此过程体现的是哪种
排序 ? 此种排序算法的基本思想是什么 ?总结下
性能总结
排序 趟数 比较次数
最好【有序·同序】：n-1
直接插入排序 n-1
最坏【有序·逆序】：n(n-1)/2
冒泡排序 n-1 n(n-1)/2
最好：log n 最好【对半分】：O(nlog n)
2 2
快速排序
最坏：n-1 最坏【有序】：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)/2P297
（一）插入排序
2. 希尔排序
核心：增量两端的值PK
Ø 思想：按增量分成多个子序列，对其排序，再缩短增量。（增量m= n/2 ，m= 𝑚/2 ，直至m=1）
Ø实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
原序列 9 1 5 8 3 7 4 6 2
第一趟P297
（一）插入排序
2. 希尔排序
核心：增量两端的值PK
Ø 思想：按增量分成多个子序列，对其排序，再缩短增量。（增量m= n/2 ，m= 𝑚/2 ，直至m=1）
Ø实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
第一趟 2 1 4 6 3 7 5 8 9
第二趟P297
（一）插入排序
2. 希尔排序
核心：增量两端的值PK
Ø 思想：按增量分成多个子序列，对其排序，再缩短增量。（增量m= n/2 ，m= 𝑚/2 ，直至m=1）
Ø实例：将序列 9、1、5、8、3、7、4、6 和 2，按升序排列。
第二趟 2 1 3 6 4 7 5 8 9
第三趟P303
（三）选择排序
2.堆排序
90 10
20
70 40
80
30 70 80 50
60 10 40 50
90 60
30 20
大顶堆 小顶堆
根节点＞左/右子树 根节点＜左/右子树P303
（三）选择排序
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，按升序排列。
20 80
70 70
80 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
最后，依次输出序列（层遍历）即可。P305
（四）归并排序
Ø思想：先分解（最终分成一个或两个数），然后再两两合并
Ø实例：将序列50、10、90、30、70、40、80、60 和 20，按升序排列第七节 程序基础P306
一、相关术语
（一）程序 – 计算机程序
Ø由人事先规定的让计算机完成某项工作的操作步骤
（二）程序设计 – 过程
Ø分析阶段 → 设计阶段 → 编码阶段 → 测试阶段 → 调试和运行阶段
（三）程序设计语言 - 计算机语言
Ø一组用来定义计算机程序的语法规则书上无
二、计算机语言
【例】完成9+8的计算。
指令序号 机器指令 汇编指令 指令功能 高级指令
10110000
1 MOV AL,9 把加数9送到累加器AL中
00001001
把累加器AL中的9与加数8做加法，
00000100
print(9+8)
2 ADD AL,8 并将结果存在累加器AL中
00001000
（即完成9+8的运算）
3 11110100 HLT 停止操作P307
二、计算机语言
1.机器语言 2.汇编语言 3.高级语言
Ø纯二进制代码 Ø出现字母和符号 Ø更接近自然语言
Ø计算机可直接识别和执行 Ø执行速度较快 Ø广泛使用：C/Python/VB等
Ø但可读性差
Ø可读性较好
Ø源程序不可直接识别，需翻译
ü 编译程序
• 将“源文件”翻译成目标程序
ü 解释程序
• 以“行”为单位，边翻译边执行P308
三、程序设计方法
（一）结构化程序设计（面向过程）
Ø以过程为中心，重在分解出清晰的步骤和流程
Ø代表性语言：Pascal语言、C语言
Ø基本思想：自顶向下、逐步求精、单入口单出口
（二）面向对象程序设计
Ø以对象为中心，重在关注对象的行为和相互作用
Ø代表性语言：C++、Java、Python、VB
Ø基本概念：对象、类、消息P309
（二）面向对象程序设计
2. 基本特征
（1）封装性
Ø将有关的代码和数据封装在一个对象中，各对象间相对独立，互不干扰
Ø尽可能地隐藏对象的内部细节
Ø对数据的访问或修改只能通过对象对外提供的接口进行
（2）继承性
Ø子类自动共享父类数据结构和方法的机制
（3）多态性
Ø不同的对象收到同一消息可以产生导致不同的行动与结果书上无
试题巩固
（ ）是一种信息隐蔽技术，它体现于类的说明，是对象的重要特性。
A. 封装
B. 继承
C. 多态
D. 对象下
节
内
容在 粉 笔
遇 见 不 一 样 的 自 己
粉笔教师教育 粉笔教师
