5.3数据排序——冒泡排序 课件-2022-2023学年浙教版（2019）高中信息技术选修1

5.3数据排序 ——冒泡排序 1 冒泡排序 冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整，让较大的数“下沉（上冒）”，较小的数“上冒（下沉）”的一种排序技术。 算法思想 升序时：大则交换，使得从前向后比较时________下沉； 降序时：小则交换，使得从前向后比较时________下沉。 大数 小数 冒泡排序 29 36 39 38 44 36 29 39 38 44 36 39 29 38 44 36 39 38 29 44 36 39 38 44 29 ② ① ③ ④ 初始值 第1遍加工 第1遍加工： i：_____，j：_________。比较_____次，交换___次。 1 [0,n-2] d[0] d[1] d[2] d[3] d[4] d[j]与d[j+1]比较 4/n-1 4 冒泡排序 39 36 38 44 29 39 38 36 44 29 39 38 44 36 29 36 39 38 44 29 ② ① ③ 初始值 第2遍加工 第2遍加工： i：_____，j：_________。比较____次，交换____次。 2 [0,n-3] d[0] d[1] d[2] d[3] d[4] d[j]与d[j+1]比较 3 3 冒泡排序 39 38 44 36 29 39 44 38 36 29 39 38 44 36 29 ② ① 初始值 第3遍加工 第3遍加工： i：_____，j：_________。比较____次，交换____次。 3 [0,n-4] d[0] d[1] d[2] d[3] d[4] d[j]与d[j+1]比较 2 1 冒泡排序 44 39 38 36 29 ① 初始值 第4遍加工 第4遍加工： i：_____，j：_________。比较____次，交换____次。 4 [0,n-5] d[0] d[1] d[2] d[3] d[4] d[j]与d[j+1]比较 1 1 39 44 38 36 29 冒泡排序 d=[29,36,39,38,44] n=len(d) for i in range(_________):#加工遍数 for j in range(________):#每遍加工范围 if d[j]<d[j+1]:#降序排序 ___________________#交换 print(d) 确定数据加工遍数 确定每一遍加工的范围 相邻比较，逆则交换 1,n 0,n-i d[j],d[j+1]=d[j+1],d[j] 冒泡排序小结 初始值 1遍加工： 比较4次 交换4次。 2遍加工： 比较3次 交换3次。 3遍加工： 比较2次， 交换1次。 4遍加工： 比较1次， 交换1次。 有比较不一定有交换。 交换次数<=比较次数 n个数据比较次数为? n个数据交换次数为? 比较与交换 29 36 39 38 44 36 39 38 44 29 39 38 44 36 29 39 44 38 36 29 44 39 38 36 29 (n-1)+(n-2)+...+1=n*(n-1)/2 0——n*(n-1)/2 冒泡变式 d=[29,36,39,38,44] for i in range(_________):#加工遍数 for j in range(________):#每遍加工范围 if d[j]<d[j+1]:#降序排序 ___________________#交换 print(d) i表示遍数 j表示数组下标 0 1 2 3 0,n-1 0,n-i-1 d[j],d[j+1]=d[j+1],d[j] i的范围：______________j的范围：______________ 0—n-2 0—n-i-2 29 36 39 38 44 [0,n-2] [0,n-3] [0,n-4] [0,n-5] 冒泡变式 思考：若想要实现n个数据从后往前降序排序该如何改写上述代码？ d=[29,36,39,38,44] n=len(d) for i in range(_________):#加工遍数 for j in range(________):#每遍加工范围 if d[j]<d[j+1]:#降序排序 ___________________#交换 print(d) i表示遍数 j表示数组下标 1 [0,n-2]