(26)--第7章 排序-归并数据结构基数.ppt
《(26)--第7章 排序-归并数据结构基数.ppt》由会员分享,可在线阅读,更多相关《(26)--第7章 排序-归并数据结构基数.ppt(43页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
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个队列链成一个链表重复上述两步,进行第二趟、第三趟分配和收集,分别对十位、百位进行,最后得到
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 26-第7章 排序-归并数据结构基数 26 排序 归并 数据结构 基数
限制150内