数据结构(牛小飞)4排序比较和习题.ppt
总结和习题,习题课,各种排序方法的比较,本章的主要内部排序方法,本章的主要内部排序方法,本章研究的内部排序方法主要有：,1.插入排序,1)基本思想：,插入排序：将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。,本章的主要排序方法,2)常见的插入排序算法,a.直接插入排序（基于顺序查找）,b.希尔排序（基于逐趟缩小增量）,O(n2),是一种稳定的排序方法,是一种不稳定的排序方法,本章的主要排序方法,2.交换类排序,1)基本思想：,依次两两比较相邻关键字，并交换不满足排序要求的关键字，直至全部有序。,本章的主要排序方法,2)常见的交换类排序算法,a.起泡排序,b.快速排序,O(n2),是一种稳定的排序方法,是一种不稳定的排序方法,O(nlogn),本章的主要排序方法,3.选择类排序,1)基本思想：,每一趟从待排序的n-i+1（i=1,2,3,n-1）个记录中选出关键字最小的记录，作为有序序列中第i个记录，直到全部记录排序完毕。,本章的主要内部排序方法,2)常见的选择类排序算法,O(n2),是一种不稳定的排序方法,是一种不稳定的排序方法,O(nlogn),a.简单选择排序,b.堆选择排序,本章的主要内部排序方法,4.归并排序,1)基本思想：,将两个或两个以上的有序子序列“归并”为一个有序序列。,时间复杂度为(nlogn)。,是一种稳定的排序方法,本章的主要内部排序方法,各种内部排序方法的比较,5.链式基数排序,1)基本思想：,在多关键字的记录序列中，每个关键字的取值范围相同，则按LSD法进行排序时，可以采用“分配-收集”的方法，不需要进行关键字间的比较。,时间复杂度为O(d(n+rd),是稳定的排序方法,各种内部排序方法的比较,1.平均的时间性能,基数排序,时间复杂度为 O(nlogn)：,快速排序、堆排序和归并排序,时间复杂度为 O(n2)：,直接插入排序、起泡排序和简单选择排序,时间复杂度为 O(d(n+rd):,一、时间性能,各种内部排序方法的比较,2.当待排记录序列按关键字顺序有序时,直接插入排序和起泡排序能达到O(n)的时间复杂度快速排序的时间性能蜕化为O(n2)。,3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。,各种内部排序方法的比较,二、空间性能,指的是排序过程中所需的辅助空间大小,1.所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；,2.快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；,各种内部排序方法的比较,3.归并排序所需辅助空间最多，其空间复杂度为 O(n);,4.链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。,各种内部排序方法的比较,三、排序方法的稳定性能,1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。,排序之前:Ri(K)Rj(K),排序之后:Ri(K)Rj(K),各种内部排序方法的比较,2.当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。,3.对于不稳定的排序方法，只要能举出一个实例说明即可。,4.快速排序、堆排序和希尔排序是不稳定的排序方法。,例如:对 4,3,4,2 进行快速排序，得到 2,3,4,4,各种内部排序方法的比较,四、关于“排序方法的时间复杂度的下限”,本章讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法。,可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn)。(基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制。),各种内部排序方法的比较,例如:对三个关键字进行排序的判定树如下：,K1K3,K1K2,K1K3,K2K3,K2 K3,K2K1K3,K1K2K3,K3K2K1,K2K3K1,K3K1K2,K1K3K2,树上的每一次“比较”都是必要的;,树上的叶子结点包含所有可能情况。,各种内部排序方法的比较,一般情况下，对n个关键字进行排序，可能得到的结果有n!种，由于含n!个叶子结点的二叉树的深度不小于log2(n!)+1,则对 n 个关键字进行排序的比较次数至少是 log2(n!)nlog2n(斯蒂林近似公式)。,所以，基于“比较关键字”进行排序的排序方法，可能达到的最快的时间复杂度为 O(nlogn)。,1、在待排序的元素序列基本有序的前提下，效率最高的排序方法是（）A 插入排序 B选择排序 C 快速排序 D 归并排序 2、在所有的排序方法中，关键字比较的次数与记录的初始排序次序无关的是（）A 起泡排序 B 希尔排序 C 插入排序 D 选择排序,【答案】A,【答案】D,习题课,3、排序方法中，从未排序队列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，然后放入到已排序序列中的正确位置上，这种方法称为（）A 起泡排序 B 选择排序 C 插入排序 D 堆排序 4、下列排序方法中，（）是从未排序序列中依次挑选元素，并将其放入已排序序列（初始为空）的末尾。A 希尔排序 B 归并排序 C 选择排序 D 插入排序,【答案】C,【答案】C,习题课,5、对n个记录进行堆排序，最坏情况下的执行时间为 A)O(log2n)B)O(n)C)O(nlog2n)D)O(n2)6、用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是 A）94、32、40、90、80、46、21、69 B）32、40、21、46、69、94、90、80 C）21、32、46、40、80、69、90、94 D）90、69、80、46、21、32、94、40,【答案】C,【答案】C,习题课,7、用快速排序法对包含n个关键字的序列进行排序，最坏情况下 的执行时间为 A）O(log2n)B）O(n)C）O(nlog2n)D）O(n2),【答案】D,习题课,8、下列哪一个关键码序列不符合堆的定义？A）A、C、D、G、H、M、P、Q、R、X B）A、C、M、D、H、P、X、G、O、R C）A、D、P、R、C、Q、X、M、H、G D）A、D、C、M、P、G、H、X、R、Q,【答案】C,9、已知一个序列为21，39，35，12，17，43，则利用堆 排序的方法建立的初始堆为（）A 39，21，35，12，17，43 B 43，39，35，12，17，21 C 43，39，35，21，17，12 D 43，35，39，17，21，12,【答案】B,习题课,10、一组记录的关键字为46，79，50，38，42，80，利用快速 排序的方法，以第一个记录为基准得到的一次划分结果为 A 38，42，46，50，79，80 B 42，38，46，79，50，80 C 42，38，46，79，80，50 D 42，38，46，80，50，76,【答案】C,11、用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则所采用的排序方法是（）A选择排序 B 快速排序 C 归并排序 D 希尔排序 12、在插入排序、希尔排序、选择排序、堆排序、快速排序、归并排序中，排序稳定的有。,【答案】B,插入排序、归并排序,习题课,13、已知如下代码:FOR i=2 TO n DO x=Ai;j=i-1;WHILE(j0)AND(Ajx)DO Aj+1:=Aj;j:=j-1 Aj+1=x 1、这段代码所描述的排序方法是_。2、这段代码所描述的排序方法的时间复杂度为_。3、假设这段代码开始执行时,数组A中的元素已经按值的递增 次序排好了序,则这段代码的执行时间为_。,直接插入排序,O(n2),O(n),习题课,14、设有n个无序元素，按非递减次序排序，但只想得到前面长度为k的部分序列，其中nk，最好采用什么排序方法？为什么？如果有这样的一个序列59，11，26，34，17，91，25，得到的部分序列是11，17，25，对于该例使用所选择的方法实现时，共执行多少次比较？,习题课,15、给出如下关键字序列321，156，57，46，28，7，331，33，34，63，请按链式基数排序方法，列出一趟分配和收集的过程。,16、给定一个关键字序列24，19，32，43，38，6，13，22，请写出快速排序第一趟的结果；堆排序时所建的初始堆；归并排序的全过程。,习题课,17、设有一个数组中存放了一个无序的关键字序列K1,K2,Kn。现要求将Kn放在将元素排序后的正确的位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。,
