快速排序课件.ppt
《快速排序课件.ppt》由会员分享,可在线阅读,更多相关《快速排序课件.ppt(23页珍藏版)》请在三一办公上搜索。
1、江西师范大学计算机信息工程学院 数据结构,快速排序,作者:杨劲松,内容提要,快速排序导入,快速排序思想,快速排序讲解,快速排序算法分析,练习题,退出,快速排序导入,请同学们使用冒泡排序的方法将下列数据排序:(从小到大),21 25 49 16 25 06,目录,初始状态,第一次交换结束,快速排序导入 冒泡排序过程,目录,第二次交换,第二次交换结束,快速排序导入 冒泡排序过程,目录,第三次交换结束,第二次交换结束,第四次交换结束,快速排序导入 冒泡排序过程,目录,第六次交换结束,第五次交换结束,请同学们说说,冒泡排序是如何工作的,快速排序导入,目录,对所有记录从左到右每相邻的元素进行比较 ,不符
2、合要求则交换,快速排序导入 冒泡排序分析,冒泡排序的基本做法:,思考:在数据为以下排列时,冒泡的排序效果好不好?,49 25 25 21 16 06,快速排序导入 冒泡排序分析,初始状态是反序的,则需要进行n-1趟扫描,目录,快速排序导入 冒泡排序分析,从直观上49移动到最终的位置经过了n-1次比较和交换,49 25 25 21 16 06,06 16 21 25 25 49,能不能不经过n-1次比较和交换呢?,不能?这是由于冒泡排序中需要相邻的元素两两比较、交换,目录,快速排序思想,基本思想:,1)寻找一个中心元素(通常为第一个数),2)将小于中心点的元素移动至中心点之前,大于中心点的元素移
3、动至中心点之后。,3)对上步分成的两个无序数组段重复1)、2)操作直到段长为1。,t,=t,目录,快速排序思想,以21为中心元素,划分可得:,以06、49为中心元素,划分可得:,目录,快速排序讲解,选取中心元素的问题,选取第一个数为中心元素,如何划分问题,如何重复步骤将所有数据排序,使用递归,目录,当已知中心元素的前提下,怎样将其他元素划分好?(即:大于中心点在之后,小于中心点在之前),需要解决的问题,快速排序讲解,i,0,1,2,3,4,5,i=0,i=1,j=5,j=5,j,i=1,j=3,i=1,j=4,i=2,j=3,i=2,j=2,算法终止,目录,快速排序讲解,请同学们思考,该算法有
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 快速 排序 课件
链接地址:https://www.31ppt.com/p-1344213.html