基数排序-阿里云开发者社区

开发者社区> usher.yue> 正文

基数排序

简介: 基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。
+关注继续查看
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。
中文名
基数排序
外文名
Radix sort
类    别
分配式排序
别    称
“桶子法”
方    法
最高位优先法和最低位优先
发明者
赫尔曼·何乐礼
领    域
计算机算法

基本解法

第一步

以LSD为例,假设原来有一串数值如下所示:
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值,在走访数值时将它们分配至编号0到9的桶子中:
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39

第二步

接下来将这些桶子中的数值重新串接起来,成为以下的数列:
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配,这次是根据十位数来分配:
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93

第三步

接下来将这些桶子中的数值重新串接起来,成为以下的数列:
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕;如果排序的对象有三位数以上,则持续进行以上的动作直至最高位数为止。
LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。

效率分析

时间效率[1]  :设待排序列为n个记录,d个关键码,关键码的取值范围为radix,则进行链式基数排序的时间复杂度为O(d(n+radix)),其中,一趟分配时间复杂度为O(n),一趟收集时间复杂度为O(radix),共进行d趟分配和收集。 空间效率:需要2*radix个指向队列的辅助空间,以及用于静态链表的n个指针

实现方法

最高位优先(Most Significant Digit first)法,简称MSD法:先按k1排序分组,同一组中记录,关键码k1相等,再对各组按k2排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd对各子组排序后。再将各组连接起来,便得到一个有序序列。
最低位优先(Least Significant Digit first)法,简称LSD法:先从kd开始排序,再对kd-1进行排序,依次重复,直到对k1排序后便得到一个有序序列。

实现原理

基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSD(Least significant digital)或MSD(Most significant digital),LSD的排序方式由键值的最右边开始,而MSD则相反,由键值的最左边开始。

实现

C语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#include<math.h>
testBS()
{
    inta[] = {2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3};
    int *a_p = a;
    //计算数组长度
    intsize = sizeof(a) / sizeof(int);
    //基数排序
    bucketSort3(a_p, size);
    //打印排序后结果
    inti;
    for(i = 0; i < size; i++)
    {
        printf("%d\n", a[i]);
    }
    intt;
    scanf("%d", t);
}
//基数排序
voidbucketSort3(int *p, intn)
{
    //获取数组中的最大数
    intmaxNum = findMaxNum(p, n);
    //获取最大数的位数,次数也是再分配的次数。
    intloopTimes = getLoopTimes(maxNum);
    inti;
    //对每一位进行桶分配
    for(i = 1; i <= loopTimes; i++)
    {
        sort2(p, n, i);
    }
}
//获取数字的位数
intgetLoopTimes(intnum)
{
    intcount = 1;
    inttemp = num / 10;
    while(temp != 0)
    {
        count++;
        temp = temp / 10;
    }
    returncount;
}
//查询数组中的最大数
intfindMaxNum(int *p, intn)
{
    inti;
    intmax = 0;
    for(i = 0; i < n; i++)
    {
        if(*(p + i) > max)
        {
            max = *(p + i);
        }
    }
    returnmax;
}
//将数字分配到各自的桶中,然后按照桶的顺序输出排序结果
voidsort2(int *p, intn, intloop)
{
    //建立一组桶此处的20是预设的根据实际数情况修改
    intbuckets[10][20] = {};
    //求桶的index的除数
    //如798个位桶index=(798/1)%10=8
    //十位桶index=(798/10)%10=9
    //百位桶index=(798/100)%10=7
    //tempNum为上式中的1、10、100
    inttempNum = (int)pow(10, loop - 1);
    inti, j;
    for(i = 0; i < n; i++)
    {
        introw_index = (*(p + i) / tempNum) % 10;
        for(j = 0; j < 20; j++)
        {
            if(buckets[row_index][j] == NULL)
            {
                buckets[row_index][j] = *(p + i);
                break;
            }
        }
    }
    //将桶中的数,倒回到原有数组中
    intk = 0;
    for(i = 0; i < 10; i++)
    {
        for(j = 0; j < 20; j++)
        {
            if(buckets[i][j] != NULL)
            {
                *(p + k) = buckets[i][j];
                buckets[i][j] = NULL;
                k++;
            }
        }
    }
}

