浙教版高中信息技术-选修1-23-排序课件.pptx

1、第二单元排序算法及程序实现下表记录了6个数据的排序过程。分析表中数据可知,该排序采用的算法与排序方式分别为()A.冒泡排序,降序B.选择排序,降序C.冒泡排序,升序D.选择排序,升序原始数据655759444569第1遍446557594569第2遍444565575969第3遍444557655969排序是一种算法思想（对已有的一组数，经过一系列的加工处理后输出一组目标数）。什么是排序（什么是排序（sortsort）就是把杂乱无章的数据变为有序的数据的过程。（递增或递减）。生活和工作中对问题的处理过程更多的依赖于数据的有序性。比如说学生的成绩。校园歌手打分评委评委1评委评委2评委评委3评委评

2、委4评委评委5评委评委69.59.09.69.79.69.4评委评委1评委评委2评委评委3评委评委4评委评委5评委评委69.59.09.69.79.69.4d(1)d(2)d(3)d(4)d(5)d(6)9.09.49.59.69.69.7d(1)d(2)d(3)d(4)d(5)d(6)排序d(1)=9.5d(2)=9.0d(3)=9.6d(4)=9.7d(5)=9.6d(6)=9.4排序For i=1 to 6List1.additem d(i)Next i冒泡排序冒泡排序是在一列数据中把较小（大）的数据逐次向上推移的一种排序技术。（1）N个元素垂直堆放一列（2）从最下面的一个元素起，自下而

3、上比较相邻两个元素，将小的元素换到上面（3）重复这一过程，直到处理完最后的两个元素 结果：第一遍加工结束，最小的元素会升到第一个元素的位置 对剩下的n-1个元素重复2-3步骤，这是第二遍加工，第二小的元素会上升到第二个元素的位置但比较的数据会逐个减少，直至只剩下最后的两个元素的比较和交换。基本思想：冒泡排序的过程冒泡排序的过程请观察第一、二遍共比较几次，交换几次，请问第三、四、五遍的结果第一遍加工第二遍加工原始数据123451234A(1)40404040402020202020A(2)30303030204040404025A(3)70707020303030302540A(4)252520

4、70707070253030A(5)20202525252525707070A(6)55555555555555555555冒泡排序的数据比较次数冒泡排序的数据比较次数l对于规模为n的数据进行排序，总共需进行n-1遍加工。l第一遍加工的比较次数为n-1次；l第二遍加工的比较次数为n-2次；ll第n-1遍加工的比较次数为1次。l所以总比较次数：n(n-1)/2次冒泡排序的数据交换次数冒泡排序的数据交换次数当ia(j)，就称a(i)和a(j)为一个逆序对。数列中逆序对的对数=数据的交换次数例：数列40 30 70 25 20 55中存在的逆序对有数据的交换次数为9次。(40,30)(40,25)(

5、40,20)(30,25)(30,20)(70,25)(70,20)(70,55)(25,20)l有如下一组数据：27 166 85 36 73 127 159，利用冒泡排序进行从小到大排序，需要交换的次数是 A、5 B、6 C、7 D、8第一遍：27 36 166 85 73 127 159 交换两次第二遍：27 36 73 166 85 127 159 交换两次第三遍：27 36 73 85 166 127 159 交换一次第四遍：27 36 73 85 127 166 159 交换一次第五遍：27 36 73 85 127 159 166 交换一次第六遍：27 36 73 85 127

