admin管理员组文章数量:1531478
作为数据结构的课程笔记,以便查阅。如有出错的地方,还请多多指正!
目录
- 多关键字排序 Multi-key Sort
- 最高位优先法 (MSD, Most Significant Digit first)
- 最低位优先法 (LSD, Least Significant Digit first)
- 链式基数排序 Linked Radix Sort
- 排序过程
- 思路
- 算法实现
- 算法评价
- T ( n ) T(n) T(n)
- S(n)
- 是否稳定
多关键字排序 Multi-key Sort
- 基数排序是一种借助 “多关键字排序” 思想来实现 “单逻辑关键字排序” 的内部排序算法
最高位优先法 (MSD, Most Significant Digit first)
- MSD: 必须将序列逐层分割成若干子序列,再对各子序列分别排序
- 先对最高位关键字 k 1 k_1 k1 排序,将序列分成若干子序列,每个子序列有相同的 k 1 k_1 k1 值
- 然后分别就每个子序列对次关键字 k 2 k_2 k2 排序,又分成若干更小的子序列
- 依次重复,直至对关键字 k d − 1 k_{d-1} kd−1 排序
- 分别就每个子序列对最低位关键字 k d k_d kd 排序
- 最后将所有子序列依次连接在一起成为一个有序序列
最低位优先法 (LSD, Least Significant Digit first)
- LSD: 不必逐层分割成子序列,并且可不通过关键字比较,而通过若干次分配与收集实现排序
- 从最低位关键字 k d k_d kd 起进行排序,再对高一位关键字排序
- 依次重复,直至对最高位关键字 k 1 k_1 k1 排序后,成为一个有序序列
链式基数排序 Linked Radix Sort
- 对于多关键字的记录序列,通常利用 LSD 法借助 “分配-收集” 进行排序
- 对于数字型或字符型的单逻辑关键字,可以看成是由多个数位或多个字符构成的多关键字 (例如三位数的排序可以看作有 3 个关键字:百位、十位、个位),也可以采用 “分配-收集” 的排序方法
- 链式基数排序:用静态链表作存储结构的基数排序
排序过程
思路
- 设置10个队列,
f[i]
和e[i]
分别为第i
个队列的头指针和尾指针 - 第一趟分配对最低位关键字(个位)进行,将链表中记录分配至10个链队列中,每个队列记录的关键字的个位相同
- 第一趟收集是改变非空队列的队尾记录指针域,令其指向下一个非空队列的队头记录,将10个队列连成一个链表
- 重复上述两步,进行第二趟、第三趟分配和收集,分别对十位、百位进行,最后得到一个有序序列
算法实现
- 将数据存储在如下的静态链表中,每个结点都有数据域和指针域
next
。next
中存的是链表中下一个结点在数组中的索引。第0个结点为头结点,不存数据,它指示了第一个结点的位置。数据域为1个数组,在里面存各个关键字(十进制数的不同位),默认0号关键字为最次要关键字(个位)
下图表示的链表即为1->2->3->4->5->6
#define MAX_SIZE 100 //待排元素个数的最大值
#define MAX_KEY_NUM 8 //最多的关键字个数 这里默认最大为8位数
//静态链表结点
typedef struct {
int keys[MAX_KEY_NUM];
int next;
}SLCell_t;
//静态链表
typedef struct {
SLCell_t data[MAX_SIZE+1];
int keyNum; //关键字个数
int len; //静态链表长度
}SLList_t;
- 设置队尾和队首指针。因为要比较的是10进制数的大小,基数为10,因此10个队尾指针和10个队首指针都分别用1个大小为10的
int
数组表示。指针域中存的值也为数据在静态链表的数组中的索引
#define RADIX 10 //关键字基数 这里排序的是10进制数,因此基数为10
typedef int PtrArr_t[RADIX]; //指针数组类型
- 一趟分配:先清空队首指针,遍历静态链表,依次将各个元素分配到不同队列中。要注意算法实现时并非是真的额外增加了10个队列,而是只更新队首和队尾指针,并更新对应的静态链表的指针域
//按照第 key_index 个关键字进行一趟分配
void Distribute(SLList_t* sllist, int key_index, PtrArr_t* f, PtrArr_t* e)
{
//清空队首指针
for (int i = 0; i < RADIX; ++i)
{
(*f)[i] = 0;
}
for (int p = sllist->data[0].next; p; p = sllist->data[p].next)
{
int key = sllist->data[p].keys[key_index];
if (!(*f)[key])
{
(*f)[key] = p;
}
else {
sllist->data[(*e)[key]].next = p;
}
(*e)[key] = p;
}
}
- 一趟收集:先将静态链表中的0号元素的指针域指向第一个非空队列的队首指针所指元素,之后将相邻的非空队列队首和队尾指针所指元素两两连接,然后将最后一个非空队列的队尾指针所指元素的指针域指向0表示链表尾
void Collect(SLList_t* sllist, PtrArr_t* f, PtrArr_t* e)
{
int i;
//找到第一个非空队列
for (i = 0; (*f)[i] == 0; ++i)
{
}
sllist->data[0].next = (*f)[i];
for (int j = i + 1; j < RADIX; ++j)
{
if ((*f)[j])
{
sllist->data[(*e)[i]].next = (*f)[j];
i = j;
}
}
sllist->data[(*e)[i]].next = 0;
}
- 主体部分
void SLList_radix_sort(SLList_t* sllist)
{
PtrArr_t f, e;
//初始化静态链表的指针域
for (int i = 0; i < sllist->len; ++i)
{
sllist->data[i].next = i + 1;
}
sllist->data[sllist->len].next = 0;
for (int i = 0; i < sllist->keyNum; ++i)
{
Distribute(sllist, i, &f, &e);
Collect(sllist, &f, &e);
}
}
void Radix_sort(SqList_t* list)
{
SLList_t sllist;
sllist.len = list->len;
sllist.keyNum = MAX_KEY_NUM;
//将数值转换为多关键字,存入静态链表
for (int i = 1; i < sllist.len + 1; ++i)
{
Key_t num = list->rec[i].key;
for (int j = 0; j < sllist.keyNum; j++)
{
sllist.data[i].keys[j] = num % 10;
num /= 10;
}
}
SLList_radix_sort(&sllist);
int adr[MAX_SIZE + 1];
adr[0] = 0;
for (int i = 1; i <= list->len; ++i)
{
adr[i] = sllist.data[adr[i-1]].next;
}
Rearrange(list, adr); //该函数是利用地址数组重排记录的实际物理地址 解释见内部排序的第一篇博客
}
算法评价
设 n : 记 录 数 , d : 关 键 字 数 , r d : 基 数 设\ \ n:记录数, d:关键字数 , rd:基数 设 n:记录数,d:关键字数,rd:基数
T ( n ) T(n) T(n)
- 一趟分配 (将
n
n
n 个记录分配到相应队列中)
T ( n ) = O ( n ) T(n) = O(n) T(n)=O(n) - 一趟收集:将
r
d
rd
rd 个队列首尾相连
T ( n ) = O ( r d ) T(n)=O(rd) T(n)=O(rd) ∴ T ( n ) = O ( d ( n + r d ) ) \therefore T(n)=O(d(n+rd)) ∴T(n)=O(d(n+rd)) - 可以看到,当 n n n 很大时,这个时间复杂度接近于线性
S(n)
- 需要
2
r
d
2rd
2rd 个队列指针以及
n
n
n 个指针域
∴ S ( n ) = O ( r d + n ) \therefore S(n)=O(rd+n) ∴S(n)=O(rd+n)
是否稳定
- 稳定
版权声明:本文标题:内部排序 (六):基数排序 (Radix Sort) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1725721769a1038461.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论