21天学习挑战赛-链式基数排序

​
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…
…

链式基数排序

基数排序是借助“分配”和“收集”两种操作对单逻辑关键字进行排序的一种内部排序方法。

1. 基数排序的定义

有的逻辑关键字可以看成由若干个关键字复合而成的。

例如，若关键字是数值，且其值都在 $0\le K\le 999$ 范围内，则可把每一个十进制数字看成一个关键字，即可认为 K 由 3 个关键字 $(K^0,K^1,K^2)$ 组成，其中 $K^0$ 是百位数，$K^1$ 是十位数，$K^2$ 是个位数；又若关键字 $K$ 是由 5 个字母组成的单词，则可看成是由 5 个关键字 $\left(K^0,K^1,K^2,K^3,K^4\right)$ 组成，其中 $K^{j-1}$ 是（自左至右的）第 $j+1$ 个字母。由于如此分解而得的每个关键字 $K^j$ 都在相同的范围内（对数字 $0⩽K^j⩽9$, 对字母 ${}^{\prime }{\mathrm{A}}^{\prime }⩽K^j{⩽}^{\prime }{Z}^{\prime }$），则按 LSD 进行排序更为方便，只要从最低数位关键字起，按关键字的不同值将序列中记录“分配”到 RADIX 个队列中后再“收集”之，如此重复 $d$ 次。

按这种方法实现排序称之为 基数排序，其中“基”指的是 RADIX 的取值范围，在上述两种关键字的情况下，它们分别为 “10” 和 “26”。

实际上，早在计算机出现之前，利用卡片分类机对穿孔卡上的记录进行排序就是用的这种方法。然而，在计算机出现之后却长期得不到应用，原因是所需的辅助存储量（$RADIXxN$ 个记录空间）太大。直到 1954 年有人提出用“计数”代替“分配”才使基数排序得以在计算机上实现，但此时仍需要 $n$ 个记录和 $2xRADIX$ 个计数单元的辅助空间。此后，有人提出用链表作存储结构，则又省去了 $n$ 个记录的辅助空间。下面我们就来介绍这种“链式基数排序”的方法。

2. 实例代码

在描述算法之前，尚需定义新的数据类型

#define MAX_NUM_OF_KEY 8                    //关键字项数的最大值 
#define RADIX 10                            //关键字基数，此时是十进制整数的基数 
#define MAX_SPACE 10000 

typedef struct{
    KeysType keys[MAK_NUM_OF_KEY];          //关键字
    InfoType otheritems;                    //其他数据项 
    int next; 
}SLCell;                                    //静态链表的结点类型 

typedef struct{
    SLCell r[MAX_SPACE];                    //静态链表的可利用空间，r[0] 为头结点
    int keynum;                             //记录的当前关键字个数
    int recnum;                             //静态链表的当前长度
}SLList;                                    //静态链表类型 

typedef int ArrType[RADIX];                 //指针数组类型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

算法 10.15

算法 10.15 为链式基数排序中一趟分配的算法

void Distribute (SLCell & r, int i, ArrType & f, ArrType & e){

    //静态链表 L 的 r 域中记录已按（keys[0], ... , keys[i-1]) 有序
    //本算法按第 i 个关键字 keys[i] 建立 RADIX 个子表，使同一子表中记录的 keys[i] 相同
    //f[0..RADIX - 1] 和 e[0..RADIX - 1] 分别指向各子表中第一个和最后一个记录。 
    
    for(j = 0; j < Radix; ++ j)
        f[j] = 0;                           //各子表初始化为空表 
        
    for(p = r[0].next; p; p = r[p].next){
        j = ord(r[p].keys[i]);              //ord 将记录中第 i 个关键字映射到 [0..RADIX - 1],

        if(!f[j])
            f[j] = p;
        else 
            r[e[j]].next = p;

        e[j] = p;                           //将 p 所指的结点插入第 j 个子表中
    }
}//Distribute
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

算法 10.16

算法 10.16 为一趟收集的算法:

void Collect(SLCell & r, int i, ArrType f, ArrType e){

    //本算法按 keys[i] 自小至大地将 f[0..RADIX - 1] 所指各子表依次链接成一个链表, e[0..RADIX - 1] 为各子表的尾指针。
    for(j = 0; !f[j]; j = succ(j));          //找第一个非空子表，succ 为求后继函数
        r[0].next = f[j];
        t = e[j];                            //r[0].next 指向第一个非空子表中第一个结点

    while(j < RADIX){
        
        for(j = succ(j); j < RADIX - 1 && !f[j]; j = succ(j)); //找下一个非空子表

        if(f[j]){
            r[t].next = f[j];         
            t = e[j];                        //链接两个非空子表
        }
    }

    r[t].next = 0;                           //t 指向最后一个非空子表中的最后一个结点 
    
}// Collect
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

算法 10.17

算法 10.17 为链式基数排序的算法:

void RadixSort (SLList & L){

    //L 是采用静态链表表示的顺序表
    //对 L 作基数排序，使得 L 成为按关键字自小到大的有序静态链表，L.r[0] 为头结点。
    for(i = 0; i < L.recnum; ++ i) 
        L.r[i].next = i + 1; 

    L.r[L.recnum].next = 0;                   //将 L 改造为静态链表

    for(i = 0; i < L.keynum; ++ i) {          //按最低位优先依次对各关键字进行分配和收集
        Distribute (L.r, i, f, e);            //第 i 趟分配
        Collect(L.r, i, f, e);                //第 i 趟收集
    }

}//RadixSort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

从算法中容易看出，对于 $n$ 个记录（假设每个记录含 $d$ 个关键字，每个关键字的取值范围为 $rd$ 个值）进行链式基数排序的时间复杂度为 $O(d(n+rd))$，其中每一趟分配的时间复杂度为 $O(n)$，每一趟收集的时间复杂度为 $O(rd)$，整个排序需进行 $d$ 趟分配和收集。所需辅助空间为 $2rd$ 个队列指针。当然，由于需用链表作存储结构，则相对于其他以顺序结构存储记录的排序方法而言，还增加了 $n$ 个指针域的空间。