2020版信息技术新优化浙江大一轮（课件+优选习题）：第三部分 第二章　排序算法的程序实现 (共2份打包)

第二章　排序算法的程序实现 -2- -3- 考点1 考点2 冒泡排序 冒泡排序的基本思想是把待排序的n个元素看成垂直堆放的一列数据,从最下面的一个元素起,自下而上地比较相邻的两个元素的数据,将较小的数据换到上面的一个元素中。重复这一过程,直到处理完最后两个数,称为第一遍加工。当第一遍加工完成后,最小(大)的数已经上升到第一个元素的位置。然后对余下的n-1个数重复上述过程,经过n-1遍处理以达到排序目的的一种排序方法。冒泡排序最多需要比较和交换的次数是 条目梳理 -4- 考点1 考点2 常用的冒泡排序程序结构: 升序方式冒泡排序的程序段 For i = 1 To n - 1 　For j = n To i + 1 Step -1 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 提示在降序方式中,If语句中条件表达式为a(j)>a(j-1)。 条目梳理 -5- 考点1 考点2 【例1】有如下VB程序段: s=″　″ For i = 1 To 3 For j = 6 To i + 1 Step -1 　　If a(j) > a(j-1) Then 　　　 k=a(j):a(j)=a(j-1):a(j-1)=k 　　End If Next j s = s + str(a(i)) Next i Text1.Text=str(s) 数组元素从a(1)到a(6)的数据依次为“3、7、2、5、8、9”,经过该程序“加工”后,文本框Text1中显示的是(　　) A.2　3　5 B.9　8　7 C.3　7　2 D.7　3　2 条目梳理 -6- 考点1 考点2 答案:B 解析:观察程序可知,内循环中每次都是对相邻的数据进行比较,把较大数交换到上面,所以该算法属于升序型冒泡排序。外循环3遍,表明排序3遍。可用列表方式模拟冒泡排序的过程。 其次,每一遍排序完之后都将对应的a(i)以字符串的形式加入到字符串变量s中,每加一次在两个数之间都会产生一个空格,最终s的结果是:9　8　7。 条目梳理 -7- 考点1 考点2 选择排序 选择排序算法的基本思想是在待排序的数据中选出最小(大)的数据,把它与第1个位置的数据交换,然后在其余的数据中再选出最小(大)的数据与第2个数据交换,依此类推,直到所有的数据排序完成。选择排序最多需要比较的次数是 最多需要交换的次数是n-1。 常用的选择排序程序结构: 条目梳理 -8- 考点1 考点2 升序方式选择排序的程序段 For i = 1 To n-1 　k=i 　For j =i+1 To n If a(j) < a(k) Then k=j 　Next j If　k<>i then t = a(i): a(i) = a(k): a(k) = t End If Next i 提示在降序方式中,If语句中表达式为a(j)>a(k)。 条目梳理 -9- 考点1 考点2 【例2】 某学校举行校园歌手比赛,数组a存放歌手的得分,数组mc存放名次。名次计算规则为:分值最高为第1名,分值相同则名次相同。VB程序段的部分代码如下: For i=1 To n-1 k=i For j=i+1 To n If 　①　 Then k=j  Next j If k<>i then t=a(k):a(k)=a(i):a(i)=t If i=1 then mc(1)=1　'数组元素mc(i)存放i号歌手的名次 Else If a(i)<>a(i-1) Then 　②　 Else 　③　  End if Next i 条目梳理 -10- 考点1 考点2 答案:①a(j)>a(k)　②mc(i)=i　③mc(i)=mc(i)-1 解析:代码段采用了选择排序算法。根据题意,分值最高为第1名,并由语句mc(1)=1可知,a(1)应是最高分,说明应是对数组降序排序,故①处填a(j)>a(k)。在第i遍排序完成后,该遍中最大数已存入a(i)中,然后计算a(i)的名次。如果i=1,即最高分者为第1名,所以mc(1)=1;否则如果a(i)<>a(i-1),那么第i位歌手的名次是mc(i)=i,如果a(i)=a(i-1),表示当前歌手的得分和前一位相同,则其名次也应与前者相同,即mc(i)=mc(i)-1。 条目梳理 -11- 1 2 3 4 5 6 7 8 1.有以下VB程序段 For i = 1 To 2 　For j = 1 To 5-i If d(j) > d(j +1)Then 　t = d(j):d(j) = d(j +1):d(j +1) = t End If 　Next j Next i 数组元素a(1)到a(5)的值依次为“48