(26)--第7章 排序-归并数据结构基数.ppt

第8章排序;归并：将两个或两个以上的有序表组合成一个新有序表;将两个有序表合并成一个有序表;思考;初始关键字：[49][38][65][97][76][13][27];对n个记录进行归并排序，归并趟数的数量级是;时间效率O(nlog2n)

空间效率O（n）

稳定性稳定;前面的排序方法主要通过关键字值之间的比较和移动

而基数排序不需要关键字之间的比较

利用多关键字排序方法进行排序;对52张扑克牌按以下次序排序：

?2?3……?A?2?3……?A

?2?3……?A?2?3……?A

两个关键字：花色（????）

面值（23……A）

并且“花色”地位高于“面值”;用链表作存储结构的基数排序

每一位作为关键字。

;最高位优先MSD(MostSignificantDigitfirst)

最低位优先LSD(LeastSignificantDigitfirst);;先对最高位关键字k1排序，将序列分成若干子序列，每个子序列有相同的k1值；

然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；

依次重复，直至就每个子序列对最低位关键字kd排序，就可以得到一个有序的序列。;首先依据最低位对所有记录进行一趟排序

再依据次低位对上一趟排序结果排序

依次重复，直到最后一趟排序完成，就可以得到一个有序的序列。;例如;先决条件：

知道各级关键字的主次关系

知道各级关键字的取值范围

;过程

首先对低位关键字排序，各个记录按照此位关键字的值‘分配’到相应的序列里。

按照序列对应的值的大小，从各个序列中将记录‘收集’，收集后的序列按照此位关键字有序。

在此基础上，对下一位关键字进行排序。;278;505;008;设置10个队列，f[i]和e[i]分别头指针和尾指针

第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同

第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表

重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列;给出关键字序列{321，156，57，46，28，7，331，33，34，63}，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？;n个记录

每个记录有d位关键字

关键字取值范围rd(如十进制为10);需要2rd个队列指针，链表增加n个指针域。;（数据不是顺次后移时将导致方法不稳定）;为避免顺序存储时大量移动记录的时间开销，可考虑用链表作为存储结构

直接插入排序、归并排序、基数排序;1.平均的时间性能;2.当待排记录序列按关键字顺序有序时;指的是排序过程中所需的辅助空间大小;3.归并排序所需辅助空间最多，其空间复杂度为O(n);;1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。;3.对于不稳定的排序方法，只要能举出一个实例说明即可。;（1）分布随机，稳定性不做要求，则采用快速排序

（2）内存允许，要求排序稳定时，则采用归并排序

（3）可能会出现正序或逆序，稳定性不做要求，则采用堆排序或归并排序;（1）基本有序，则采用直接插入排序

（2）分布随机，则采用简单选择排序，若排序码不接近逆序，也可以采用直接插入排序;本章讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法。;;一般情况下，对n个关键字进行排序，可能得到的结果有n!种，由于含n!个叶子结点的二叉树的深度不小于?log2(n!)?+1,则对n个关键字进行排序的比较次数至少是?log2(n!)??nlog2n(斯蒂林近似公式)。;归并排序算法是稳定的排序方法。;将序列{2,12,16,88,5,10,34}排序。若前2趟排序的结果如下：

第1趟排序后：2,12,16,10,5,34,88

第2趟排序后：2,5,10,12,16,34,88

则可能的排序算法是：;选择一个排序算法时，除算法的时空效率外，还需要考虑的是：

I、数据的规模

II、数据的存储方式

III、算法的稳定性

IV、数据的初始状态;在基于比较的排序算法中，哪种算法的最坏情况下的时间复杂度不高于O(NlogN)？?;下面四种排序算法中，稳定的算法是？?;就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是：