基数排序

2021-09-20 14:12:22

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

目录

  1. 1 基本解法
  2. ▪ 第一步
  3. ▪ 第二步
  4. ▪ 第三步
  5. 2 效率分析
  6. 3 实现方法
  1. 4 实现原理
  2. 5 实现
  3. ▪ C语言
  4. ▪ Java语言
  5. ▪ pascal
  6. ▪ c++
  1. ▪ C# 实现基数排序
  2. ▪ python 实现
  3. 6 AAuto
  4. ▪ 第一步
  5. ▪ 第二步
  6. ▪ 第三步
  1. ▪ 第四步
  2. ▪ 第五步
  3. ▪ 第六步
  4. ▪ 第七步

基本解法

第一步

以LSD为例，假设原来有一串数值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中：
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
接着再进行一次分配，这次是根据十位数来分配：
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 =
        {73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100};
        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 i 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为基数"""
    K = int(math.ceil(math.log(max(a), radix))) # 用K位数可表示任意整数
    bucket = [[] for i in range(radix)] # 不能用 [[]]*radix
    for i 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 i in range(radix)]

上一篇：阿里云云数据库RDS如何监控、备份及克隆实例？


下一篇：git bash各种乱码问题,已解决