DSE ICT｜排序与搜寻算法备课指引（导师用）｜三种排序、线性与二分搜寻

2026-11-05

学生背得出“二分搜寻比较快”，但一问 1024 个资料最多比较几次就答错。这一堂要学生亲手数一次，把口号变成可算的数字。

本堂目标　学生能够：① 讲出泡沫、插入、选择排序的分别；② 用追踪表写出一个排序的每一轮结果；③ 算线性搜寻与二分搜寻的比较次数（1024 个资料：1024 次对 10 次）。

01　先备知识（开课前 3 分钟快检）

以下任何一项未过关，本堂就会卡住，先补该项：

技能	快检题	过关标准
阵列	阵列索引由 0 开始	最后一个索引是长度减一
循环	for 与 while 的分别	搜寻用 while 较自然
比较	大于、小于与等于	排序只靠两两比较

02　课堂流程（60 分钟）

时间	环节	导师做什么	学生做什么
0–8 分	诊断	四个数字排一次序	口头讲步骤
8–22 分	三种排序	泡沫、插入、选择	各写一轮结果
22–36 分	追踪表	每轮比较与交换	填满表格
36–48 分	两种搜寻	线性与二分	算出比较次数
48–56 分	题型训练	改错与计数题	按步骤作答
56–60 分	离场检查	三题快问	口头答案

03　讲解脚本（照着说就可以）

第一幕：第一幕：三种排序其实只差“几时交换”

泡沫排序：相邻两个比较，不对就交换，每一轮把最大值推到尾。插入排序：逐个抽出，插入前面已排序的部分。选择排序：每轮找最小值，放到前面。8 个资料，三者最坏情况都要做 28 次两两比较。
要学生做：同一组 8 个数字，用三种方法各写第一轮结果。
易错：以为选择排序的比较次数会少过泡沫排序，其实最坏情况一样。

导师做法：只要求学生写“这一轮边两个比较过”，不准写完整程式。

第二幕：第二幕：线性搜寻系唯一不需要排序的

线性搜寻逐个检查，最坏要看完 1024 个；好处是资料不需要排序，一有新资料可以直接加在尾。平均只需一半，即 512 次左右。
要学生做：讲出“边种情况一定用线性搜寻”。答案：资料经常新增、未排序。
易错：把平均数当成最坏数，答 512 次。

导师做法：要学生在 1024 个格画面试找最尾一个，数住自己揭了几多次。

第三幕：第三幕：二分搜寻每步斩一半

二分搜寻要求资料已排序。每次比较中间值，不中就丢掉一半：1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1，共 10 次。即 2 的 10 次方等于 1024，所以最坏比较次数是 log₂1024 = 10。
要学生做：自己数一次折半次数，核对答案。
带出论点：1024 次对 10 次，差距约 102 倍。

导师做法：要学生先排序才准用二分搜寻，并且问“如果资料未排序，二分搜寻会出什么事”。

04　必教题型与步骤

题型	例子	步骤
写出一轮结果	定方向→两两比较→交换→写该轮结果	只写一轮，不写全程序
追踪表	每行记录比较对象、交换与否、阵列状态	每格一个动作
计算比较次数	判断线性或二分→套公式→代入 n	二分是 log₂n 向上取整
改错题	检查资料是否已排序→检查中点计算→检查界线	每题一个错处

合理性检查（一定要教）：1024 个已排序资料，二分搜寻最坏 10 次，线性搜寻最坏 1024 次；答 11 次系错，因为最后一次比较已经找到。8 个资料的气泡排序最坏 28 次比较，三种简单排序最坏情况相同。二分搜寻的前提是资料已排序，未排序就一定错。

05　独立练习三题

题目	答案	想观察什么
二分搜寻最坏比较次数（1024 个）	10	log₂1024
线性搜寻最坏比较次数（1024 个）	1024	逐个检查
8 个资料的简单排序最坏比较次数	28	8 × 7 ÷ 2

06　学生常见错误与纠正句

错误	学生通常这样写	导师这样说
二分搜寻找 11 次	把最后一次失败比较也算进去	“最后一次比较系不系已经找到？”
未排序就用二分搜寻	直接对乱序阵列折半	“二分搜寻的前提系什么？”
混淆平均与最坏	线性搜寻答 512 次	“最坏系找边一个？”
以为选择排序比较较少	答选择排序 7 次	“每轮你比较了几多个？”

07　家课建议（直接指到练习卷题号）

排序追踪练习（校内）　第 1–4 题：三种排序各一轮
搜寻计数练习（校内）　第 5–7 题：线性与二分比较次数

08　离场检查（最后 5 分钟）

题目	答案	判定
二分搜寻 1024 个的最坏次数	10	错：重教折半
二分搜寻的前提	资料已排序	错：重教前提
三种简单排序最坏比较次数	28（8 个资料）	错：重教 n(n−1)/2

09　导师常问

为何二分搜寻要向上取整

折半到剩一个仍然要做最后一次比较，所以次数取上整。

实际程式会用哪种排序

多数语言内建排序用混合法，但考试只考三种简单排序的逻辑。

何时线性搜寻反而更好

资料量细、经常新增、未排序时，线性搜寻省掉排序成本。

立即免费找导师导师登记 →

本页为 TutorZone 导师备课指引，内容由 TutorZone 团队编写；题目与流程为原创，并非任何学校或出版社的教材。