算法设计与分析课件 24 快速排序_第1页
算法设计与分析课件 24 快速排序_第2页
算法设计与分析课件 24 快速排序_第3页
算法设计与分析课件 24 快速排序_第4页
算法设计与分析课件 24 快速排序_第5页
已阅读5页，还剩11页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

算法设计与分析本节要点CONTENTS快速排序快速排序快速排序（Quicksort）是比较快速的排序方法。快速排序由C.A.R.Hoare在1962年提出。基本思想：通过一组排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，最终使所有数据变成有序序列。快速排序快速排序基于分治策略，分为3步。（1）分解：先从原序列中取出一个元素作为基准元素。以基准元素为界，将原序列分解为两个子序列，小于或等于基准元素的子序列在基准元素左侧，大于或等于基准元素的子序列在基准元素右侧。（2）治理：对两个子序列进行快速排序。（3）合并：将排好序的两个子序列合并，得到原问题的解。快速排序如何分解是一个难题，因为如果基准元素选取不当，有可能分解成规模为0和n−1的两个子序列。例如，序列（30,24,5,58,18,36,12,42,39），第一次选取5作为基准元素，第二次选取12作为基准元素……快速排序基准元素选取有以下几种方法：• 取第一个元素。• 取最后一个元素。• 取中间位置元素。• 取第一个、最后一个、中间位置元素三者之中位数。• 取第一个和最后一个之间位置的随机数k（low≤k≤high），选R[k]做基准元素。快速排序算法步骤：（1）选取第一个元素作为基准元素，pivot=a[left]，i=left，j=right。（2）从右向左扫描，找小于或等于pivot的数，令a[i]=a[j]，i++。（3）从左向右扫描，找大于或等于pivot的数，令a[j]=a[i]，j--。（4）重复第2～3步，直到i和j重合，将pivot放到中间，即a[i]=pivot，返回mid=i。至此完成一趟排序。此时以mid为界，将原序列分解为两个子序列，左侧的子序列都小于或等于pivot，右侧的子序列都大于或等于pivot。接着分别对这两个子序列进行快速排序。快速排序对序列（30,24,5,58,18,36,12,42,39）进行快速排序。快速排序快速排序快速排序时间复杂度分析：1）分解：划分函数Partition需要扫描每个元素，每次扫描的元素个数不超过n，因此时间复杂度为O(n)。2）治理：最好情况下，每次划分将问题分解为两个n/2的子问题，递归求解两个子问题，所需时间为2T(n/2)。最坏情况下，每次划分将问题分解为0和n-1的子问题，所需时间为T(n-1)。3）合并：原地排序，合并操作不需要时间。快速排序最好情况：快速排序最坏情况：快速排序平均情况：快速排序空间复杂度分析：快速排序最好（平均）情况：时间复杂度：O(nlogn)空间复杂度：O(logn)最坏情况：时间复杂度：O(n2)空间复杂度：O(n)快速排序优化拓展为避免出现最坏情况，可以在选取基准元素

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论