第四部分 第二单元 排序算法(教学课件)-【导与练】2022高考信息技术一轮选考总复习（浙江专用）

第二单元　排序算法 信息技术 考点与典例 考点1 冒泡排序 1.排序的含义及方式 (1)所谓排序就是将无序的数据变成有序的数据。 (2)排列方式有升序(也称递增,即从小到大排列)和降序(也称递减,即从大到小排列)两种。 信息技术 2.冒泡排序 (1)冒泡排序基本思想 将n个数据看作竖向排列的一组数据,每趟排序自下而上对每对相邻数据进行比较,若次序不符合要求则进行交换。每趟排序结束时都能使排序范围内关键字最小(或最大)的数据像一个气泡一样升到上端的对应位置,依次将关键字最小、次小……的各个数据冒到数列的第一个、第二个、……、倒数第二个位置上。 用冒泡排序对n个数据进行排序时,共需进行n-1趟(遍)排序,比较的总次数为n×(n-1)/2。 (2)冒泡排序算法的基本框架 　　For　i=1　To　n-1　 ′ n个数据进行排序,共需进行n-1趟 ′第i趟排序:从第n个数到第i个数,依次比较相邻两个数,符合条件则进行互换。 　　Next i 信息技术 (3)冒泡排序程序实现 对数组d中的n个数进行升序排序的程序为: 　For i=1 To n-1 　　′n个数排序共需进行n-1趟 　　　For j=n To i+1 Step-1　　 ′每一趟排序均从最后往前,依次比较相邻两数 　　　　　If d(j)<d(j-1) Then　　′若后面的数比前面的小,则进行互换 　　　　　　　temp=d(j)　　′变量temp是用于交换的中间变量 　　　　　　　d(j)=d(j-1) 　　　　　　　d(j-1)=temp 　　　　　End If 　　　Next j 　Next i 信息技术 重难点剖析 ①相邻两数分别用d(j)和d(j-1)来表示,第i趟排序时,j的位置变化为: n～i+1。第1趟排序时,j从n变化到2,第2趟排序时,j从n变化到3,因此可推得:第i趟排序时,j从n变化到i+1。 ②若要按降序排列,只需将程序中的语句“If d(j)<d(j-1)Then”改为“If d(j)>d(j-1)Then”即可。 信息技术 典例一 有一个数组,采用冒泡排序,第一遍排序后的结果为:4,10,5,32,6, 7,9,17,24,那么该数组的原始顺序不可能的是(　　) A.10,5,32,6,7,9,17,24,4 B.10,5,32,6,7,9,4,17,24 C.10,5,32,4,6,7,9,17,24 D.4,10,5,32,17,9,24,6,7 解析:冒泡排序默认是从后向前排序的,选项A中数据4最小,则将其依次递推至第1位,故选项A不符合题意;选项B中数据17与24顺序正确,需要将倒数第3位的数字4递推至第1位,故选项B不符合题意;选项C中后半部分的6,7,9,17,24顺序正确,需要将第4位的数字4递推至第1位,故选项C不符合题意;选项D中,经历一遍后的排序结果为4,5,10,6,32,17,9,24,7,故选项D符合题意。 答案:D 信息技术 典例二 有如下程序段: For i=1 To 2 　For j=2 To 7-i 　　　If d(j-1)>d(j) Then 　　　　t=d(j)︰d(j)=d(j-1)︰d(j-1)=t 　　　End If 　Next j Next i 数组元素d(1)到d(6)的值依次为8,5,7,1,3, 9,经过该程序段“加工”后,下列说法正确的是(　　) A.数组元素d(1)到d(6)的值依次为5, 1, 3, 7 , 8, 9 B.此过程中数据共需比较次数为8次 C.此过程中数据共需交换次数为5次 D.此过程中数据“5”共被比较5次 信息技术 解析:从程序段的结构上分析,可确定该程序段为冒泡排序,由前至后比较,并且将较大数据向后交换,执行两次排序后结果如下表, 答案:A 排序遍数 a(1) a(2) a(3) a(4) a(5) a(6) 交换次数 比较次数 1 5 7 1 3 8 9 4 5 2 5 1 3 7 8 9 2 4 其中共需比较次数为9次,共需交换次数为6次,数据“5”共被比较2次,正确答案为A。 信息技术 典例三 下列VB程序段的功能是将数组元素a(1)到a(n)按非递减序排序。 For i=1 To n-1 　For j= 　　　If a(j)>a(j+1) Then 　　　　　t=a(j)︰a(j)=a(j+1)︰a(j+1)=t 　　　End If 　　Next j Next i 方框中的代码将会是以下四句中的一句:① i To n-1　②n-1 To i Step-1　③1 To n-i　④n To i+1 Step-1 正确的选项是(　　) A.①② B.③④ C.①④ D.②③ 信息技术 解析:本题考查冒泡排序算法。如果