2019/10/21 Monday,#,栏目索引,教材研读重难突破,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/10/21 Monday,#,第,二,单元排序算法及程序实现,第二单元排序算法及程序实现,下表记录了6个数据的排序过程。分析表中数据可知,该排序采用的算,法与排序方式分别为,(),A.冒泡排序,降序B.选择排序,降序,C.冒泡排序,升序D.选择排序,升序,原始数据,65,57,59,44,45,69,第1遍,44,65,57,59,45,69,第2遍,44,45,65,57,59,69,第3遍,44,45,57,65,59,69,下表记录了6个数据的排序过程。分析表中数据可知,该排序采用的,2,排序是一种算法思想（对已有的一组数，经过一系列的,加工处理,后输出一组目标数）。,什么是排序（,sort,）,就是,把杂乱无章的数据变为,有序,的数据的过程。（递增或递减）。,生活和工作中对问题的处理过程更多的依赖于数据的有序性。比如说学生的成绩。,排序是一种算法思想（对已有的一组数，经过一系列的加工处理后输,3,校园歌手打分,评委,1,评委,2,评委,3,评委,4,评委,5,评委,6,9.5,9.0,9.6,9.7,9.6,9.4,校园歌手打分评委1评委2评委3评委4评委5评委69.59.0,4,评委,1,评委,2,评委,3,评委,4,评委,5,评委,6,9.5,9.0,9.6,9.7,9.6,9.4,d(1),d(2),d(3),d(4),d(5),d(6),9.0,9.4,9.5,9.6,9.6,9.7,d(1),d(2),d(3),d(4),d(5),d(6),排序,d(1)=9.5,d(2)=9.0,d(3)=9.6,d(4)=9.7,d(5)=9.6,d(6)=9.4,排序,For i=1 to 6,List1.additem,d(i),Next i,评委1评委2评委3评委4评委5评委69.59.09.69.7,5,冒泡排序,冒泡排序,6,冒泡排序是在一列数据中把较小（大）的数据逐次向上推移的一种排序技术。,冒泡排序是在一列数据中把较小（大）的数据逐次向上推移的一种排,7,（,1,）,N,个元素垂直堆放一列,（,2,）从最下面的一个元素起，自下而上比较相邻两个元素，将小的元素换到上面,（,3,）重复这一过程，直到处理完最后的两个元素,结果：第一遍加工结束，最小的元素会升到第一个元素的位置,对剩下的,n-1,个元素重复,2-3,步骤，这是第二遍加工，第二小的元素会上升到第二个元素的位置,但比较的数据会逐个减少，直至只剩下最后的两个元素的比较和交换。,基本思想：,（1）N个元素垂直堆放一列基本思想：,8,冒泡排序的过程,请观察第一、二遍共比较几次，交换几次，请问第,三,、四、五遍的结果,第一遍加工,第二遍加工,原始数据,1,2,3,4,5,1,2,3,4,A(1),40,40,40,40,40,20,20,20,20,20,A(2),30,30,30,30,20,40,40,40,40,25,A(3),70,70,70,20,30,30,30,30,25,40,A(4),25,25,20,70,70,70,70,25,30,30,A(5),20,20,25,25,25,25,25,70,70,70,A(6),55,55,55,55,55,55,55,55,55,55,冒泡排序的过程请观察第一、二遍共比较几次，交换几次，请问第三,9,浙教版高中信息技术-选修1-2,10,冒泡排序的数据比较次数,对于规模为,n,的数据进行排序，总共需进行,n-1,遍加工。,第一遍加工的比较次数为,n-1,次；,第二遍加工的比较次数为,n-2,次；,第,n-1,遍加工的比较次数为,1,次。,所以总比较次数：,n(n-1)/2,次,冒泡排序的数据比较次数对于规模为n的数据进行排序，总共需进行,11,冒泡排序的数据交换次数,当,ia(j),，就称,a(i),和,a(j),为一个,逆序对,。,数列中逆序对的对数,=,数据的交换次数,例：数列,40 30 70 25 20 55,中存在的逆序对有,数据的交换次数为,9,次。,(40,30)(40,25)(40,20),(30,25)(30,20),(70,25)(70,20)(70,55),(25,20),冒泡排序的数据交换次数当ia(j)，就称a,12,有如下一组数据：,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 159 166,无交换,有如下一组数据：27 166 85 36 73,13,冒泡排序,算法的程序实现,冒泡排序算法的程序实现,14,冒泡排序的过程,冒泡排序的过程,15,变量分析，及过程归纳,n,表示排序数据的个数；,i,表示加工处理（冒泡）的遍数；,j,表示当前访问数据的下标（相当于指针）；,处理过程,(,i),比较对象（交换）,访问数据范围,(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),，若逆序则交换,N,到,N,推出第,n-1,小的数据到,n-1,位置,变量分析，及过程归纳n表示排序数据的个数；处理过程(i)比较,16,(,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 If,Next j,Next i,从小到大排序,If语句中条件表达式为:a(j)a(j-1)。,(1)冒泡排序的代码如下:,17,冒泡排序程序的实现可用双重,FOR,循环来实现，外层,FOR,循环控制是第几遍加工，内层,FOR,循环控制进行排序的数组元素下标的变化范围。,由于每趟加工完成后，进行排序的范围会发生变化（每趟减少一个），故内层,FOR,循环变量的下界由外层循环变量决定。,冒泡排序程序的实现可用双重FOR循环来实现，外层FOR循环控,18,例1,(2012浙江3月高考,3,3分)实现某排序算法的部分VB程序如下:,For i=1 To 4,For j=5 To i+1 Step-1,If a(j)a(j-1)Then t=a(j):a(j)=a(j-1):a(j-1)=t,Next j,Next i,在经过某一遍排序“加工”后,数组元素a(1)到a(5)的数据依次为“28,7,0,53,57,30”。则下一遍排序“加工”后数组元素a(1)到a(5)的数据应该,是,(),A.28,30,70,53,57B.28,30,53,57,70,C.28,30,57,53,70D.28,30,53,70,57,浙教版高中信息技术-选修1-2,19,s=“”,For i=1 to 3,For j=7 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=s,数组元素,a(1),到,a(7),的数据一次为,3,，,9,，,1,，,5,，,8,，,6,，,2,，经过该程序段加工后，文本框,Text1,中显示的内容是（）,A,、,1 2 3 B,、,9 8 6 C,、,3 9 1 D,、,8 6 2,A,加工三遍,冒泡排序算法,s=“”A加工三遍冒泡排序算法,20,采用冒泡排序算法对数组,a,中的,5,个数据“,5,，,10,，,6,，,30,，,9,”进行排序，部分程序如下：,For i=1 to 4,For j=5 to i+1 step-1,If a(j)a(j-1)then,End if,Next j,Next I,以上程序是以,方式 排序的，框内的语句共执行了,次。,t=a(j):a(j)=a(j-1):a(j-1)=t,采用冒泡排序算法对数组a中的5个数据“5，10，6，30，9,21,冒泡算法的程序优化,For i=1 To,n-1,flag,=,0,For j=,n,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,Next i,For i=1 To n-1,For j=1 To n-i,自上而下的冒泡For i=n to 2 step-1For,24,For i=1 to 2,For j=1 to 6-i,If a(j)a(j+1)then,K=a(j):a(j)=a(j+1):a(j+1)=k,End if,Next j,Next i,数组,a(1)a(6),的值依次为,71,，,54,，,58,，,29,，,31,，,78,，则最后结束为：,A.29,，,31,，,54,，,58,，,71,，,78,B.78,，,71,，,58,，,54,，,31,，,29,C.54,，,29,，,31,，,58,，,71,，,78,D.71,，,58,，,54,，,78,，,31,，,29,For i=1 to 2,25,选择排序,选择排序,26,选择排序的基本思想：,在参加排序数组的所有元素中找出最小（或最大）数据的元素，使它与第一个元素中的数据相互交换位置。,然后在余下的元素中，找出最小（或最大）数据的元素与第二个元素中的数据相互交换位置。,以此类推，直至所有元素成为一个有序的序列。,选择排序的基本思想：,27,位置重排,Dim d,（,1 to 6,）,as integer,数组,d,d(1),d(2),d(3),d(4),d(5),D(6),98,21,16,73,43,65,16,21,98,73,43,65,16,21,98,73,43,65,16,21,43,73,98,65,16,21,43,65,98,73,16,21,43,65,73,98,选择排序,位置重排Dim d（1 to 6）as integer数组d,28,1.按日期先后整理一堆文件的算法是:第一次,在这叠文件中从上到下找,出日期最早的文件反扣在桌面上;第二次从剩余文件中从上到下找出日,期最早的文件反扣在第一次找出的文件上;第三次,从剩余文件中从上到,下找出日期最早的文件反扣在第二次找出的文件上;,依此类推,最后,完成整理工作。此算法属于,(),A.选择排序B.对分查找C.递归算法D.冒泡排序,1.按日期先后整理一堆文件的算法是:第一次,在这叠文件中从上,29,3.,经过某一遍排序“加工”后，数组元素,a(1),到,a(7),的数据依次为,“,10,，,41,，,75,，,12,，,63,，,11,，,85,”。则下一遍排序“加工”后数组元素,a(1),到,a(7),的数据依次为：,3.经过某一遍排序“加工”后，数组元素a(1)到a(7)的数,30,例3,(2010浙江6月会考,3分)某校通过政府招投标中心采购一套多媒体,教学设备,有5家单位参加竞标,竞标价分别为19万、15万、21万、13,万、12万元人民币。若采用选择排序算法