ch10复习及习题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,10,章 内部排序,简介,:,计算机程序设计中的重要操作。约有,1/4,时间用于日常数据排序,本章介绍各类内部排序方法,。,重点：,掌握各类内部排序方法所依据的原则及典型算法，会判定何时使用何种排序方法。,难点：,内部排序及经典算法，各类算法在排序时依据的原则。,第,10,章知识结构图,内部排序,排序方法稳定性,复杂度分析,排序方法,判定方法,插入排序,交换排序,选择排序,归并排序,基数排序,简单插入,希尔排序,折半插入,起泡,快速排序,简单选择,树型选择,堆排序,各种内部排序方法的比较讨论,按,平均的时间性能,来分：,(1),时间复杂度为,O(nlog,2,n),：,快速排序、堆排序和归并排序,；,(2),时间复杂,度为,O(n,2,),：,直接插入排序、起泡排序和简单选择排序,;,(3),时间复杂度为,O(d,*n):,基数排序,(4),当待排记录按关键字有序，,直接插入排序和起泡排序,能达到,O(n,),;,而对,快速排序,是最不好的情况，时间性能,蜕化为,O(n,2,),。,(5),简单选择排序、堆排序时间性能不随记录序列关键字的分布改变,各种内部排序方法的比较讨论,按,空间性能,分,(,指排序过程中所需的辅助空间大小,),：,(1),空间复杂度是,O(1),：,直接插入、起泡、简单选择和堆排序,(2),空间复杂度是,O(log,2,n,),：,快速排序,(3),空间复杂度是,(n),：,归并排序,按,排序方法的稳定性,分：,希尔排序、快速排序、,简单选择和堆排序不稳定,。,排序方法,平均时间,最好情况,最坏情况,辅助空间,稳定性,简,单,排,序,直接插入,O(n,2,),O(n),O(n,2,),O(1),稳定,折半插入,O(n,2,),O(n),O(n,2,),O(1),稳定,起泡,O(n,2,),O(n),O(n,2,),O(1),稳定,简单选择,O(n,2,),O(n),O(n,2,),O(1),不稳定,快速排序,O(nlog,2,n),O(nlog,2,n),O（n,2,）,O(log,2,n),不稳定,堆,排序,O(nlog,2,n),O(nlog,2,n),O(nlog,2,n),O(1),不稳定,归并排序,O(nlog,2,n),O(nlog,2,n),O(nlog,2,n),O(n),稳定,应掌握的习题及类型：,一、内部排序的方法和分类,二、插入排序,(,直接、希尔排序）方法,三、,交换排序（起泡、快速排序）方法,四、选择排序（简单、堆排序）方法,五、,会求上述各种排序算法的时间,/,空间复杂度、判断稳定性。,ch10,类型题,1.,下列方法中，,_,算法的时间复杂度为,O(n,2,),。,A.,堆排序,B.,希尔排序,C.,快速排序,D.,直接插入排序,2.,下列序列中，,_,是堆。,A. 12,，,35,，,20,，,60,，,40,，,30,B. 100,，,85,，,120,，,38,，,10,，,9,，,36,C. 1,，,5,，,6,，,24,，,7,，,3,，,4 D. 38,，,24,，,15,，,20,，,30,，,46,3.,下列方法中，,_,是稳定的排序方法。,A.,堆排序,B.,希尔排序,C.,快速排序,D.,折半插入排序,4.,在待排序的元素序列基本有序的前提下，效率最高的排序方法是,_,。,A.,起泡排序,B.,快速排序,C.,堆排序,D.,直接插入排序,Ch10,复习题,5.,排序方法中，从未排序序列中挑选元素，将其依次放至已排序序列（初始为空）的一端的方法，称为,_,。,A.,希尔排序,B.,归并排序,C.,选择排序,D.,基数排序,6.,在所有排序方法中，关键字之间比较的次数与记录的初始排列次序无关的是,_,。,A.,希尔排序,B.,起泡排序,C.,简单选择排序,D.,插入排序,7.,关键字序列为,46,，,79,，,56,，,38,，,40,，,84,，利用快速排序方法，以第,1,个记录为枢轴得到的一次划分结果是,_,。,A. 38,，,40,，,46,，,56,，,79,，,84 B. 40,，,38,，,46,，,79,，,56,，,84,C. 40,，,38,，,46,，,56,，,79,，,84 D. 40,，,38,，,46,，,84,，,56,，,79,8.,在下列排序方法中，某一趟结束后未必能选出一个,元素放在其最终位置上的是,_,。,A.,堆排序,B.,起泡排序,C.,快速排序,D.,直接插入排序,9.,在下列排序方法中，在待排序的数据有序时,花费时间,反而最多的是,_,。,A.,堆排序,B.,起泡排序,C.,快速排序,D.,希尔排序,10.,对,n,个记录的序列进行堆排序，最坏情况下的时间复杂度为,_,。,A.,O(logn,) B.,O(nlogn,) C.,O(n,) D.O(n2),快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。,只有在初始数据表为逆序时，冒泡排序所执行的比较次数最多。,对一个堆按层次遍历，不一定能得到一个有序序列。,快速排序算法在待排序数据有序时最不利于发挥其长处。,快速排序算法在每趟排序结束时都能找到一个元素放到其最终位置上。,由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。,在一个大顶堆中，最小元素不一定在最后。,第,10,章作业讲评,10.1.,以关键字序列,503,，,087,，,512,，,061,，,908,，,170,，,897,，,275,，,653,，,426,为例，手工执行以下排序算法，写出每一趟排序结束时的关键字序列的状态：,（,1,）直接插入排序 （,2,）希尔排序（增量,d1=5,）,（,3,）快速排序 （,4,）堆排序,10.7.,不难看出，对长度为,n,的记录序列进行快速排序时，所需进行的比较次数依赖于这,n,个记录的初始排列。,（,1,）,n=7,时在最好情况下需进行多少次比较？说明理由。,（,2,）对,n=7,给出一个最好情况的初始排列实例。,10.7,（,1,）,n=7,时在最好情况下需进行,10,次比较,(2) n =7,的一个最好情况的初始排列实例：,4 1 3 2 6 5 7,判断以下序列是否是堆。若是，说明是小顶堆还是大顶堆，若不是，把它们调整为堆（要求记录交换次数最少）。,（,1,）（,100,，,86,，,48,，,73,，,35,，,39,，,42,，,57,，,66,，,21,）,（,2,）（,12,，,70,，,33,，,65,，,24,，,56,，,48,，,92,，,86,，,33,）,（,3,）（,103,，,97,，,56,，,38,，,66,，,23,，,42,，,12,，,30,，,52,，,6,，,20,）,（,4,）（,5,，,56,，,20,，,23,，,40,，,38,，,29,，,61,，,35,，,76,，,28,，,100,）,1,是大顶堆,2,不是堆。调整为小顶堆：（,12,，,24,，,33,，,65,，,33,，,56,，,48,，,92,，,86,，,70,）,3,是大顶堆,4,不是堆。调整为小顶堆：（,5,，,23,，,20,，,35,，,28,，,38,，,29,，,61,，,56,，,76,，,40,，,100,）,