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

5.3数据排序 ——选择排序 1 冒泡排序 冒泡排序是在一系列数据中对相邻两个数依次进行比较和调整,让较大的数“下沉（上冒）”,较小的数“上冒（下沉）”的一种排序技术。 算法思想 升序时：大则交换,使得从前向后比较时________下沉； 降序时：小则交换,使得从前向后比较时________下沉。 大数 小数 缺点：交换次数过于频繁,浪费效率 核心要素 加工遍数：n个数最多加工 遍就完全有序 范围及方向：范围受加工遍数和比较的两个数影响；从前往后、从后往前 升序/降序：相邻比较,逆则交换 n-1 选择排序 在排序数组的所有元素中找出最小（或最大）数据的元素,使它与第一个元素中的数据相互交换位置。然后在余下的元素中,找出最小（或最大）数据的元素与第二个元素中的数据相互交换位置。以此类推,直至排序完成。 算法思想 核心要素 加工遍数：n个数最多加工 遍就完全有序 范围：范围受加工遍数影响； 升序/降序：最小/大值交换到第一个位置 n-1 选择排序过程 初始值 1遍加工结果： j:____________ 比较____次 交换____次。 2遍加工结果： j:____________ 比较____次 交换____次。 3遍加工结果： j:____________ 比较____次 交换____次。 4遍加工结果： j:____________ 比较____次 交换____次。 29 36 39 38 44 44 36 39 38 29 44 39 36 38 29 44 39 38 36 29 44 39 38 36 29 d[j]与d[k]比较,k存储最大值索引 [1,n-1] [2,n-1] 4 1 3 1 [3,n-1] 2 1 [4,n-1] 1 0 选择排序 d=[29,36,39,38,44] n=len(d) for i in range(_________):#加工遍数 k=i-1 for j in range(________):#每遍加工范围 if d[j]>d[k]:#求最大值索引 k=j if k != i-1: ___________________#交换 print(d) i表示遍数 j表示数组下标 1 [1,n-1] 2 [2,n-1] 3 [3,n-1] 4 [4,n-1] 1,n i,n d[k],d[i-1]=d[i-1],d[k] i的范围：______________j的范围：______________ [1,n-1] [i,n-1] 课堂练习 【例1】 有6位裁判为运动员评分，给出的分数分别为49，45，61，46，58，57。采用选择排序算法对其进行排序，若完成第一遍时的结果为61，45，49，46，58，57，则完成第二遍时的结果是(　　) A.61，45，49，46，58，57 B.61，58，57，49，45，46 C.61，58，57，46，45，49 D.61，58，49，46，45，57 D 解析　从第一遍的结果可以看出排序要求是从大到小排。选择排序的基本思想是从所有的记录中选出最大(从大到小排序时)的数据，把它与第一个数据进行交换，然后在其余的记录中再选出最大的数据与第二个数据进行交换。因此第二遍排序58与45交换，得到61、58、49、46、45、57。 选择排序小结 有比较不一定有交换。 交换次数<=比较次数 n个数据比较次数为? n个数据交换次数为? 【结论】比较与交换 (n-1)+(n-2)+...+1=n*(n-1)/2 0——n-1 冒泡排序与选择排序 冒泡排序 选择排序 算法原理 一边比较,一边交换 先选出最大值或最小值的索引,再交换 核心代码 for i in range(1,n): for j in range(n-1,i-1,-1): if a[j]<a[j-1]: _________________ for i in range(1,n): k=i-1 for j in range(i,n): if a[j]<a[k]: k=j if k!=i-1: _________________ 相同点 ①n个数都需要n-1遍排序,其中变量i控制排序的遍数；②比较的次数一样多,都是___________；③最好的情况下,交换的次数一样,都是0 不同点 边比较边交换,最坏的情况下交换的次数是n*(n-1)/2 先选择再交换,最