基本思想
基数排序(radix sort),同样时一种非比较的内部排序算法,主要基于多关键字排序的思想进行排序,它将单个关键字按照基数分成“多个关键字”进行排序。例如整数789是一个关键字,可以按照十进制位划分多关键字(十进制数字取值0-9,所以基数是10),从高到低分为三个关键字“7、8、9”,这样对每位关键字进行排序,即可得到排序。
基数排序对关键字数据元素有要求,一般是等长的整数和字符串。基数排序是一种稳定的内部排序算法。时间复杂度是O(d*(n+radix),d是关键字位数,radix是基数。
例如:对于(21, 12, 31, 10, 30)进行基数排序,可以按照以下步骤进行。
1.根据每一位数字,划分组,最多10组,因为基数为10,代表数字0-9。
2.首先看十位数字,从小到大排序后,可以得到(12,10)(21)(31,30)三组数,数字相同的分为一组。
3.再看个位数字,对上述三组分别进行从小到大排序后,得到(10,12)(21)(30,31),最终得到有序序列。
以上基数排序采用最高位优先方法,从高位到低位进行划分,同样还可以采用从最低位开始排序。最高位优先法排序时候必须不断对划分子序列进行排序,编程实现复杂,最低位优先方法可以每次从低位开始对整个序列进行排序,无需划分。
代码实现
1.实现基于“链式基数排序”方法,具体理论参见数据结构相关书籍。
2.基数排序关键操作是分配和收集,分配就是每次根据关键字分组到链队列中,收集是将分组链队列排序后的数据记录整理成完整的链表。
3.使用数组实现静态链表存放待排序的数据记录。
4.需要两个数组辅助,大小为基数,一个数组负责指向链队列头部,一个数组指向链队列尾部。
/*
#include <stdio.h>
#include <stdlib.h>
// 对整数,基数为10
#define RADIX 10
// 最大元素个数
#define MAX_LENGTH 100
// 静态链表结点
struct node
{
int data;
// 下标代替指针表示下一个结点
int next;
};
// 获取关键字每一位数字
// i=1 表示个位,i=2,表示十位
int get_digit(int n, int loc)
{
int i;
for(i=1; i<loc; i++)
n = n/10;
return n%10;
}
// 分配和收集操作
void distri_collect(struct node r[], int length, int loc)
{
// 辅助数组,指向每个链队列
int front[RADIX], rear[RADIX];
// 初始为空
int i;
for(i=0; i<RADIX; i++)
{
front[i] = 0;
rear[i] = 0;
}
// 遍历整个静态链表,按照关键字分配到各链队列
int p,digit;
for(p = r[0].next ; p!=0 ; p=r[p].next)
{
digit = get_digit(r[p].data, loc);
// 链队列为空时直接插入
if(front[digit] == 0)
front[digit] = p;
else
{
// 插入尾部
r[rear[digit]].next = p;
}
rear[digit] = p;
}
// 收集合并
// 找到第一个1非空链队列
for(i=0; front[i] == 0 && i<RADIX; i++);
r[0].next = front[i];
p = rear[i];
while(i<RADIX)
{
// 寻找下一个非空链队列
for(i++;i<RADIX-1 && front[i]==0;++i);
// 对最后一个元素特殊处理
if(i>=RADIX) break;
if(front[i])
{
// 链接两个非空链队列
r[p].next = front[i];
p = rear[i];
}
}
r[p].next = 0;
}
void radix_sort(int a[], int length, int k)
{
// 创建静态链表保存数据
// r[0]表示头结点
struct node r[MAX_LENGTH];
// 初始化链表为空
r[0].next = 0;
int i;
for(i=0; i<length; i++)
{
r[i].next = i+1;
r[i+1].data = a[i];
}
// 链表最后一个元素指向0,表示链表结束
r[i].next = 0;
// 对关键字按照从低位到高位进行排序
for(i=1; i<=k; i++)
distri_collect(r, length, i);
// 将排序后的结果复制到原数组a中
int p = r[0].next;
for(i=0; i<length && p!=0; i++)
{
a[i] = r[p].data;
p = r[p].next;
}
}
int main(void)
{
int a[14] = {103,102,101,401,489,345,322,710,500,609,800,0,3,4};
radix_sort(a, 14, 3);
int i;
for(i=0; i<14; i++)
printf("%d ", a[i]);
return 0;
}
其实做为一个学习者,有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410,不管你是小白还是转行人士欢迎入驻,大家一起交流成长。
网友评论