Java语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class RadixSort
{
    public static void sort(int[] number, int d) //d表示最大的数有多少位
    {
        intk = 0;
        intn = 1;
        intm = 1//控制键值排序依据在哪一位
        int[][]temp = newint[10][number.length]; //数组的第一维表示可能的余数0-9
        int[]order = newint[10]; //数组orderp[i]用来表示该位是i的数的个数
        while(m <= d)
        {
            for(inti = 0; i < number.length; i++)
            {
                intlsd = ((number[i] / n) % 10);
                temp[lsd][order[lsd]] = number[i];
                order[lsd]++;
            }
            for(inti = 0; i < 10; i++)
            {
                if(order[i] != 0)
                    for(intj = 0; j < order[i]; j++)
                    {
                        number[k] = temp[i][j];
                        k++;
                    }
                order[i] = 0;
            }
            n *= 10;
            k = 0;
            m++;
        }
    }
    public static void main(String[] args)
    {
        int[]data =
        {7322934355142865398133100};
        RadixSort.sort(data, 3);
        for(inti = 0; i < data.length; i++)
        {
            System.out.print(data[i] + "");
        }
    }
}

pascal

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
type link=^node;
node=record
data:integer;
next:link;
end;
var
i,j,l,m,k,n:integer;
a:array[1..100] of integer;
s:string;
q,head:array[0..9] of link;
p,p1:link;
begin
readln(n);
writeln('Enterdata:');
for i:=1 to n do read(a[i]);
for i:=5 downto 1 do
begin
for j:=0 to 9 do
begin
new(head[j]);
head[j]^.next:=nil;
q[j]:=head[j]
end;
for j:=1 to n do
begin
str(a[j],s);
for k:=1 to 5-length(s) do
s:='0'+s;
m:=ord(s[i])-48;
new(p);
p^.data:=a[j];
p^.next:=nil;
q[m]^.next:=p;
q[m]:=p;
end;
l:=0;
for j:=0 to 9 do
begin
p:=head[j];
while p^.next<>nil do
begin
l:=l+1;
p1:=p;
p:=p^.next;
dispose(p1);
a[l]:=p^.data;
end;
end;
end;
writeln('Sorteddata:');
for i:=1 to n do
write(a[i]:6);
end.

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
int maxbit(int data[], int n) //辅助函数,求数据的最大位数
{
    int d = 1; //保存最大的位数
    int p = 10;
    for(int i = 0; i < n; ++i)
    {
        while(data[i] >= p)
        {
            p *= 10;
            ++d;
        }
    }
    return d;
}
void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = newint[n];
    int *count = newint[10]; //计数器
    int i, j, k;
    int radix = 1;
    for(i = 1; i <= d; i++) //进行d次排序
    {
        for(j = 0; j < 10; j++)
            count[j] = 0; //每次分配前清空计数器
        for(j = 0; j < n; j++)
        {
            k = (data[j] / radix) % 10; //统计每个桶中的记录数
            count[k]++;
        }
        for(j = 1; j < 10; j++)
            count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
        for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
        {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        for(j = 0; j < n; j++) //将临时数组的内容复制到data中
            data[j] = tmp[j];
        radix = radix * 10;
    }
    delete[]tmp;
    delete[]count;
}

