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

归并排序

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

基本思想

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

在这里插入图片描述

算法分析

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

基数排序

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

多关键字排序

• 多关键字： n 个记录的序列 { R1, R2, …，Rn} 对关键字 (Ki0, Ki1,…,Kid-1) 有序是指： - 对于序列中任意两个记录 Ri 和 Rj(1≤i<j≤n) 都满足下列*词典)有序关系： (Ki0, Ki1, …,Kid-1) < (Kj0, Kj1, …,Kjd-1) - K0 被称为 “最主”位关键字， - Kd-1 被称为 “最次”位关键字

最高位优先MSD法

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

在这里插入图片描述

最低位优先LSD法

• 首先依据最低位排序码Kd对所有对象进行一趟排序
• 再依据次低位排序码Kd-1对上一趟排序结果排序
• 依次重复，直到依据排序码K1最后一趟排序完成，就可以得到一个有序的序列。这种方法不需要再分组，而是整个对象组都参加排序

在这里插入图片描述

链式基数排序

基本思想

• 先决条件： - 知道各级关键字的主次关系 - 知道各级关键字的取值范围
• 过程 - 首先对低位关键字排序，各个记录按照此位关键字的值‘分配’到相应的序列里。 - 按照序列对应的值的大小，从各个序列中将记录‘收集’，收集后的序列按照此位关键字有序。 - 在此基础上，对前一位关键字进行排序。

算法设计

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

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

算法分析

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