教科版 信息技术 必修 3.2 排序算法的程序实现课件（共26张ppt)

课件26张PPT。第二章　排序算法的程序实现-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-123456781.有以下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,36,78,18,15”,经过该程序段“加工”后,数组元素a(1)到a(5)的值依次为 (　　) A.36,15,18,48,78 B.36,18,15,48,78 C.15,18,36,48,78 D.15,18,48,36,78 答案解析-12-123456782.有如下程序段: bottom=6:　i=1:　r= ... ...