排序——归并排序 ＆ 基数排序

排序——归并排序 ＆ 基数排序

​​归并排序​​

​​基本思想​​​​算法分析​​

​​基数排序​​

​​多关键字排序​​

​​最高位优先MSD法​​​​最低位优先LSD法​​

​​链式基数排序​​

​​基本思想​​​​算法设计​​​​算法分析​​

归并排序

归并：将两个或两个以上的有序表组合成一个新有序表

基本思想

初始序列看成n个有序子序列，每个子序列长度为1两两合并，得到n/2个长度为2或1的有序子序列再两两合并，重复直至得到一个长度为n的有序序列为止

算法分析

时间效率：O(nlog2n)空间效率：O（n）稳定性：稳定

基数排序

基数排序是一种借助“多关键字排序”的思想来实现“单关键字排序”的内部排序算法。

多关键字排序

多关键字： n 个记录的序列 { R1, R2, …，Rn} 对关键字 (Ki0, Ki1,…,Kid-1) 有序是指：

对于序列中任意两个记录 Ri 和 Rj(1≤i

最高位优先MSD法

先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至就每个子序列对最低位关键字kd排序，就可以得到一个有序的序列。

十进制数比较可以看作是一个多关键字排序

最低位优先LSD法

首先依据最低位排序码Kd对所有对象进行一趟排序再依据次低位排序码Kd-1对上一趟排序结果排序依次重复，直到依据排序码K1最后一趟排序完成，就可以得到一个有序的序列。

这种方法不需要再分组，而是整个对象组都参加排序

链式基数排序

基本思想

先决条件：

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

过程

首先对低位关键字排序，各个记录按照此位关键字的值‘分配’到相应的序列里。按照序列对应的值的大小，从各个序列中将记录‘收集’，收集后的序列按照此位关键字有序。在此基础上，对前一位关键字进行排序。

算法设计

待排序记录以指针相链，构成一个链表“分配” 时，按当前“关键字位”所取值，将记录分配到不同的 “链队列” 中，每个队列中记录的 “关键字位” 相同“收集”时，按当前关键字位取值从小到大将各队列首尾相链成一个链表对每个关键字位均重复以上步骤

算法分析

n个记录每个记录有d 位关键字关键字取值范围rd(如十进制为10)时间效率：O(d( n+rd))空间效率：O(n+rd)稳定性：稳定

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。