归并排序

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

基本思想

• 初始序列看成 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)

• 稳定性：稳定