6、159 166 无交换冒泡排序冒泡排序算法的程序实现算法的程序实现冒泡排序的过程冒泡排序的过程n n表示排序数据的个数；表示排序数据的个数；i i表示加工处理（冒泡）的遍数；表示加工处理（冒泡）的遍数；j j表示当前访问数据的下标（相当于指针）；表示当前访问数据的下标（相当于指针）；处理过程处理过程(i i)比较对象比较对象（交换）（交换）访问数据范围访问数据范围(j(j）处理成效处理成效第1遍(i=1)d(j)与d(j-1)，若逆序则交换N 到 2（i+1）推出最小的数据到1号位置第i遍d(j)与d(j-1)，若逆序则交换N 到 i+1推出第i小的数据到i位置第n-1遍d(j)与d(j-1)

7、，若逆序则交换N到 N推出第n-1小的数据到n-1位置(1)冒泡排序的代码如下:For i=1 To n-1 n个数需要n-1次排序For j=n To i+1 Step-1 从后往前,两两比较,一直到第i+1个数If a(j)a(j-1)Then 比较相邻的两个数temp=a(j-1):a(j-1)=a(j):a(j)=temp 小的在后面,则交换End IfNext j Next i从小到大排序,If语句中条件表达式为:a(j)a(j-1)。冒泡排序程序的实现可用双重FOR循环来实现，外层FOR循环控制是第几遍加工，内层FOR循环控制进行排序的数组元素下标的变化范围。由于每趟加工完成后，进

8、行排序的范围会发生变化（每趟减少一个），故内层FOR循环变量的下界由外层循环变量决定。例例1 (2012浙江3月高考,3,3分)实现某排序算法的部分VB程序如下:For i=1 To 4For j=5 To i+1 Step-1If a(j)a(j-1)Then t=a(j):a(j)=a(j-1):a(j-1)=t Next jNext i在经过某一遍排序“加工”后,数组元素a(1)到a(5)的数据依次为“28,70,53,57,30”。则下一遍排序“加工”后数组元素a(1)到a(5)的数据应该是()A.28,30,70,53,57B.28,30,53,57,70C.28,30,57,53,

9、70D.28,30,53,70,57ls=“”lFor i=1 to 3l For j=7 to i+1 step-1l If a(j)a(j-1)thenl k=a(j):a(j)=a(j-1):a(j-1)=kl end ifl next jls=s+str(a(i)lNext IlText1.text=s l数组元素a(1)到a(7)的数据一次为3，9，1，5，8，6，2，经过该程序段加工后，文本框Text1中显示的内容是（）lA、1 2 3 B、9 8 6 C、3 9 1 D、8 6 2 A加工三遍冒泡排序算法采用冒泡排序算法对数组a中的5个数据“5，10，6，30，9”进行排序，部分

10、程序如下：For i=1 to 4For j=5 to i+1 step-1If a(j)a(j-1)thenEnd if Next jNext I以上程序是以 方式 排序的，框内的语句共执行了 次。t=a(j):a(j)=a(j-1):a(j-1)=t冒泡算法的程序优化冒泡算法的程序优化lFor i=1 To n-1lflag=0l For j=n To i+1 Step-1l If a(j)a(j+1)then K=a(j):a(j)=a(j+1):a(j+1)=kEnd if Next jNext iFor i=1 To n-1For j=1 To n-iFor i=1 to 2For

11、j=1 to 6-iIf a(j)a(j+1)thenK=a(j):a(j)=a(j+1):a(j+1)=kEnd if Next jNext i数组a(1)a(6)的值依次为71，54，58，29，31，78，则最后结束为：A.29，31，54，58，71，78B.78，71，58，54，31，29C.54，29，31，58，71，78D.71，58，54，78，31，29选择排序选择排序的基本思想：在参加排序数组的所有元素中找出最小（或最大）数据的元素，使它与第一个元素中的数据相互交换位置。然后在余下的元素中，找出最小（或最大）数据的元素与第二个元素中的数据相互交换位置。以此类推，直至所有

12、元素成为一个有序的序列。位置重排位置重排 数组dd(1)d(2)d(3)d(4)d(5)D(6)982116734365162198734365162198734365162143739865162143659873162143657398选选择择排排序序1.按日期先后整理一堆文件的算法是:第一次,在这叠文件中从上到下找出日期最早的文件反扣在桌面上;第二次从剩余文件中从上到下找出日期最早的文件反扣在第一次找出的文件上;第三次,从剩余文件中从上到下找出日期最早的文件反扣在第二次找出的文件上;,依此类推,最后完成整理工作。此算法属于()A.选择排序B.对分查找C.递归算法D.冒泡排序3.经过某一遍

13、排序“加工”后，数组元素a(1)到a(7)的数据依次为“10，41，75，12，63，11，85”。则下一遍排序“加工”后数组元素a(1)到a(7)的数据依次为：例例3 (2010浙江6月会考,3分)某校通过政府招投标中心采购一套多媒体教学设备,有5家单位参加竞标,竞标价分别为19万、15万、21万、13万、12万元人民币。若采用选择排序算法对标价从大到小排序,需要进行数据互换的次数是()A.1B.2C.3D.4(2011浙江6月会考,3分)用选择排序法对一组学生的身高数据进行升序排序,已知第一遍排序结束后的数据序列为165,168,178,175,171,则下列选项中可能是原始数据序列的是(

14、)A.175,178,168,165,171B.178,168,165,175,171C.165,178,168,175,171D.165,168,171,175,178选择排序的程序实现怎么找到最小数？第一遍第一遍 i=1（k=1）j从从2到到6若若d(j)d(k),则让则让k=j第二遍第二遍 i=2（k=2）j从从3到到6若若d(j)d(k),则让则让k=j第三遍第三遍 i=3（k=3）j从从4到到6若若d(j)d(k),则让则让k=j第四遍第四遍 i=4（k=4）j从从5到到6若若d(j)d(k),则让则让k=j第五遍第五遍 i=5（k=5）j从从6到到6若若d(j)d(k),则让则让k

15、=j第第i遍遍 （k=i）j从从i+1到到6若若d(j)d(k),则让则让k=j数组dd(1)d(2)d(3)d(4)d(5)D(6)982116734365选择排序的代码如下:For i=1 To n-1k=iFor j=i+1 To nIf a(j)a(k)Then k=j Next jIf ki Thentemp=a(i):a(i)=a(k):a(k)=tempEnd IfNext i说明:虚线框内代码用于寻找数组元素a(i)到a(n)的最小值,变量k记录当前找到的最小值的位置,即数组元素的下标,则a(k)就是当前找到的最小的数组元素。它的思想方法是先假设数组的第i项是最小的(第i遍排序

16、),因此k记为i,然后把从第i+1项开始的所有数组元素跟a(k)进行比较,如果比a(k)小,则用k记录该元素的下标。这样循环结束后,变量k中存储的就是数组中从第i项至第n项的最小元素的下标,a(k)就是第i项至第n项中的最小元素。从小到大排序时,If语句中条件表达式为:a(j)a(k)。(2012浙江3月高考,9,2分)对数组元素a(1)到a(8)进行升序排序,其排序算法的VB部分程序段如下:For m=1 To 7p=mFor n=m+1 To 8Next nIf pm Then t=a(p):a(p)=a(m):a(m)=tNext m方框中的语句是()A.If a(n)a(p)Then

17、p=mB.If a(n)a(p)Then p=nD.If a(n)a(p)Then p=mi=1Do while i=n-1k=iJ=k+1Do while j=nIf a(k)a(j)then k=jj=j+1LoopIf k i then T=a(k):a(k)=a(i):a(i)=tEnd if i=i+1LoopFor I=1 to nList2.additem str(a(i)Next IDim a(1 to 100)as integer,I,j,t,k as integerConst n=100Private sub command1_click()i=0Do while in-1

18、i=i+1k=iJ=k+1Do while j=nIf a(k)a(j)then k=jk=k+1LoopIf k i then T=a(k):a(k)=a(i):a(i)=tEnd if LoopFor i=1 to nList2.additem str(a(i)Next iEnd sub下划线的代码有错误怎么找到最小数？数组dd(1)d(2)d(3)d(4)d(5)D(6)982116734365程序实现(从后向前，升序)第一遍第一遍 i=n（k=n）j从从n-1到到1若若d(j)d(k),则让则让k=j第二遍第二遍 i=n-1（k=n-1）j从从n-2到到1若若d(j)d(k),则让则让

19、k=j第三遍第三遍 i=n-2（k=n-2）j从从n-3到到1若若d(j)d(k),则让则让k=j第四遍第四遍 i=n-3（k=n-3）j从从n-4到到1若若d(j)d(k),则让则让k=j第第n-1遍遍 i=2（k=2）j从从1到到1若若d(j)d(k),则让则让k=j第第i遍遍 （k=n+1-i）j从从i-1到到1若若d(j)d(k),则让则让k=jFor i=n to 2 step-1K=iFor j=i-1 to 1 step-1If d(k)d(j)then k=jNext jIf ki thenTemp=d(i)D(i)=d(k)D(k)=tempEnd if Next iN个排序

20、共进行n-1趟排序第i位置交换时，首先用k记录K位置上的数依次与j位置上的数进行比较若找到比k位置上更小的数，则更新k的值若i位置上的数不是最小数，则和k位置上的数进行互换选择排序的比较次数和交换次数N个数进行选择排序第一遍进行n-1次比较第二遍进行n-2次比较第i遍进行n-i次比较第n-1遍进行1次比较总比较次数(n-1)+(n-2)+1 =n*(n-1)/2交换次数最多的交换次数为n-1总结：比较次数选择排序 (n-1)+(n-2)+1 =n*(n-1)/2冒泡排序 (n-1)+(n-2)+1 =n*(n-1)/2交换次数（最多）选择排序 n-1冒泡排序 (n-1)+(n-2)+1 =n*(n-1)/2