definição e significado de 基数排序

本条目的内容可能尚不周全，請考虑将其他语言维基百科的内容翻譯成中文。
歡迎您積極參與，协助改善这篇条目。

基数排序
分類	排序算法
數據結構	数组
最差時間復雜度	$O(kN)$
最差空間復雜度	$O(kN)$
最佳算法	Yes
查 · 論 · 編

基数排序(Radix sort)是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献^[1]。

它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。

效率

基数排序的时间复杂度是 O(k·n)，其中n是排序元素个数，k是数字位数。注意这不是说这个时间复杂度一定优于O(n·log(n))，因为k的大小一般会受到 n 的影响。以排序n个不同整数来举例，假定这些整数以B为底，这样每位数都有B个不同的数字，k就一定不小于log_B(n)。由于有B个不同的数字，所以就需要B个不同的桶，在每一轮比较的时候都需要平均n·log₂(B) 次比较来把整数放到合适的桶中去，所以就有：

k 大于或等于 log_B(n)
每一轮(平均)需要 n·log₂(B) 次比较

所以，基数排序的平均时间T就是：

T ≥ log_B(n)·n·log₂(B) = log₂(n)·log_B(2)·n·log₂(B) = log₂(n)·n·log_B(2)·log₂(B) = n·log₂(n)

所以和比较排序相似，基数排序需要的比较次数：T ≥ n·log₂(n)。故其时间复杂度为 Ω(n·log₂(n)) = Ω(n·log n) 。

C++

#include <iostream>
 
using namespace std;
 
const int base=10;
 
struct wx
{
        int num;
        wx *next;
        wx()
        {
                next=NULL;
        }
};
 
wx *headn,*curn,*box[base],*curbox[base];
 
void basesort(int t)
{
        int i,k=1,r,bn;
        for(i=1;i<=t;i++)
        {
                k*=base;
        }
        r=k*base;
        for(i=0;i<base;i++)
        {
                curbox[i]=box[i];
        }
        for(curn=headn->next;curn!=NULL;curn=curn->next)
        {
                bn=(curn->num%r)/k;
                curbox[bn]->next=curn;
                curbox[bn]=curbox[bn]->next;
        }
        curn=headn;
        for(i=0;i<base;i++)
        {
                if(curbox[i]!=box[i])
                {
                        curn->next=box[i]->next;
                        curn=curbox[i];
                }
        }
        curn->next=NULL;
}
 
void printwx()
{
        for(curn=headn->next;curn!=NULL;curn=curn->next)
        {
                cout<<curn->num<<' ';
        }
        cout<<endl;
}
 
int main()
{
        int i,n,z=0,maxn=0;
        curn=headn=new wx;
        cin>>n;
        for(i=0;i<base;i++)
        {
                curbox[i]=box[i]=new wx;
        }
        for(i=1;i<=n;i++)
        {
                curn=curn->next=new wx;
                cin>>curn->num;
                maxn=max(maxn,curn->num);
        }
        while(maxn/base>0)
        {
                maxn/=base;
                z++;
        }
        for(i=0;i<=z;i++)
        {
                basesort(i);
        }
        printwx();
        return 0;
}

查 · 論 · 編排序算法

理論	計算複雜性理論 \| 大O符號 \| 全序關係 \| 列表 \| 穩定性 \| 比較排序 \| 拓扑排序 \| 排序網絡

交換排序法	冒泡排序 \| 鸡尾酒排序 \| 奇偶排序 \| 梳排序 \| 侏儒排序 \| 快速排序 \|臭皮匠算法 \| Bogo排序

選擇排序法	选择排序 \| 堆排序 \| Smooth排序 \| 笛卡尔树排序 \| 锦标赛排序 \| 循环排序

插入排序法	插入排序 \| 希尔排序 \| 二叉查找树排序 \| 图书馆排序 \| Patience排序

归并排序法	归并排序 \| 多相归并排序 \| Strand排序

分布排序法	美国旗帜排序 \| 珠排序 \| 桶排序 \| 爆炸排序 \| 计数排序 \| 鸽巢排序 \| 相邻图排序 \| 基数排序 \| 闪电排序

混合排序法	Tim排序 \| 内省排序 \| Spread排序 \| 反移排序 \| J排序

其他	双调排序器 \| Batcher归并网络 \| 两两排序网络

参考文献

^ US patent 395781 和 UK patent 327

Definição e significado de 基数排序

Definição

基数排序

效率

C++

参考文献