快速排序课件.ppt

上传人:小飞机 文档编号:1344213 上传时间:2022-11-11 格式:PPT 页数:23 大小:2.17MB
返回 下载 相关 举报
快速排序课件.ppt_第1页
第1页 / 共23页
快速排序课件.ppt_第2页
第2页 / 共23页
快速排序课件.ppt_第3页
第3页 / 共23页
快速排序课件.ppt_第4页
第4页 / 共23页
快速排序课件.ppt_第5页
第5页 / 共23页
点击查看更多>>
资源描述

《快速排序课件.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,算法终止,目录,快速排序讲解,请同学们思考,该算法有

4、没有可以改进的地方,目录,快速排序讲解,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,算法终止,通过动画,可以看出每次中心元素都要交换。根据划分的思想最后位置一定是中心元素,可以申请一个变量保存中心元素,以避免交换,目录,快速排序讲解,i=left;j=right;int temp=aleft;do/从右向左找第1个不小于中心元素的位置jwhile( aj temp ,left,right用于限定要排序数列的范围,temp即为中心元素,程序填空,当前元素小于中心元素结束循环时,应当在中心元素的左边,移至左边,目录

5、,快速排序讲解,/从左向右找第1个不大于中心元素的位置iwhile(aitemp /将中心元素t填入最终位置,程序填空,目录,快速排序讲解,函数头:quicksort(int a,int left,int right),初始化:i=left;j=right;int temp=aleft;,划分:do一次划分 while(ij);,中心元素填入:ai=temp;,递归地对剩余段作快速排序,quicksort(a,left,i-1);quicksort(a,i+1,right);,目录,快速排序完整代码,void quicksort(int a,int left,int right)int i,j

6、;if(lefttemp ,目录,while(aitemp ,快速排序完整代码,目录,算法分析,思考:当数据有序的情况下,快速排序的效率如何?,快速排序的最坏时间复杂度为O(n2),06 16 21 25 25 49,例,快速排序的最好时间复杂度为O(nlog2n),快速排序的平均时间复杂度为O(nlog2n),快速排序是不稳定的排序方法,目录,练习题,1)在快速排序方法中,进行每次划分时,是从当前待排序区间 的_ 向_依次查找出处于逆序的元素并交换之,最后将 中心元素交换到一个确定位置,从而以该位置把当前区间划分为前后,两端,中间,2)假定一组记录的关键字为 (46,79,56,38,40,80),对其进行快速 排序的一次划分的结果为_。,38 40 46 56 79 84,3)快速排序在_情况下效率最低,在_情况下最易发挥其长处。,排序对象已经按其关键字从小到大排好,每次划分对象定位后,左侧子序列与右 侧子序列长度相同,4)快速排序在平均情况下的时间复杂度为_ ,在最坏 情况下的时间复杂度为_。,O(nlog2n),O(n2),目录,

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号