高中信息技术浙教版选修1 算法与程序设计1数据排序专题复习课件　

排序算法专题复习 二轮复习 2023.4.17 四月份第四课时 学期第22课时 教学目标：归并排序，选择排序，插入排序，冒泡排序的基础代码格式 教学难点：冒泡排序的优化 教学难点处理方案：例题剖析+逐层递进 我们学过的排序算法： 1.冒泡排序（首考已考，最重要） 2.选择排序（首考未考，但要会看基础代码） 3.插入排序（首考未考，地方卷喜欢考） 4.归并排序（首考已考，思想重要如链表合二归一就是归并排序的变式，地方卷几乎没考过） 由于冒泡排序我们已经做过很多题，我们倒着从最不熟悉的开始4，3，2，1 lst1,lst2各自已按首位“时间”升序排序，要把lst2归并到lst1中，使得lst1整体依然升序 4.归并排序23.1首考真题再现 def merge(lst1, lst2): i = len(lst1) - 1 j = len(lst2) - 1 for t in range(len(lst2)): lst1.append([0, 0, 0]) # 为lst1追加一个元素[0, 0, 0] k = len(lst1) - 1 while j >= 0: if i >= 0 and lst1[i][0] > lst2[j][0]: lst1[k] = lst1[i] i -= 1 else: lst1[k] = lst2[j] j -= 1 k -= 1 return lst1 4.归并排序23.1首考真题再现 问：while语句中循环体的执行次数？ A 3.插入排序 3.插入排序：习题集p68T1 1.【2022年6月宁波九校高二信息技术第11题】 1．有如下python程序段，运行该程序段后，列表a中的值可能是( ) import random a = [] for i in range(6): a.append(random.randint(1,5)*2+i%2) for i in range(1,5): j = i; k = a[j] while a[j-1]<k and j>0: a[j] = a[j-1]; j=j-1 a[j] = k A．11,8,7,6,5,5 B．8,6,5,5,3,8 C．9,6,7,8,8,11 D．11,11,8,2,2,11 a=[偶，奇，偶，奇，偶，奇] 0 1 2 3 4 5 D 2.经典选择排序的代码： a = [3, 2, 5, 4, 1] # 经典选择排序 n=len(a)#找比i项小且最小的数的下标j赋值给k，然后a[i]和a[k]互换 for i in range(n-1):#i标记待排序区间左边界 k=i for j in range(i+1,n):#扫描待排序区间，找最小值下标j，给k=j，用当前数a[i]和a[k]互换 if a[j] <a[k]: k=j if k!=i:#若a[i]不是最小值则将最小值交换到下标为i的位置 a[i], a[k] = a[k], a[i] 数据变化过程如下： [3, 2, 5, 4, 1] [1, 2, 5, 4, 3] [1, 2, 3, 4, 5] 练习1. 某 Python程序段如下 : for i in range(2) : k = i for j in range( i+ 1 ,5) : if a[j] > a[k] ; k = j if i ! = k : t = a[i] ; a[i] = a[k] ; a[k] = t 数组元素 a[0] 到 a[4] 的数据依次为“10,41,75, 12,63”。则此程序运行完成后数组元素a[0] 到 a[4] 的数据依次是 ( ) A. 75, 63, 41, 12, 10 B. 10, 12, 41, 63, 75 C. 10, 12, 75, 41, 63 D