版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、试讲:快速排序目 录问题导入思想解读案例讲解123代码实现总结作业性能分析4561、问题导入:为什么会有快速排序?传统排序的缺点传统排序:冒泡排序选择排序插入排序两两比较传统排序的缺点2、核心思想:分治与递归分治思想3、案例讲解:个无序整数快速排序基本步骤递归的4个步骤1、选定Pivot中心轴2、将大于Pivot的数字放在Pivot的右边3、将小于Pivot的数字放在Pivot的左边4、分别对左右子序列重复前三步操作案例讲解3897162606093897162606093897案例讲解389716260609LR38Pivot9716260609LR0938(Pivot)0638(Pivot
2、)1638(Pivot)2609(Pivot)1609(Pivot)0616(Pivot)案例讲解1626060938973897162606093897案例讲解4、代码实现:C语言代码实现代码实现:一趟划分函数int Partition(SqList &L, int left, int right) L.rleft=l.r0; pivotkey=l.r0.key; while(left=pivotkey)-right;L.rleft=L.rright; while(leftright&L.rleft.key=pivotkey)+left; L.rright=L.rleft; while(le
3、ftright) L.rleft=pivotkey; reture left;void QSort(SqList &L,int left,int right)if(leftright) pivotloc=Partition(L,left,right); Qsort(L,left, pivotloc-1);Qsort(L,pivotloc+1,right);代码实现:快速排序函数5、性能总结:时空分析最好:划分后,左子序列和右子序列的长度相同最坏:有序,递归树成为单支树,每次划分只得到一个比上一次少一个对象的子序列,必须经过n-1趟才能把所有对象定位,而且第i趟需要经过n-i次关键码才能得到第i
4、个对象的安放位置性能总结:最好最坏场景分析可以证明,平均计算时间是O(nlog2n)。实验结果表明:就平均计算时间而言,快速排序是我们所讨论的所有内排序方法中最好的一个。快速排序是递归的,需要有一个栈存放每层递归调用时参数(新的left和right)。最大递归调用层次数与递归树的深度一致,因此,要求存储开销为O(log2n)。性能总结:时间和空间分析时间效率:O(nlog2n)空间效率:O(log2n)-递归要用到栈空间不稳定性能总结6、总结作业:课程总结与课后作业课程总结解决传统排序两两比较带来的比较负荷问题的导入分而治之与递归基本思想主要讲解了一个位无序数字序列的案例以及语言代码的实现案例与代码时间复杂度,空间复杂度,最好、最坏情形性能总结课后作业1)在快速排序方法中,进行每次划分时,是从当前待排序区间 的(_) 向(_)依次查找出处于逆序的元素并交换之,最后将 中心元素交换到一个确定位置,从而以该位置把当前区间划分为前后 2)假定一组记录的关键字为 (46,79,56,38,40,80),对其进行快速 排序的一次划分的结果为(_)。3)快速排序在(_)情况下效率
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 面最细致的聊天室策划案
- 消防控制室管理制度
- 2024年春节年货市场营销策划方案6篇
- 2024年人物专访策划书4篇(完整)-1
- 湖南省武冈市2024届高三第七次月考试卷语文试题含解析
- 广西贺州市桂梧高中2023-2024学年高考全国统考预测卷数学试卷含解析
- 供货的合同【9篇】
- 2024-2030年全球及中国钢制地板行业运营动态及投资盈利分析报告
- 安全验收过程记录表
- 部编版八年级下册全册易错知识点整合
- 儿童睡眠习惯问卷(CSHQ)
- (完整)对赌协议范本正规范本(通用版)
- 国开2023秋《人文英语3》第5-8单元作文练习参考答案
- GB/T 15231-2023玻璃纤维增强水泥性能试验方法
- 2022-2023学年浙江省温州市瑞安市人教PEP版四年级下学期6月期末英语试卷(含听力音频)
- 2024届江苏省淮安市淮阴区开明中学中考一模物理试题含解析
- 家属看守所会见申请书
- 陕西省岐山县2024届中考生物考试模拟冲刺卷含解析
- 新型农村合作医疗定点医疗机构申请表
- 国开2023秋《思想道德与法治》专题测验试题1-17参考答案
- 装备管理制度4篇
评论
0/150
提交评论