冒泡排序系列课件新.ppt

冒冒 泡泡 排排 序序荣怀学校 张丽突围赛竞演男明星投票结果突围赛竞演男明星投票结果把较小的数据逐次向前推移。如何实现将较小如何实现将较小数数逐次从下往数数逐次从下往上推移呢？上推移呢？从最后一个元素起，依次比较相邻的两个从最后一个元素起，依次比较相邻的两个 元素中的数据，将较小的数据调换到上面。元素中的数据，将较小的数据调换到上面。突围赛竞演男明星投票结果突围赛竞演男明星投票结果a（1）a（2） a（3） a（4）a（5） a（6）原始数据第一遍第二遍第三遍第四遍第五遍198138168198178138158148比较次数交换次数a(1) a(2) a(3) a(4) a(5) a(6) 冒泡冒泡趟数趟数比较结果比较结果比较次比较次数数交换次交换次数数1确定最小数 a（1）数据： 2确定较小数 a（2）数据： 3确定较小数 a（2）数据： 4确定较小数 a（2）数据： 5确定较小数 a（2）数据： 播放1381481581681785432143311138、198、168、178、148、158 138、148、198、168、178、158 138、148、158、198、168、178、138、148、158、168、198、178、138、148、158、168、178、198、a(6)a(1)a(6)a(2)a(6)a(3)a(6)a(4)a(6)a(5)6个元素，排序进行5趟，比较次数分别是 5、4、3、2、1次n-1n个元素，排序进行 趟，比较次数分别是 次，每一趟排序中从 与 开始比较n-1、n-2、n-3、 2、1 a(n)a(n-1)从大到小怎么来实现呢？例题一：下列表格中是突围赛女选手的年龄，请你利用冒泡排序将她们的年龄从小到大排列，进行两趟冒泡排序后结果是： 韩红韩红黄丽黄丽玲玲陳洁陳洁仪仪张靓张靓颖颖谭维谭维维维李佳李佳薇薇443243313327第一趟排序：27、44、32、43、31、33 第二趟排序：27、31、44、32、43、33 我们如何用我们如何用算法算法来来实现冒泡排序？实现冒泡排序？a算法的三种表示方法算法的三种表示方法自然语言计算机语言流程图比较比较a(6)与与a(5)之间的大小之间的大小（选择结构）（选择结构） YNa(6)a(5)t a(6)a(6) a(5)a(5) t交换a（6）与a（5）的值a(6)a(5)a(5)a(4)a(4)a(3)a(3)a(2)a(2)a(1)ja(j)a(j1)YNa(j)a(j1)t a(j)a(j) a(j1)a(j1) t交换a（j）与a（j1）的值If then End ifa(j)a(j-1) t=a(j)a(j)=a(j-1)a(j-1)=ta(6)a(5)a(5)a(4)a(4)a(3)a(3)a(2)a(2)a(1)ja(j)a(j1)j的取值范围 到 62第一趟排序算法实现第一趟排序算法实现 Na( j)= 2 j6Y YN循环结构循环结构t a(j)a(j) a(j-1)a(j-1) tj= j-1 For j=6 to step If then a(j)=a(j-1) a(j-1)=t End if 21a(j) a(j-1) t=a(j)Next j第1趟冒泡排序时 j 从 6 开始到2For j=6 to 2 step -1 if a(j)a(j-1) then 交换a(j) 和a(j-1)的值Next j五趟冒泡排序算法的实现 第2趟冒泡排序时 j 从 6 开始到3For j=6 to 3 step -1 if a(j)a(j-1) then 交换a(j) 和a(j-1)的值Next j第3趟冒泡排序时 j 从 6 开始到4For j=6 to 4 step -1 if a(j)a(j-1) then 交换a(j) 和a(j-1)的值Next j第4趟冒泡排序时 j 从 6 开始到5For j=6 to 5 step -1 if d(j)d(j-1) then 交换d(j) 和d(j-1)的值Next j第5趟冒泡排序时 j 从 6 开始到6For j=6 to 6 step -1 if d(j)d(j-1) then 交换d(j) 和d(j-1)的值Next j用变量i控制排序趟数6个元素，排序进行 趟 变量i的取值范围 到 变量j的取值范围 到 5156i+1 j=5Ni = i+1Yi=1交换a（j）与a（j1）的值YYNN for i= to For j= to step If then a(j)=a(j-1) End if Next jNext i外循环内内循循环环15i11a(j)a(j-1)t=a(j)a(j-1)=t6我们如何快速高效的完成我们如何快速高效的完成n个个元素的排序呢？元素的排序呢？n个元素，排序进行 趟 变量i的取值范围 到 变量j的取值范围 到 N11N1Ni+1编写编写n个元素进行冒泡排序算法实现个元素进行冒泡排序算法实现YNt=a(j)a(j)=a(j-1)a(j-1)=t a( j)=i+1 j=n J=j-1 YNYNi=1i=n-1 i =i+1 for i= to For j= to step If then a(j)=a(j-1) End if Next jNext i外循环内内循循环环1n1i11a(j) a(j-1)a（j）= a(j-1)冒泡排序的基本原理冒泡排序的基本原理: 对存放有n个原始数据的数组，按从后往前从后往前的方向依次进行两两比较两两比较，当发现相邻相邻两个数据的次序与排序要求的大小次序次序不符合不符合时，即将这两个数据进行进行互换互换。这样，较小的数据就会逐个向前移动，好象气泡向上浮起一样。数组元素之间两两比较完成我们称为冒泡一趟，直至n1趟冒泡之后，数据呈现有序排列。利用冒泡法，对下列这一组数据按升序进行排序利用冒泡法，对下列这一组数据按升序进行排序5、8、13、17、15 、23问题问题1:在排序的过程中，排序了几趟，真正只需要冒泡几趟？在排序的过程中，排序了几趟，真正只需要冒泡几趟？问题问题2：我们如何来提高冒泡排序的效率？：我们如何来提高冒泡排序的效率？思考题：谢谢！