资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,冒 泡 排 序,经典算法之,排序,:,把杂乱无章的数据变为有序的数据的过程。,（递增或递减）,冒泡排序,:,把较小的数据逐次向上推移的一种排序技术。,如何实现将较小数逐次从下向上推移呢？,一、冒泡排序的思想,：从最下面一个元素起，依次比较相邻的两个元素中的数据，将较小的数据调换到上面,小元素像气泡一样上浮。,二、冒泡排序的过程,设置数组变量：,a (i),为牌的值（,i=1,、,2,、,3,、,4,、,5),1,2,3,4,5,数组变量,a,1,2,3,4,5,第一轮冒泡过程,a(5)a(4),保持不变,a(4)a(3),交换,a(3)a(2),交换,a(2)a(4),保持不变,a(4)a(3),交换,a(3)a(2),交换,1,2,3,4,5,第三轮冒泡过程,a(5)a(3),不变,1,2,3,4,5,第四轮冒泡过程,a(5)a(4),不变,当堂练习,1,、对“,648251”,中的,6,个数码进行两轮冒泡排序后即为某游戏中数字密码锁的密码，该密码是（ ）,A,）,684521 B,）,462518,C,）,126485 D,）,864521,C,当堂练习,2,、下表中的原始数据是一组学生的军训打靶成绩，若采用冒泡排序算法对其进行排序，则第,3,遍的排序结果是,。,原始数据,第一遍,第二遍,第三遍,第四遍,98,85,85,85,95,98,88,88,85,95,98,93,93,88,95,95,88,93,93,98,93,85,88,95,98,分析：如果要对有,5,个元素的数组进行排序，那么,1,、要进行,_,轮冒泡,2,、第一轮冒泡的时候它进行比较的范围是从,_,到,_,第,2,轮冒泡,的时候,呢？,是从,_,到,_,第,3,轮冒泡的时候呢？,是从,_,到,_,4,a(5)与a(4),a(2) 与a(1),a(5)与a(4),a(3) 与a(2),a(5)与a(4),a(4)与a(3),第,4,轮冒泡,的时候,呢？,是从,_,到,_,a(5)与a(4),a(5)与a(4),A(j)A(j-1),两数交换,Y,N,对有,5,个元素的数组进行,冒泡,排序流程图,1,开始,i1,i=?,j=j-1,N,J=i+1,流程图,2,For i= 1 to 4,Next i,For j=5 to 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,比较两个数，如果后面的数比前面的,小,，则,交换,i=1,i=2,i=3,i=4,i=1,2,i=2,3,i=3,4,i=4,5,a(,j,)a(j-1),a(,5,)a(4),a(,4,)a(3),a(,3,)a(2),a(,2,)a(1),a(,j,)a(j-1),a(,5,)a(4),a(,4,)a(3),a(,3,)a(2),a(,j,)a(j-1),a(,5,)a(4),a(,4,)a(3),a(,j,)a(j-1),a(,5,)a(4),j=5 to 2,j=5 to 3,j=5 to 4,j=5 to 5,i+1,程序实现,提高：如果要对有,n,个元素的数组进行排序，那么,要进行,_,轮冒泡，其中,外循环变量,i,从,到,变化，,内循环变量,j,从,到,变化。,n-1,1,n-1,n,i+1,a(1)、a(2)、a(3)、a(n-2)、a(n-1)、a(n),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,end if,Next j,Next i,演示已知五个数的冒泡排序,VB,程序,n-1,n,三、冒泡排序的程序实现,思考,1,：,第一个循环改为,For i=2 to n,后，,j,怎样变呢？,思考,2,：,if a(j)a(j-1),后对排序结果有何影响呢？,四、小结：,1,、冒泡排序：每次从最下面的元素开始，通过逐次往上比较，将较小的数向上推移,2,、如果有,n,个数组的元素进行排序，则要进行,n-1,趟冒泡,.,第,n-1,趟冒泡要经过,1,次比较,第一趟冒泡要经过,n-1,次比较,第二趟冒泡要经过,n-2,次比较,总计要经过,:,(,n-1)+(n-2)+(n-3)+2+1,次比较,五、复习题解,高考倒计时,P70,例,3,、,P77,第,6,题、,P80,第,14,题,
展开阅读全文