- 1、本文档共36页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
【例3.7】快速排序时间限制:1000ms内存限制:32MB问题描述用递归法实现快速排序算法,并将乱序数列变成升序。输入说明第一行输入数据元素的个数,第二行为待排序的数据元素,输入的数据之间空一格,最后一个回车。输出说明打印输出的时候空一格,尾数后没有空格。输入样例108536236729641195078输出样例21923364150677885963.6.2快速排序算法实现举例算法分析定义两个变量i和j为数组的下标,最开始时i=0,j=n-1,取出待排序序列中的第一个元素a[0]作为“基准”,即pivot=a[0],然后从数组的最后一个元素开始依次与pivot比较,直到找到比pivot小的元素并且交换位置,同时i++,这时从数组元素a[i]开始依次与pivot依次比较,直到找到比pivot大的元素并且交换位置,如此交替进行直到i==j。第一轮快速排序结束,得到序列是以pivot为基准,左边的元素都比pivot小,右边的元素都比pivot大的序列。以此为基础,进一步对pivot的左右两侧的子序列进行重复的操作直至整个序列保持有序。时间复杂度:最坏情况时,每?次选取的基准元素都是最?或最?的,复杂度为O(n2),最好情况时,每?次选取的基准元素都能平分整个序列,由于快排涉及到递归调?,所以时间复杂度为O(nlog2n)。平均情况下复杂度也是O(nlog2n)。空间复杂度:快速排序使?的辅助空间是O(1),?消耗空间较大的是在递归调?的时候了,因为每次递归就要保留?些数据,每?次都平分数组的情况下空间复杂度为O(logn),最差的情况下空间复杂度为O(n),快速排序是不稳定排序。3.6.3快速排序算法分析排序算法通常可以分为比较类排序和非比较类排序,冒泡排序、快速排序、插入排序、希尔排序、选择排序、堆排序、归并排序都属于比较类排序,而计数排序、基数排序和桶排序都属于非比较类排序。每一种排序算法都有特定的使用情形,一般来说,选择合适的排序算法既取决于当前输入数据的规模,也取决于当前输入数据的状态。对于基本有序且规模较小的输入列表,使用高级算法会给代码带来不必要的复杂度,而性能的提升可以忽略不计。例如,对于较小的数据集,一般不使用归并排序,冒泡排序更容易理解和实现。如果数据已经被部分排好序了,则可以使用插入排序。对于较大的数据集,归并排序算法是最好的选择。表3-1为常见排序算法的时间复杂度和空间复杂度以及稳定性情况。3.7排序算法的性能比较3.7排序算法的性能比较排序方法时间复杂度(平均)时间复杂度(最坏)时间复杂度(最好)空间复杂度稳定性冒泡排序O(n2)O(n2)O(n)O(1)稳定选择排序O(n2)O(n2)O(n2)O(1)不稳定插入排序O(n2)O(n2)O(n)O(1)稳定归并排序O(nlog2n)O(nlog2n)O(nlog2n)O(n)稳定快速排序O(nlog2n)O(n2)O(nlog2n)O(nlog2n)不稳定基数排序O(n*k)O(n*k)O(n*k)O(n+k)稳定希尔排序O(n1.3-2)O(n2)O(n)O(1)不稳定堆排序O(nlog2n)O(nlog2n)O(nlog2n)O(1)不稳定计数排序O(n+k)O(n+k)O(n+k)O(n+k)稳定桶排序O(n+k)O(n2)O(n)O(n+k)稳定表3-1常见排序算法性能情况3.8本章小结排序是算法设计中一种重要的操作,其主要功能就是对一个待排序序列进行重新排列成按照数据元素某个属性值有序的序列。实现排序的两个基本操作:(1)比较。“比较”待排序序列中两个关键字的大小;(2)移动。“移动”记录。正如本章节开始所介绍的常见的排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。每种排序算法都有自己特点和适用场景,那么如何选择一种排序算法呢?一般来说:当待排序列中元素很少的时候,适合选用插入排序;当待排序列中所有的元素几乎有序,也比较适合选用插入排序;而如果着重考虑排序算法最坏情况,适合选用堆排序;当希望排序算法的平均性能比较好时,选用快速排序比较合适;当待排序列中元素从一个密集几何中抽取出的时候,适合选用桶排序;如果期望编写的代码尽可能简练,选择插入排序比较合适3.8本章小结**排序算法排序算法排序算法算法设计实例教程教学分析目录CONCENTS第3章排序算法第1章数据结构基础第2章基
您可能关注的文档
- 算法设计实例教程 第4章 查 找.ppt
- 算法设计实例教程 第5章 字符串和高精度运算.ppt
- 算法设计实例教程 第6章 图论算法.ppt
- 算法设计实例教程 第7章 动态规划算法.ppt
- 算法设计实例教程 第8章 计算几何基础.ppt
- 算法设计实例教程 第9章 高级算法.ppt
- 算法设计实例教程 配套课件.ppt
- 黑龙江省海林市朝鲜族中学2024_2025学年高二生物下学期期中线上考试试题.doc
- 全国中考语文试题分类汇编07背诵默写.doc
- 全国通用2025版高考历史一轮总复习模块2专题7近现代中国经济的发展和社会生活的变迁第20讲近代中国民族工业的兴起和曲折发展课时跟踪人民版.doc
- 浙江省临海市白云高级中学2025届高三历史3月月考试题.doc
- 云南拾谷县第一中学2024_2025学年高二物理上学期10月月考试题.doc
- 2025版高考生物总复习第13讲基因的分离定律教案苏教版.doc
- 湖北省黄石实验高中2024_2025学年高一历史下学期期末考试模拟卷.doc
- 通史版2025版高考历史大一轮复习专题七近代化的曲折发展__中日甲午战争至五四运动前4第4讲从维新思想到新文化运动课后达标检测含解析新人教版.doc
- 2024年高考数学考试大纲解读专题04导数及其应用含解析文.doc
- 河南省许汝平九校联盟2024_2025学年高一语文上学期期末考试试题扫描版无答案.doc
- 江西省吉安市吉水县第二中学2024_2025学年高一历史上学期第二次月考试题.doc
- 北京市平谷区2025届高三政治一模考试试题含解析.doc
- 2025届中考物理第四讲物态变化专项复习测试无答案新人教版.docx
文档评论(0)