综合比较解读课件

,单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第9章 内部排序,9.1 排序的基本概念,9.2 插入类排序,9.3 交换类排序法,9.4 选择类排序法,9.5 归并排序,9.6 分配类排序,9.7 各种排序方法的综合比较,9.8 总结与提高,9.7 各种排序方法的综合比较,首先从算法的平均时间复杂度、最坏时间复杂度、以及算法所需的辅助存储空间三方面，对各种排序方法加以比较。,排序方法,平均时间复杂度,最坏时间复杂度,辅助存储空间,简单排序,O(n,2,),O(n,2,),O(1),快速排序,O(nlogn),O(n,2,),O(logn),堆排序,O(nlogn),O(nlogn),O(1),归并排序,O(nlogn),O(nlogn),O(n),各种排序方法的性能比较,通过分析和比较，可以得出以下结论：,简单排序一般只用于,n,值较小的情况；,归并排序适用于,n,值较大的情况；,快速排序是排序方法中最好的方法。,从排序的稳定性来看，基数排序是稳定的，除了简单选择排序，其它各种简单排序法也是稳定的。多数情况下，排序是按记录的主关键字进行的，此时不用考虑排序方法的稳定性。如果排序是按记录的次关键字进行的，则应充分考虑排序方法的稳定性。,9.8 总结与提高,9.8.1 主要知识点,1.,本章共介绍了插入、交换、选择、归并、分配这,5,类内排序算法，均为基于比较的排序，即排序过程的实现主要靠关键字的关系大小比较。理解各类排序的基本方法非常重要。,2.熟练掌握三种简单排序方法（直接插入、冒泡排序、简单选择）的基本思想和算法描述,掌握这些排序法的特点和适用情况，并能应用分析。,3.掌握三种改进排序方法（希尔排序、快速排序、堆排序）的基本思路,掌握这些排序法的特点和适用情况，并能根据特点给出应用分析。,4.理解归并排序法的基本思想和算法描述。,5.掌握基数排序法基本思想和两种实现途径。,6.证明一种排序方法是稳定的，要从算法本身的步骤中加以证明。证明排序方法是不稳定的，只需给出一个反例说明。,9.8.2 典型题例,例1：排序方法选择,设有10000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？,解：待排序元素1万，仅需找出前10个最小元素，因此并不需要整个排序；在所给定的方法中，调用堆排序中的一趟排序，即可通过最小堆找出一个最小值，每趟排序只需仅需10次调用一趟排序，即可达到要求结果。而其他的归并排序、基数排序、快速排序、插入排序方法均要全部排好才可达到要求,因此选择堆排序最好。,对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。分析其最坏与最好情况，对n=7给出一个最好情况的初始排列实例。,解：快速排序算法是平均排序性能最好的算法之一。,快速排序最坏情况是序列有序，每次以枢轴元素为界，序列分为两个子表，一个子表为空，另一个子表为n-1个元素，快速排序蜕变为冒泡排序。,快速排序最好情况是这样的排列，每次的枢轴元素放置的位置在表中间，正好能够将序列分为两个长度相当的子表，此时快速排序性能类同折半判定树的分析。其趟数为log,2,n,+1。,对长度为n的记录序列进行快速排序时，所需进行的比较次数依赖于这n个元素的初始排列。分析其最坏与最好情况，对n=7给出一个最好情况的初始排列实例。,n=7时一个最好情况的初始排列实例为：4，1，3，2，6，5，7,第一趟划分结果为：2，1，3 4 6，5，7,第二趟划分结果为：1，2，3 4 5，6，7,最终的排序结果为：1，2，3，4，5，6，7,