冒泡排序.ppt
- 文档编号:15058044
- 上传时间:2023-06-30
- 格式:PPT
- 页数:17
- 大小:298.50KB
冒泡排序.ppt
《冒泡排序.ppt》由会员分享,可在线阅读,更多相关《冒泡排序.ppt(17页珍藏版)》请在冰点文库上搜索。
冒泡排序,复习回顾,前面我们学习了有序插入排序方法,并利用这种方法将无序列变成有序列,它经历:
1确定数据的序号,2空出相应的位置,插入数据。
序号后的数据后移一位,下面我们来看另外一种将无序系列变成有序系列的方法,冒泡排序,所谓冒泡排序,形象的说,就是在将一组数据从小到大的顺序排列时,小的数据视为质量较轻,大的数据视为质量较重,小的数据好比水中的气泡,往上方移动,较大的数据好比是石头,往下沉,最重的会沉到底,最轻的会浮到顶,反复进行比较,直到数据列排成有序列,实例分析,请将下列数据按从小到大的顺序,利用冒泡法排序,49,38,65,97,76,13,27,49,1排序号:
2排序,现将1号数据49和2号数据38比较,因为4938所以,49和38的位置互换,变为:
第一次排序,第一步:
1号2号排序,第二步:
2号3号排序,因为4965所以这俩数的序号不变,第三步:
比较3、4号数据,方法同第二步,因为6597所以数据顺序不变,第四步:
比较4、5号数据,方法同第一步,因为9776,所以4、5号数据互换,则:
第五步:
比较5、6号数据:
方法同第二步,9713则,交换5、6号数据,则:
第六步:
比较6、7号数据,同理,上面的顺序可以变为:
同理第七步比较7、8号数据后可以变为:
这样就完成了第一次排序,它的基本特征是将最大数排到了最右边,然后再从头开始,进行第二次排序,将第二大的数据排到了倒数第二位,反复下去,就可以完成排序。
一共要进行7次才能完成。
思考,你会用冒泡法将上面的数据按从大到小的顺序排列吗?
完成所有的排序需要多少步比较?
请你设计一个数据列为R1,R2,R10,要求从小到大的顺序排列?
1.画出一次冒泡排序的算法流程图,2.画出整个冒泡排序的算法流程图,1.循环变量和初始条件:
序号i为变量,初始条件为1,2循环体:
如果RiRi+1,则交换数据的顺序,3.终止条件:
i9,基本流程如图,结束,上面的流程图在实际操作性不是很强,我们可以将它改进,很重要,整个排序流程图如图所示,说明,1.冒泡法排序完成n个数据的一次排序需要n-1次比较,完成整个排序需要(n-1)!
次比较,对于数据较多时,计算量很大。
2.有些数据的冒泡法排序可能用更少的步骤可以完成,后面的步骤可能毫无意义,但计算机必须完成。
3.交换数据时注意引入第三方变量。
课后思考,1.针对毫无意义的操作,你有什么好方法改进整个算法吗?
2.有序列插入排序和冒泡排序各有什么优缺点?
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 冒泡 排序