专题23 数据排序课件-2025-2026学年高考信息技术总复习

该高中信息技术高考复习课件聚焦“数据排序”专题，覆盖排序概念、冒泡/插入/选择/桶排序等核心考点，对接计算思维水平3（理解算法思想）和4（构建模型解决问题）要求。通过考点诊断（判断正误）、算法效率分析（如n(n-1)/2次比较）、Python实现代码归纳常考题型，结合浙江选考等真题案例，精准对接高考评价体系。 课件亮点在于“考点拆解+真题精析+代码优化”策略，如冒泡排序标志位优化、选择排序真题（例8机器加工产品问题）解析，培养计算思维（算法设计、问题分解）和数字化学习与创新（Python编程实现）素养。提供易错点分析（交换次数计算）和答题模板（排序算法代码框架），助力学生掌握得分技巧，教师可据此精准教学，提升复习效率。

专题 23 数据排序 1 知识梳理 归纳提升 题型考法 考点1 排序 1.排序的概念 排序就是整理数据的序列，使其中元素按照某个值的递增（或递减）的次序重新排列的操作。在排序过程中，数据元素的值保持不变。 2.数组中的排序 （1）将数据依次存放在一组地址连续的存储单元中，排序过程是对数据 本身进行____________，通过关键字之间的比较判断，将数据移到 合适的位置。 （2）如果对一个数组进行升序排序，那么排序结束后，最小的数据一定 存储在 _________中，最大的数据一定存储在 d[-1]中；同理，若是 降序排序，则最小的数据一定存储在 ________中，最大的数据一 定存储在 d[0]中。 物理重排 d[0] d[-1]　 知识梳理 归纳提升 题型考法 3.链表中的排序 排序过程中无须移动数据，仅____________即可。 4.Python 中的排序函数 （1）sort 方法：只适用于列表，将直接对原列表进行排序，不会产生 新的列表；参数 reverse 默认为 False 时实现升序排序，reverse=Tr ue 时实现降序排序。 （2）sorted函数：将排好序的数据返回为一个新的序列，而原序列依然 存在；参数reverse默认为False时实现升序排序，reverse=True时实 现降序排序。 修改指针　 知识梳理 归纳提升 题型考法 考点2 冒泡排序 1.冒泡排序的算法思想 （1）冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整， 让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排 序技术。 （2）冒泡排序从数据序列的一端开始，如若从左端开始，则每个数据 元素都与其右边一个元素进行两两比较并交换__________，使每 一对比较的数据的排列顺序符合要求的升序（降序）。 　逆序对　 知识梳理 归纳提升 题型考法 2.冒泡排序的实现过程图示 （1）举例：对数组 a=[9,7,2,6,11,3]进行升序排序。 知识梳理 归纳提升 题型考法 （2）如图所示为一轮冒泡，一轮冒泡排序结束后，数组元素 a[5]的值 最大，无须再进行排序，则下一轮冒泡在 a[0]~a[4]中进行 ，第三 轮在a[0]~a[3]中 进 行 ，以 此 类 推 ，直 至 冒 泡 范 围为 0。 3.冒泡排序的算法效率 对于包含 n个元素的数组，用冒泡排序算法进行排序时，共需比较 ___________（次），其时间复杂度为 O(n2)。 　n(n-1)/2　 知识梳理 归纳提升 题型考法 考点3 插入排序 1.插入排序的算法思想 将新数据插入到已经排好顺序的有序表中，使插入之后的数据序列依旧有序。首先在有序表中查找到新数据应该插入的位置，然后将新数据插入到___________中。 　有序表　 知识梳理 归纳提升 题型考法 2.插入排序的实现过程图示（以升序为例） 知识梳理 归纳提升 题型考法 3.插入排序的算法效率 对于包含 n 个元素的数组，用插入排序算法进行排序时，需要用到双层循环来实现，外层循环遍历每个新数据，时间复杂度为 O(n)，内层循环查找新数据的插入位置，时间复杂度为O(n)，故总的算法时间复杂度为 O(n2)。 知识梳理 归纳提升 题型考法 考点4 选择排序 1.选择排序的算法思想 首先在未排序序列中找到最小（大）元素，交换到排序序列的___________，然后从剩余未排序元素中继续寻找最小（大）元素，交换到序列第二个位置，以此类推，直到完成序列的排序。 　　起始位置 知识梳理 归纳提升 题型考法 2.选择排序的实现过程图示（以升序为例） 知识梳理 归纳提升 题型考法 3.选择排序的算法效率 对于包含 n个元素的数组，用选择排序算法进行排序时，共需比较 n(n-1)/2（次），其时间复杂度为 O(n2)。 知识梳理 归纳提升 题型考法 考点 5 桶排序 1. 桶排序的算法思想：若待排序序列的元素均为 非 负 整 数 ，且 最 大 值 为 m，则 分 配 m+1 个桶，每个桶的编号（下标）就等于待排序元素的值，每个桶的元素值就是存入桶中的待排序元素个数。 2.桶排序的过程 （1）根据待排序序列中最大元素值，确定申请的桶的个数，并将桶全部清空。 （2）统计待排序序列中每个值为 i 的元素出现的次数，存入编号为 i的桶。 （3）依次把数据从桶里倒出来，存储到原序列中，获得一个已排序序列。 知识梳理 归纳提升 题型考法 （3）桶排序的实现过程图示。 （4）一般来说，桶的算法思想主要有三种功能：桶计数功能；桶排序 功能；验证数据是否存在。 知识梳理 归纳提升 题型考法 判断正误，正确的画“√”，错误的画“×”。 1. 冒泡排序中，每一轮排序都会将当前未排序序列的最大值（或最小值）移动到固定位置。（　　） 2. 对 5 个数字按从低到高进行冒泡排序，第一遍加工后的结果为 165，172，177，168，180，则排序前这 5 个数字不可能是 172，165，177，168，180。 （　　） 3. 数组 a 的初始值为[6,4,3,8,7,5]，使用冒泡排序进行降序排序，则排序过程中总的交换次数是 9。 （　　） 4. 在冒泡排序时引入标志位 flag，若某一轮未发生交换，则提前终止排序，可以减少不必要的比较轮次，提升效率。 （　　） 5. 选择排序在排序过程中，每次交换操作都会改变两个元素的位置，且交换次数等于排序轮次。 （　　） 　　√ 　　√ 　　× 　　√ 　　× 知识梳理 归纳提升 题型考法 （1）冒泡排序的 4 种变式。 基础聚焦 题点考法 方法归纳 （2）冒泡排序的 2 种优化。 优化思路：在某一轮加工过程中没有数据交换时，说明数据已经有序，排序可以提前结束， 以提高代码效率。 ①优化 1：引入变量 flag 来检测是否产生数据交换，代码如下（以升序为例）。 def bubble_1(a): n=len(a) i=1 flag=True while i<n and flag: flag=False for j in range(0,n-i): if a[j]>a[j+1]: a[j],a[j+1]=a[j+1],a[j] flag=True i+=1 return a 基础聚焦 题点考法 方法归纳 ②优化 2：记下每轮最后一次数据交换的位置，代码如下（以升序为例）。 def bubble_2(a): n=len(a) i=1 while i<n: start=n for j in range(n-1,i-1,-1): if a[j]<a[j-1]: a[j],a[j-1]=a[j-1],a[j] start=j i=start+1 return a 基础聚焦 题点考法 方法归纳 插入排序的代码实现（以升序为例）。 def insertion_sort(arr): for i in range(1,len(arr)): key=arr[i] j=i-1 while j>=0 and key<arr[j]: arr[j+1]=arr[j] j-=1 arr[j+1]=key return arr 基础聚焦 题点考法 方法归纳 （1）选择排序的代码实现（以升序为例）。 def select_sort(a): n=len(a) for i in range(n-1): Min=i #最小值下标初始设定为序列中第一个位置 for j in range(i+1,n): #遍历剩余序列 if a[Min]>a[j]: #找出最小值 Min=j #存储最小值下标到变量 Min if Min!=i: #判断是否需要交换 a[Min],a[i]=a[i],a[Min] return a 基础聚焦 题点考法 方法归纳 （2）选择排序算法采用双重 for 循环来实现，外层循环用来控制排序轮次（或待排区 间左边界），内层循环用来查找待排序列中最小值的位置。在每一轮排序结束 后，都要把最小值交换到待排序区间最左端。 （3）程序表示的是对数组 a进行升序排序，若是降序排序，则需要找到数组中的最大 值存储到序列前面。 基础聚焦 题点考法 方法归纳 （1）快速排序。 ①快速排序的实现分为两部分：一是以基准数为分隔，将比基准数小的数排列 到基准数左边，则基准数右边都是比它大的数；二是采用递归的思想实现整 个序列的分割。 基础聚焦 题点考法 方法归纳 ②代码实现（以升序为例）。 #以基准数分割序列的函数 def cut(arr,low,high): #arr[]：排序数组；low：起始索引；high：结束索引 base=arr[low] #选取 arr[low]作为基准数 i,j=low,high while i<j: while i<j and arr[j]>=base: j-=1 #j左移，找到比 base 小的元素 while i<j and arr[i]<=base: i+=1 #i右移，找到比 base 大的元素 if i<j: #交换二者 arr[i],arr[j]=arr[j],arr[i] arr[i],arr[low]=arr[low],arr[i] #将基准数放回序列 return i #返回基准数的位置 #快速排序函数 def quickSort(arr,low,high): if low<high: pi=cut(arr,low,high) quickSort(arr,low,pi-1) quickSort(arr,pi+1,high) return arr 基础聚焦 题点考法 方法归纳 （2）桶排序。 ①桶的数量：0~max(a)个桶，理想情况下每个数据装一个桶，且这些桶按顺序 排列。 ②遍历数组 a，将 a 中的每个数组元素存储到它的专属“桶”中，进行桶内排序。 ③所有元素存储完毕之后，按桶的排列顺序逐个取出非空的桶中的数据，则取 出的数据顺序就是有序排列的。 基础聚焦 题点考法 方法归纳 ④代码实现（以升序为例）。 def bucketSort(a): #选择一个序列中最大的数 max_num=max(a) #创建一个元素全是 0 的列表作为空桶 bucket=[0]*(max_num+1) #把所有元素放入桶中，即是将对应元素个数加 1 for i in a: bucket[i]+=1 #存储排序好的元素 sort_a=[] #取出桶中的元素 for j in range(len(bucket)): if bucket[j]!=0: for x in range(bucket[j]): sort_a.append(j) return sort_a 基础聚焦 题点考法 方法归纳 考向 一 冒泡排序算法 例 1 采用冒泡排序算法对某数据序列进行排序，若经过第一轮排序后的结果是 2，8，3，9，5，6，7，则原数据序列不可能是 （　　） A.8，3，9，5，2，7，6 B.8，3，9，2，6，5，7 C.8，2，9，3，5，7，6 D.8，3，2，9，6，5，7 D 例 1 D 由第一轮排序结果可知，最小值 2 处于最前面的位置，所以此冒泡排序算法是将最小值上冒的升序排序。选项 D 经过一轮排序后的结果为 2，8，3，5，9，6，7。 √ 知识梳理 归纳提升 题型考法 例 2 ［2023浙江选考］列表 s包含 8个互不相等的元素，即 s[0]，s[1]，s[2]，…，s[7]，有如下 Python程序段： n=8 for i in range(1,n-1): for j in range(1,n-i-1): if s[j]>s[j-1]: s[j],s[j-1]=s[j-1],s[j] 该程序段实现的是 （　　） A.s[0]到 s[5]的降序排列 B.s[1]到 s[6]的降序排列 C.s[1]到 s[7]的升序排列 D.s[2]到 s[6]的升序排列 A 例 2 A 外循环变量 i的取值范围是 1～6，当 i为 1时，内循环变量 j的取值范围是 1～5，由于参与比较的两元素下标分别是 j和 j-1，故列表中仅元素 s[0]～s[5]从前往后进行比较排序，由 s[j]>s[j-1]可知，当后一个数大于前一个数时要发生交换，故最终排序结果是降序。 √ 知识梳理 归纳提升 题型考法 例 3 ［2025强基联盟］有如下 Python程序段： d=[27,78,25,36,5] flag=True i=0 while i<=3 and flag : #① flag=False for j in range(len(d)-1,i,-1): if d[j]>d[j-1]: d[j],d[j-1]=d[j-1],d[j] #② flag=True i+=1 print(d) 执行该程序段后，下列说法不正确的是 （　　） A.输出 d 的值为[78,36,27,25,5] B. 方框①处语句改为“i<=2 and flag”后，输出的结果不变 C.方框②处语句的执行次数是 9 D.最终 i的值为 3 C 例 3 C　该程序段对列表 d 中的元素从右往左进行比较，若 d[j]大于 d[j-1]，则交换这 2 个元素，即将较大值冒泡到左边，且 flag 的值置为 True。若一轮内循环结束后没有发生数据交换，则表明序列 d 已有序，此时结束排序，输出序列 d。方框②处语句实现交换元素，交换的次数与逆序对有关，序列 d 中一共有 3 个逆序对，故方框②处语句的执行次数为 3。 √ 知识梳理 归纳提升 题型考法 例 4 ［2025湖丽衢模拟］某算法的部分流程图如图所示，若数组 a 初始值依次为 5，3，2，4，7，则执行这部分流程后，输出 a 的值是 （　　） A.2，3，4，5，7 B.7，5，4，3，2 C.2，5，7，4，3 D.7，4，3，5，2 B 例 4 B　由流程图可知，外层循环控制冒泡排序轮数，一共执行 n-1 轮，内层循环从后往前比较相邻元素，将较大数交换至最前端，实现数组 a 的降序排列。故执行这部分流程后，输出数组 a 的值是 7，5，4，3，2。 √ 知识梳理 归纳提升 题型考法 考向 二 插入排序算法 例 5 ［2025浙江选考］数组元素 a[0]~a[n-1]已按升序排列，现要将 a[pos]（0≤pos≤n-1）的值加 1，并保持数组的有序性不变，实现该功能的程序段如下，方框中应填入的正确代码为 （　　） t=a[pos]+1 i=pos while 　　　　　　　 : a[i]=a[i+1] i+=1 a[i]=t A.i<n-1 B.i<n-1 and t>a[i+1] C.i<n-1 and a[i]>a[i+1] D.i<=n-1 or t>a[i] B √ 例5 B 初始变量 t为 a[pos]的值加 1（并没有改变 a[pos]的值），变量 i从pos 位置开始遍历数组元素，若 t 大于它后面的数 a[i+1]，则将 a[i+1]的值向前移动一位，直到 a[i+1]大于或等于 t，最后将 a[i]赋值为 t。由于比较的对象是 t和 a[i+1]，因此 i的值不能超过 n-2，即 i<n-1。 知识梳理 归纳提升 题型考法 例 6 ［2025七彩阳光联盟］有如下 Python程序段： a=[11,4,2,13,6,5,3,6,19,1] for i in range(1,len(a)): key=a[i] j=i while 　　　（1）　　　: a[j]=a[j-1] j-=1 　　　（2） 划线处有如下可选代码： ①j>0 and key<a[j-1] ②j>=0 and key<a[j-1] ③a[j]=key ④a[j-1]=key 为使得数组 a 实现升序排序，则划线处应填入的正确代码为 （　　） A.①③ B.①④ C.②③ D.②④ A 例 6 A　本题中插入排序的思路为将第 i 个元素插入至已有序的范围[0,i]中，故需将 a[i]的元素和下标范围为[0,i-1]的元素进行比较，程序中 a[i]的值存入 key 中，下标范围为[0,i-1]的元素采用 j-1 来进行枚举，所以 j 的取值最多只能取到 1，当 j的值为 0 时，不再继续执行，故（1）处填入代码为 j>0 and key<a[j-1]，key 应该插入在 a[j-1]的后一个位置，故（2）处填入代码为 a[j]=key。 √ 知识梳理 归纳提升 题型考法 考向 三 选择排序算法 例 7 有如下 Python 程序段： from random import randint x=randint(2,4)*2 a=[9,2,5,1,3,4,8,7] n=len(a) for i in range(0,n-1): k=i for j in range(i+1,x): if a[k]>a[j]: k=j if i!=k: a[k],a[i]=a[i],a[k] print(a) 执行该程序段后，输出的结果不可能是 （　　） A.[1,2,3,4,5,7,8,9] B.[1,2,3,4,5,9,8,7] C.[1,2,5,9,3,4,8,7] D.[1,2,3,4,5,9,7,8] D 例 7 D　该程序段实现的是选择排序算法，随机数 x 的取值为 4、6、8，所以内循环查找数据时范围有限。当 x=4时，只对 a[0]～a[3]的元素进行升序排序，得到 a 的值为[1,2,5,9,3,4,8,7]。当 x=6 时，只对 a[0]～a[5]的元素进行升序排序，得到 a 的值为[1,2,3,4,5,9,8,7]。当 x=8 时，对所有元素进行升序排序，得到 a 的值为[1,2,3,4,5,7,8,9]。 √ 知识梳理 归纳提升 题型考法 例 8 ［2025浙江联考］某机器在上午 8 点到 12 点可以安排加工产品。按如下规则选择部分产品进行加工：首先选择所有产品中加工结束时间最早的产品（若有多个产品的结束时间相同，则优先选择加工时长少的产品），然后在剩余产品中选择时间不冲突的结束时间最早的产品进行加工，以此类推，直至选择完毕。 编写 Python 程序，实现如下功能：读取 n 个产品的编号、预计到达时间和所需加工时长，输出选择加工的产品编号、加工起始时间和结束时间。请回答下列问题： （1）有 6 个产品的产品编号、预计到达时间和所需加工时长（分钟）为[[1,"08:00",105],[2,"08:30",60], [3, "09: 35", 105], [4, "10: 30", 90], [5, "10: 00",35],[6,"09:40",40]]，则选择加工的第 2 个产品的编号为　　　　　　　（填数字）号。 6 知识梳理 归纳提升 题型考法 （2）实现上述功能的 Python 程序如下，请在划线处填入合适的代码。 def convert1(t): '''把时间格式 t 转换为整数，如"08:30"转换为 510。代码略''' def convert2(t): '''把整数 t 转换为时间格式，如 510 转换为"08:30"。代码略''' '''读取 n 个产品的数据存入列表 a[0]至 a[n-1]中，a[i]包含 3 个数据项，a[i][0]、a[i][1]和 a[i][2]分别存放产品编号、预计到达时间和所需时长。代码略''' for i in range(n): st=convert1(a[i][1]) a[i].append(st) ed=st+a[i][2] a[i].append(ed) flag=[False]*n 知识梳理 归纳提升 题型考法 for i in range(n-1): 　　　①　　　 for j in range(i+1,n): if a[j] [4] <a[k] [4] or a[j] [4] ==a[k] [4] and a[j][2]<a[k][2]: k=j a[i],a[k]=a[k],a[i] st=convert1("08:00") ed=convert1("12:00") for i in range(n): if a[i][3]>=st and a[i][4]<=ed: flag[i]=True 　　　②　　　 print("产品编号","起始时间","结束时间") for i in range(n): if 　　　③　　　: print(a[i][0],a[i][1],convert2(a[i][4])) k=i st=a[i][4] flag[i] 或　flag[i]==True 知识梳理 归纳提升 题型考法 例 8 （1）6 （2）①k=i ②st=a[i][4]　或其他等价答案　 ③flag[i]　或　flag[i]==True （1）先选择所有产品中加工结束时间最早的产品，则选择的第 1 个产品是[2,"08:30",60]，结束时间是 09:30；剩余 产 品 中 时 间 不 冲 突 的 有 [3,"09:35",105]，[4,"10:30",90]，[5,"10:00",35]，[6,"09: 40",40]，其中加工结束时间最早的产品是[6,"09:40",40]，结束时间是 10:20；剩余产品中时间不冲突的为[4,"10:30",90]，结束时间为 12:00。因此选择加工的产品编号依次是 2、6、4。 （2）①根据选择 排序算法的特点，应初始化比较索引为当前索引，故填入代码为 k=i。②要选择不冲突的产品进行加工，需更新起始时间为当前选择产品的结束时间，故填入代码为st=a[i][4]。③flag 为 True 表示已选择了该产品，故填入代码为 flag[i]或 flag[i]==True。 知识梳理 归纳提升 题型考法 考向 四 其他排序算法 例 9 有如下 Python 程序段： a=[4,8,6,9,4,5,2,3] m,n=max(a)+1,len(a) b=[0]*m for i in range(n): k=int(a[i]) b[k]=b[k]+1 for i in range(m): for j in range(1,b[i]+1): print(i,end=" ") 执行该程序段后，输出的结果是 （　　） A.9 8 6 5 4 4 3 2 B.2 3 4 4 5 6 8 9 C.2 4 5 8 9 6 4 3 D.9 6 4 3 2 4 5 8 B 例 9 B 该程序使用了桶排序的算法思想，数组 b 相当于桶，数组 a 的值对应数组 b 中的下标，经过桶排序之后，数组 a 实现升序排序。 √ 知识梳理 归纳提升 题型考法 例 10 ［2024浙江选考］有如下 Python 程序段： for i in range(0,len(a)-1,2): if i>0 and a[i]<a[i-1]: a[i],a[i-1]=a[i-1],a[i] if a[i]<a[i+1]: a[i],a[i+1]=a[i+1],a[i] 列表 a有 6个元素，运行该程序段后，a可能的值是（　　） A.[2,9,8,6,9,3] B.[9,9,8,6,3,2] C.[9,3,6,2,8,9] D.[6,3,9,2,9,8] D 例 10 D　根据代码可知，当 i 的值为 0 时，a[i]的值比 a[i+1]的值大（或相等）；当 i 的值为 2、4 时，a[i]的值比 a[i-1]和 a[i+1]的值都要大（或相等）。选项 A 中 a[0]比 a[1]小，故不可能。选项 B 中 a[2]比 a[1]小，故不可能。选项 C 中a[4]比 a[5]小，故不可能。 √ 知识梳理 归纳提升 题型考法 例 11 使用快速排序算法对序列 arr 进行排序的Python 程序段如下： def quS(arr,left,right): if left>right: return temp=arr[left] i,j=left,right while i!=j: while arr[j]>=temp and i<j: j-=1 while arr[i]<=temp and 　　　①　　　: i+=1 if i<j: 　　　②　　　 arr[left]=arr[i];arr[i]=temp quS(arr,left,i-1) quS(　　　③　　　) return arr arr=[10,7,8,8,2,19,3] n=len(arr) print(quS(arr,0,n-1)) i<j arr[i],arr[j]=arr[j],arr[i] arr,i+1,right 知识梳理 归纳提升 题型考法 请回答下列问题： （1）执行该程序段，输出的结果是　　　 　　　。 （2）请在划线处填入合适的代码。 [2,3,7,8,8,10,19] 例 11 （1）[2,3,7,8,8,10,19] （2）①i<j ②arr[i],arr[j]=arr[j],arr[i] ③arr,i+1,right （1）该程序对序列 arr进行升序排序，故执行该程序段后，输出的结果是[2,3,7,8,8,10,19]。 （2）①快速排序中，左右指针在序列中的移动必须在没重合之前进行，所以此处应填写的条件与上一个右指针 j 的 while 循环一样，故填入代码为 i<j，即左指针小于右指针，表示两个指针还未重合。②前两个 while 循环结束后，得到的指针 j 所指的元素小于基准数，指针 i 所指的元素大于基准数，若此时 i 的索引值依然小于 j，则根据快速排序的规则，需要交换 i 和 j 所指的元素，故填入代码为 arr[i],arr[j]=arr[j],arr[i]。③程序运行到此处时，arr[i]是基准数，arr[i]左边的数均小于 arr[i]，右边的数均大于 arr[i]，但是两边的数都是乱序的，所以要对两边的数据区域继续进行快速排序，调用函数 quS，数据范围是 arr，右半部分的左指针移动范围是 i+1～right，故填入代码为 arr,i+1,right。 知识梳理 归纳提升 题型考法 THANK YOU $$