基数排序
前面所讲的排序都是基于关键字比较，而分配类的排序不需要比较关键字大小，它是根据关键字中各位的值，通过对待排序记录进行若干遍“分配”与“收集”来实现排序的，是一种借助于多关键字排序的思想对单关键字排序的方法。基数排序（Radix Sorting）是典型的分配类排序。
多关键字排序
先看一个具体例子。
已知扑克牌中 52 张牌的次序关系为：先按花色黑桃、红桃、梅花、方格的顺序放置，同花色的按点数
每一张牌有两个关键字：花色和点数，且花色的地位高于点数，在比较任意两张牌的大小时，必须先比较花色，再比较点数。
因此，将扑克牌整理成如上所述次序关系时，有以下两种方法：
- 最高位优先法：先按不同花色分成有次序的 4 堆，每一堆的牌均具有相同的花色，然后分别对每一堆按点数大小整理有序；
- 最低位优先法：这是一种分配与收集交替进行的方法。先按不同点数分成 13 堆，然后将这 13 堆牌自小至大叠在一起（3 在 2 之上，4 在 3 之上，......，最上面的是 4 张 A）。再重新对这些牌按不同花色分成 4 堆，最后将这 4 堆牌按花色的次序再收集到一起，此时同样得到一副满足如上次序关系的牌。
链式基数排序
基数排序的思想类似于上述“最低位优先法”的洗牌过程，是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。有的逻辑关键字可以看成由若干个关键字复合而成的。例如，若关键字是数值，且其值都在
假设记录的逻辑关键字由
具体实现时，一般采用链式基数排序。
具体排序过程如下图。
首先以链表存储
第一趟分配对个位数进行，改变记录的指针值将链表中的记录分配至 10 个链队列中，每个队列中的记录关键字的个位数相等，如图 b 所示，其中
第二趟分配和第二趟收集是对十位数进行的，其过程和个位数相同。分配和收集结果分别如图 d 和图 e 所示。
第三趟分配和第三趟收集是对百位数进行的，过程同上，分配和收集结果分别如图 f 和图 g 所示。至此排序完毕。
算法实现时采用静态链表，以便于更有效地存储和重排记录。
算法如下：
const RADIX = 10
export class StaticListNode {
constructor(public keys: number[], public next: number) {}
}
function distribute(
link: StaticListNode[],
heads: number[],
tails: number[],
exp: number
) {
let p = link[0].next // 取头结点指向的元素。
while (p) {
const i = link[p].keys[exp]
if (heads[i] === -1) {
heads[i] = p
} else {
link[tails[i]].next = p
}
tails[i] = p
p = link[p].next
}
}
function collect(link: StaticListNode[], heads: number[], tails: number[]) {
let j = 0
while (heads[j] === -1) {
// 找到第一个非空链表。
j++
}
link[0].next = heads[j] // 头结点指向第一个非空链表。
let t = tails[j]
let i = j + 1
while (i < RADIX) {
if (heads[i] !== -1) {
// 找到下一个非空链表，并且链接到上一个非空链表。
link[t].next = heads[i]
t = tails[i]
}
i++
}
link[t].next = 0 // 尾结点指向头结点。
}
export function radixSort(link: StaticListNode[], exp: number) {
const heads = Array.from({ length: RADIX }, () => -1)
const tails = Array.from({ length: RADIX }, () => -1)
distribute(link, heads, tails, exp)
collect(link, heads, tails)
if (exp > 0) {
radixSort(link, exp - 1)
}
}使用方法：
const arr = [-1, 5, 4, 2, 1].map(
(key, idx, arr) =>
new StaticListNode([key], idx !== arr.length - 1 ? idx + 1 : 0)
)
radixSort(arr, 0)
expect(arr).toEqual([
new StaticListNode([-1], 4),
new StaticListNode([5], 0),
new StaticListNode([4], 1),
new StaticListNode([2], 2),
new StaticListNode([1], 3),
])时间复杂度
对于
空间复杂度
所需辅助空间为
特点
- 稳定；
- 链式结构和顺序结构皆可用；
- 时间复杂度可以突破关键字比较一类方法的下界
，达到 ； - 基数排序使用条件有严格的要求：需要知道各级关键字的主次关系和各级关键字的取值范围。
另一种实现：
export class RadixSort {
static sort(arr: number[]): number[] {
const max = Math.max(...arr)
let exp = 1
while (Math.floor(max / exp) > 0) {
arr = this.countSort(arr, exp)
exp *= RADIX
}
return arr
}
private static countSort(arr: number[], exp: number): number[] {
const count = Array.from({ length: RADIX }, () => 0)
const output = Array.from({ length: arr.length }, () => 0)
const units = arr.map((item) => Math.floor(item / exp) % RADIX)
for (let i = 0; i < arr.length; i++) {
count[units[i]]++
}
for (let i = 1; i < RADIX; i++) {
count[i] += count[i - 1]
}
for (let i = arr.length - 1; i >= 0; i--) {
output[count[units[i]] - 1] = arr[i]
count[units[i]]--
}
return output
}
}该实现与上述实现区别是，该实现的收集方式通过调整元素位置替代调整 next 指针，这减少了指针域所占用的存储空间，但是由于在调整元素位置时需要