《(26)--第7章 排序-归并数据结构基数.ppt》由会员分享，可在线阅读，更多相关《(26)--第7章 排序-归并数据结构基数.ppt（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第8章 排序归并、基数类排序归并：将两个或两个以上的有序表组合成一个新有序表2-路归并排序排序过程初始序列看成n个有序子序列，每个子序列长度为1两两合并，得到n/2个长度为2或1的有序子序列再两两合并，重复直至得到一个长度为n的有序序列为止8.5归并排序将两个有序表合并成一个有序表0 1 2 3 44913659776780AB 0 1 2 3 4 5 6 7 Cijk7jjjB表的元素都已移入C表，只需将A表的剩余部分移入C表即可iiikkkkkk134965768097思考设有序表A表长度为m，B表长度为n合并成一个有序表最多比较多少次？最少比较多少次？初始关键字：49 38 65 97
2、76 13 27一趟归并后：38 49 65 97 13 76 27二趟归并后：38 49 65 97 13 27 76三趟归并后：13 27 38 49 65 76 97归并排序的排序过程对n个记录进行归并排序，归并趟数的数量级是O(logn)O(n)O(nlogn)O(n2)ABCD提交单选题2分时间效率O(nlog2n)空间效率O（n）稳定性稳定排序性能前面的排序方法主要通过关键字值之间的比较和移动而基数排序不需要关键字之间的比较利用多关键字排序方法进行排序基数排序对52张扑克牌按以下次序排序：23A23A23A23A两个关键字：花色（）面值（23A）并且“花色”地位高于“面值”多关键字
3、排序例如：十进制数比较可以看作是一个多关键字排序十进制数比较可以看作是一个多关键字排序用链表作存储结构的基数排序每一位作为关键字。链式基数排序先从低位开始排序还是从高位开始？u最高位优先MSD(Most Significant Digit first)u最低位优先LSD(Least Significant Digit first)多关键字排序先对最高位关键字k1排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序，就可以得到一个有序的序列。最高位优先首先依据最低位对所有记录进
4、行一趟排序再依据次低位对上一趟排序结果排序依次重复，直到最后一趟排序完成，就可以得到一个有序的序列。这种方法这种方法不需要再分组，而是所有记录都而是所有记录都参加排参加排序序最低位优先例如初始序列按个位排序按十位排序按百位排序需不需要稳定呢？先决条件先决条件：知道各级关键字的主次关系知道各级关键字的取值范围利用利用“分配分配”和和“收集收集”对关键字进行对关键字进行排序排序链式基数排序过程首先对低位关键字排序，各个记录按照此位关键字的值分配到相应的序列里。按照序列对应的值的大小，从各个序列中将记录收集，收集后的序列按照此位关键字有序。在此基础上，对下一位关键字进行排序。链式基数排序278109
5、063930589184505269008083109589269278063930083184505008e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9一一趟趟分分配配930063083184505278008109589269一趟收集：505008109930063269278083184589二趟收集083184589063505269930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9二趟分配008109278930063083184505278008109589269一趟收集008063083109184269278
6、505589930三趟收集：109008184930e0e1e2e3e4e5e6e7e8e9f0f1f2f3f4f5f6f7f8f9三三趟趟分分配配063083269278505589505008109930063269278083184589二趟收集设置10个队列，fi和ei分别头指针和尾指针第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到
7、一个有序序列链式基数排序步骤给出关键字序列321，156，57，46，28，7，331，33，34，63，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？3313213363341564657728574628733346315632133115628321331333446576373213313363341564657728ABCD提交单选题2分n个记录每个记录有d位关键字关键字取值范围rd(如十进制为10)排序性能分析n n重复执行重复执行d d趟趟“分配分配”与与“收集收集”n n每每趟趟对对n n个个记记录录进进行行“分分配配”，对对rdrd个个队队列列进进
8、行行“收集收集”时间效率：O(d(n+rd)n需要2rd个队列指针，链表增加n个指针域。空间复杂度：O(n+rd)稳定性：稳定排序性能分析（数据不是顺次后移时将导致方法不稳定）总结为避免顺序存储时大量移动记录的时间开销，可考虑用链表作为存储结构直接插入排序、归并排序、基数排序不宜采用链表作为存储结构的折半插入排序、希尔排序、快速排序、堆排序使用的存储结构1.平均的时间性能时间复杂度为 O(nlogn)：快速排序、堆排序和归并排序时间复杂度为 O(n2)：直接插入排序、起泡排序和简单选择排序时间性能2.当待排记录序列按关键字顺序有序时3.简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键
9、字的分布而改变。直接插入排序和起泡排序能达到O(n)的时间复杂度，快速排序的时间性能蜕化为O(n2)。指的是排序过程中所需的辅助空间大小1.所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；2.快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；空间性能3.归并排序所需辅助空间最多，其空间复杂度为 O(n);4.链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。1.稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。2.当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序
10、方法。排序之前:Ri(K)Rj(K)排序之后:Ri(K)Rj(K)排序方法的稳定性能 3.对于不稳定的排序方法，只要能举出一个实例说明即可。4.快速排序、堆排序和希尔排序是不稳定的排序方法。例如:对4,3,4,2进行快速排序，得到2,3,4,4（1）分布随机，稳定性不做要求，则采用快速排序（2）内存允许，要求排序稳定时，则采用归并排序（3）可能会出现正序或逆序，稳定性不做要求，则采用堆排序或归并排序n较大时排序算法选择规则（1）基本有序，则采用直接插入排序（2）分布随机，则采用简单选择排序，若排序码不接近逆序，也可以采用直接插入排序n较小时排序算法选择规则 本章讨论的各种排序方法，除基数排序外
11、，其它方法都是基于“比较关键字”进行排序的排序方法。可以证明，这类排序法可能达到的最快的时间复杂度为O(nlogn)。(基数排序不是基于“比较关键字”的排序方法，所以它不受这个限制。)关于“排序方法的时间复杂度的下限”K1K3K1K2K1K3K2K3K2 K3K2K1K3K1K2K3K3K2K1K2K3K1K3K1K2K1K3K2树上的每一次“比较”都是必要的;树上的叶子结点包含所有可能情况。对三个关键字进行排序的判定树 一般情况下，对n个关键字进行排序，可能得到的结果有n!种，由于含n!个叶子结点的二叉树的深度不小于log2(n!)+1,则对 n 个关键字进行排序的比较次数至少是 log2(
12、n!)nlog2n(斯蒂林近似公式)。所以，基于“比较关键字”进行排序的排序方法，可能达到的最快的时间复杂度为 O(nlogn)。归并排序算法是稳定的排序方法。正确错误AB提交单选题1分将序列2,12,16,88,5,10,34排序。若前2趟排序的结果如下：第1趟排序后：2,12,16,10,5,34,88第2趟排序后：2,5,10,12,16,34,88则可能的排序算法是：冒泡排序归并排序插入排序快速排序ABCD提交单选题2分选择一个排序算法时，除算法的时空效率外，还需要考虑的是：I、数据的规模II、数据的存储方式III、算法的稳定性IV、数据的初始状态仅 III仅 I、II仅 II、III、IVI、II、III、IVABCD提交单选题2分在基于比较的排序算法中，哪种算法的最坏情况下的时间复杂度不高于O(NlogN)？冒泡排序归并排序快速排序希尔排序ABCD提交单选题2分下面四种排序算法中，稳定的算法是？堆排序归并排序快速排序希尔排序ABCD提交单选题2分就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是：堆排序归并排序归并排序快速排序堆排序快速排序快速排序归并排序ABCD提交单选题2分