7.10 数排序★4◎3--考研乐学帮

7.10 数排序★4◎3

7.10 基数排序★4◎3

　　基数排序是一种借助于多关键码排序的思想，是将单关键码按基数分成“多关键码”进行排序的方法。
　　1．多关键码排序
　　设n个元素的待排序列包含d个关键码，对于序列中任两个记录r[i]和 r[j](1≤i≤j≤n)都满足下列有序关系：
　　，其中称为最主位关键码，称为最次位关键码，则称序列对关键码﹛k1,k2,…,kd﹜有序。
　　多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序，分两种方法：
　　 最高位优先（Most Significant Digit first）法，简称MSD法：先按k1排序分组，同一组记录中关键码k1相等，再对各组按k2排序分成子组，之后对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。最后将各组连接起来，便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法即为MSD法。
　　 最低位优先（Least Significant Digit first）法，简称LSD法：先从kd开始排序，再对kd1进行排序，依次重复，直到对k1排序后便得到一个有序序列。
　　2．链式基数排序
　　将关键码拆分为若干项，每项作为一个“关键码”，则对单关键码的排序可按多关键码排序方法进行。比如，关键码为4位的整数，可以每位对应一项，拆分成4项；又如，关键码由5个字符组成的字符串，可以每个字符作为一个关键码。由于这样拆分后，每个关键码都在相同的范围内（对数字是0～9，字符是'a'～'z'），称这样的关键码可能出现的符号个数为“基”，记做RADIX。上述取数字为关键码的“基”为10，取字符为关键码的“基”为26。基于这一特性，用LSD法排序较为方便。
　　基数排序：从最低位关键码起，按关键码的不同值将序列中的记录“分配”到RADIX个队列中，然后再“收集”，如此重复d次即可。链式基数排序是用RADIX个链队列作为分配队列，关键码相同的记录存入同一个链队列中，“收集”则是将各链队列按关键码大小顺序链接起来。
　　以静态链表存储待排记录，头结点指向第一个记录。链式基数排序过程如图7-4所示。
　　【效率分析】
　　时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为RADIX，则进行链式基数排序的时间复杂度为O(d(n+RADIX))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(RADIX)，共进行d趟分配和收集。