冒泡排序及改进算法.ppt

《冒泡排序及改进算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、ISAS冒泡排序冒泡排序这个名字对于我们来说实在是过于熟悉了。作为一个编程人员，如果敢说出自己不会冒泡排序，结局肯定是会被鄙视到火星上去。许多公司到学校去招聘应届毕业生的时候，都会要求写一个冒泡排序。毫无疑问的，冒泡排序就是算法世界里面的HelloWorld。情景：观察水中的气泡往上冒的情景，气泡往上冒的时候有什么特点呢？上面的气泡比较大，而下面的气泡比较小！冒泡原理冒泡排序和气泡在水中不断往上冒的情况有些类似。气泡大的（大的数据）在上面，气泡小的（小的数据）在下面。冒泡排序的基本原理是对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当发现相邻两个数据的次序与排序要

2、求的大小次序不符合时，即将这两个数据进行互换。这样，较大的数据就会逐个向后移动，好象气泡向上浮起一样。用冒泡排序的方法将下面无序成绩排成有序{49,38,65,97,76,13,27,49}分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：“明日之星英语演讲大赛”评分出来了，需要选出每组前三名进入决赛。我们需要设计程序，对选手成绩进行排序。实例第一趟排序，一共进行了7次比较4927137697653849数据87654321序号49>38,交换位置原数据和序号序号12345678数据4938659776132749第一趟排序的步骤：序号12345678数据38496597

3、76132749序号12345678数据3849659776132749序号12345678数据3849659776132749序号12345678数据3849657697132749序号12345678数据3849657613972749序号12345678数据3849657613279749序号12345678数据3849657613274997经过第一趟排序，把最大的数97移到最后面了！49<65,保持不变65<97,保持不变97>76,交换位置97>13,交换位置97>27,交换位置97>49,交换位置经过第二趟排序，把第二大的数沉到倒数第二个位置了!97492713766549

4、38数据87654321序号38<49,保持不变第一趟排序后的数据和序号第二趟排序的步骤：序号12345678数据384965761327499749<65,保持不变65<76,保持不变76>13,交换位置76>27,交换位置76>49,交换位置序号12345678数据3849657613274997序号12345678数据3849657613274997序号12345678数据3849657613274997序号12345678数据3849651376274997序号12345678数据3849651327764997序号12345678数据384965132749769776<97,

5、保持不变序号12345678数据3849651327497697序号12345678数据3849132749657697序号12345678数据4938659776132749序号12345678数据3849657613274997序号12345678数据3813274949657697序号12345678数据1327384949657697序号12345678数据3849651327497697序号12345678数据1327384949657697序号12345678数据1327384949657697初始1趟2趟3趟4趟5趟6趟7趟算法分析//采用冒泡法对数组进行排序for(in

6、ti=1;i<8;i++)//外层循环{for(intj=0;j<8;j++)//内层循环，比较七次{if(myArray[j]>myArray[j+1]){inttemp=myArray[j];myArray[j]=myArray[j+1];myArray[j+1]=temp;}}观察原数据与第一、二趟排序后的数据序号12345678数据3849657613274997序号12345678数据3849651327497697序号12345678数据4938659776132749问：在我们刚才的比较过程中，每一趟的排序我们都进行了7次，是否每一趟的排序都需要进行7次比较呢？

7、观察原数据与第一、二趟排序后的数据序号12345678数据3849657613274997序号12345678数据3849651327497697序号12345678数据4938659776132749减少判断次数--算法改进（一）//采用冒泡法对数组进行排序for(inti=1;i<8;i++)//外层循环{for(intj=0;j<8-i;j++)//内层循环，比较7-i次{if(myArray[j]>myArray[j+