原创力文档- 1、本文档共28页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
查看更多
第二十讲分配排序与归并排序
孙猛
/teachers/sunm
2016年12月29 日
1
• 分配排序
• 归并排序
• 课程总结
2
• 基本思想：分配排序是把排序码分解成若⼲部分，然后通过
对各个部分排序码的分别排序，最终实现对整个排序码的排
序。
• 定义：假设⽂件F⾥有n个记录，F=(R ,R ,…,R ) ，且记录
0 1 n-1
R 的排序码包含 d 个部分 (k 0,k 1,…,k d-1) ，⽂件 F 对排序码
i i i i
0 1 d-1
(k ,k ,…,k ) 有序是指：对于⽂件中的任意两个记录 Ri 和
R (0≤i≤j≤n-1)，其排序码都满⾜字典序：
j
(ki0, ki1,…, kid-1) ≤ (kj0, kj1,…, kjd-1)
• 这⾥ki0 称为最⾼位排序码，k id-1 称为最低位排序码。
3
0
• 从最⾼位排序码k 开始，逐个针对各个排序码排序，这种⽅
法称为⾼位优先法。
• 采⽤⾼位优先排序，按⼀位排序码排序，就是将⽂件分割成若⼲
⼦⽂件。要完成整个⽂件的排序，后续⼯作是做各⼦⽂件独⽴排
序。
• 这样逐层分割，d数⽬⼤时分许多层，数据组织⽐较麻烦。
• 例如扑克牌排序(花⾊和点数) ：
• 先按花⾊分成4组，
• 然后每组按点数排序，
• 最后把4组收集到⼀起。
4
• 从最低位排序码kd-1开始排序，称为低位优先法。
• i
低位优先排序不划分⼦⽂件，对每位排序码K ⼯作时都以整
个⽂件作为排序对象，通过若⼲次“分配”和“收集”实现。
• 例如扑克牌排序(花⾊和点数) ：
• 先按点数分13组，收集到⼀起；
• 后按花⾊分4组，再收集到⼀起。
• 低位优先法的实现⽐⾼位优先法简单。
• i
但是要求针对各 K 的排序必须⽤稳定的排序⽅法。
5
• 把排序码看成 d 元组：
K = (K 0, K 1,…, K d-1)
i i i i
j
其中每个 K 都是集合{C ,C ,…,C } 中的元素，这些元素满⾜：
i 0 1 r-1
C C …C
0 1 r-1
r 称为排序码的
文档评论（0）