C# 实现基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LearnSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = CreateRandomArray(10); //产生随机数组
            Print(arr);//输出数组
            RadixSort(refarr);//排序
            Print(arr);//输出排序后的结果
            Console.ReadKey();
        }
        public static void RadixSort(ref int[] arr)
        {
            int iMaxLength = GetMaxLength(arr);
            RadixSort(ref arr, iMaxLength);
        }
        //排序
        private static void RadixSort(ref int[] arr, int iMaxLength)
        {
            List<int> list = newList<int>(); //存放每次排序后的元素
            List<int>[] listArr = newList<int>[10]; //十个桶
            char currnetChar;//存放当前的字符比如说某个元素123中的2
            string currentItem;//存放当前的元素比如说某个元素123
            for(int i = 0; i < listArr.Length; i++) //给十个桶分配内存初始化。
                listArr[i] = newList<int>();
            for(int i = 0; i < iMaxLength; i++) //一共执行iMaxLength次,iMaxLength是元素的最大位数。
            {
                foreach(int number in arr)//分桶
                {
                    currentItem = number.ToString(); //将当前元素转化成字符串
                    try
                    {
                        currnetChar = currentItem[currentItem.Length - i - 1];   //从个位向高位开始分桶
                    }
                    catch
                    {
                        listArr[0].Add(number);    //如果发生异常,则将该数压入listArr[0]。比如说5是没有十位数的,执行上面的操作肯定会发生越界异常的,这正是期望的行为,我们认为5的十位数是0,所以将它压入listArr[0]的桶里。
                        continue;
                    }
                    switch(currnetChar)//通过currnetChar的值,确定它压人哪个桶中。
                    {
                    case'0':
                        listArr[0].Add(number);
                        break;
                    case'1':
                        listArr[1].Add(number);
                        break;
                    case'2':
                        listArr[2].Add(number);
                        break;
                    case'3':
                        listArr[3].Add(number);
                        break;
                    case'4':
                        listArr[4].Add(number);
                        break;
                    case'5':
                        listArr[5].Add(number);
                        break;
                    case'6':
                        listArr[6].Add(number);
                        break;
                    case'7':
                        listArr[7].Add(number);
                        break;
                    case'8':
                        listArr[8].Add(number);
                        break;
                    case'9':
                        listArr[9].Add(number);
                        break;
                    default:
                        throw new Exception("unknowerror");
                    }
                }
                for(int j = 0; j < listArr.Length; j++) //将十个桶里的数据重新排列,压入list
                    foreach(int number in listArr[j].ToArray<int>())
                    {
                        list.Add(number);
                        listArr[j].Clear();//清空每个桶
                    }
                arr = list.ToArray<int>(); //arr指向重新排列的元素
                //Console.Write("{0}times:",i);
                Print(arr);//输出一次排列的结果
                list.Clear();//清空list
            }
        }
        //得到最大元素的位数
        private static int GetMaxLength(int[] arr)
        {
            int iMaxNumber = Int32.MinValue;
            foreach(int in arr)//遍历得到最大值
            {
                if(i > iMaxNumber)
                    iMaxNumber = i;
            }
            return iMaxNumber.ToString().Length;//这样获得最大元素的位数是不是有点投机取巧了...
        }
        //输出数组元素
        public static void Print(int[] arr)
        {
            foreach(intiinarr)
                System.Console.Write(i.ToString() + '\t');
            System.Console.WriteLine();
        }
        //产生随机数组。随机数的范围是0到1000。参数iLength指产生多少个随机数
        public static int[] CreateRandomArray(int iLength)
        {
            int[] arr = new int[iLength];
            Random random = new Random();
            for(inti = 0; i < iLength; i++)
                arr[i] = random.Next(0, 1001);
            return arr;
        }
    }
}

python 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#!/usr/bin/env python
#encoding=utf-8
 
import math
 
def sort(a, radix=10):
    """a为整数列表, radix为基数"""
    = int(math.ceil(math.log(max(a), radix))) # 用K位数可表示任意整数
    bucket = [[] for in range(radix)] # 不能用 [[]]*radix
    for in range(1, K+1): # K次循环
        for val in a:
            bucket[val%(radix**i)/(radix**(i-1))].append(val) # 析取整数第K位数字 (从低到高)
        del a[:]
        for each in bucket:
            a.extend(each) # 桶合并
        bucket = [[] for in range(radix)]

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
7251 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,大概有三种登录方式:
2509 0
阿里云服务器端口号设置
阿里云服务器初级使用者可能面临的问题之一. 使用tomcat或者其他服务器软件设置端口号后,比如 一些不是默认的, mysql的 3306, mssql的1433,有时候打不开网页, 原因是没有在ecs安全组去设置这个端口号. 解决: 点击ecs下网络和安全下的安全组 在弹出的安全组中,如果没有就新建安全组,然后点击配置规则 最后如上图点击添加...或快速创建.   have fun!  将编程看作是一门艺术,而不单单是个技术。
8947 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
2119 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
10541 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
4448 0
阿里云ECS云服务器初始化设置教程方法
阿里云ECS云服务器初始化是指将云服务器系统恢复到最初状态的过程,阿里云的服务器初始化是通过更换系统盘来实现的,是免费的,阿里云百科网分享服务器初始化教程: 服务器初始化教程方法 本文的服务器初始化是指将ECS云服务器系统恢复到最初状态,服务器中的数据也会被清空,所以初始化之前一定要先备份好。
5835 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
2950 0
+关注
usher.yue
算法相关技术专家
431
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《Nacos架构&原理》
立即下载
《看见新力量:二》电子书
立即下载
云上自动化运维(CloudOps)白皮书
立即下载