基数排序

维基百科,自由的百科全书
跳转至: 导航搜索
基数排序
分類 排序算法
數據結構 数组
最差時間複雜度 O(kN)
最差空間複雜度 O(kN)

基数排序英语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的大小取决于数字位的选择(比如比特位数),和待排序数据所属数据类型的全集的大小;k决定了进行多少轮处理,而n是每轮处理的操作数目。

以排序n个不同整数来举例,假定这些整数以B为底,这样每位数都有B个不同的数字,k = logB(N),N是待排序数据类型全集的势。虽然有B个不同的数字,需要B个不同的桶,但在每一轮处理中,判断每个待排序数据项只需要一次计算确定对应数位的值,因此在每一轮处理的时候都需要平均n次操作来把整数放到合适的桶中去,所以就有:

  • k约等于logB(N)

所以,基数排序的平均时间T就是:

T~= logB(Nn

其中前一项是一个与输入数据无关的常数,当然该项不一定小于logn

如果考虑和比较排序进行对照,基数排序的形式复杂度虽然不一定更小,但由于不进行比较,因此其基本操作的代价较小,而且在适当选择的B之下,k一般不大于logn,所以基数排序一般要快过基于比较的排序,比如快速排序。

C++[编辑]

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 = new int[n];
    int *count = new int[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[编辑]

#include<stdio.h>
#define MAX 20
//#define SHOWPASS
#define BASE 10
 
void print(int *a, int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf("%d\t", a[i]);
  }
}
 
void radixsort(int *a, int n) {
  int i, b[MAX], m = a[0], exp = 1;
 
  for (i = 1; i < n; i++) {
    if (a[i] > m) {
      m = a[i];
    }
  }
 
  while (m / exp > 0) {
    int bucket[BASE] = { 0 };
 
    for (i = 0; i < n; i++) {
      bucket[(a[i] / exp) % BASE]++;
    }
 
    for (i = 1; i < BASE; i++) {
      bucket[i] += bucket[i - 1];
    }
 
    for (i = n - 1; i >= 0; i--) {
      b[--bucket[(a[i] / exp) % BASE]] = a[i];
    }
 
    for (i = 0; i < n; i++) {
      a[i] = b[i];
    }
 
    exp *= BASE;
 
#ifdef SHOWPASS
    printf("\nPASS   : ");
    print(a, n);
#endif
  }
}
 
int main() {
  int arr[MAX];
  int i, n;
 
  printf("Enter total elements (n <= %d) : ", MAX);
  scanf("%d", &n);
  n = n < MAX ? n : MAX;
 
  printf("Enter %d Elements : ", n);
  for (i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }
 
  printf("\nARRAY  : ");
  print(&arr[0], n);
 
  radixsort(&arr[0], n);
 
  printf("\nSORTED : ");
  print(&arr[0], n);
  printf("\n");
 
  return 0;
}

VB[编辑]

Sub Main()
        Dim data() As Integer = {69, 55, 4, 50, 47, 63, 28, 20, 132, 56, 3, 27, 12, 10, 96, 125, 1034}
        Radix_Sort(data)
        OutputArray(data)
        Console.ReadLine()
    End Sub
 
    Private Sub Radix_Sort(ByRef data() As Integer)
        Dim Max As Integer = data(0)        '存储数组中最大的数字,以获取最大位数’
        Dim m As Integer = 1                '存储当前处理的基数,1表示个位,10表示十位,以此类推’
        Dim Length As Integer = data.Length
        '获取数组最大值’
        For i As Integer = 1 To Length - 1
            If data(i) > Max Then Max = data(i)
        Next
        While Max \ m > 0
            '计数排序计数器’
            Dim Counting(0 To 9) As Integer
            '辅助空间,用于存放计数排序的结果’
            Dim b(Length - 1) As Integer
            '下面是计数排序的三个循环,请参考计数排序’
            For i As Integer = 0 To Length - 1
                Counting((data(i) \ m) Mod 10) = Counting((data(i) \ m) Mod 10) + 1
            Next
            For i As Integer = 1 To Counting.Length - 1
                Counting(i) = Counting(i) + Counting(i - 1)
            Next
            For i As Integer = Length - 1 To 0 Step -1
                b(Counting((data(i) \ m) Mod 10) - 1) = data(i)
                Counting((data(i) \ m) Mod 10) = Counting((data(i) \ m) Mod 10) - 1
            Next
            '从辅助数组中取回结果’
            For i As Integer = 0 To Length - 1
                data(i) = b(i)
            Next
            '基数向前移1位’
            m = m * 10
        End While
    End Sub
 
    Private Sub OutputArray(Data() As Integer)
        For i As Integer = 0 To Data.Length - 1
            Console.Write(Data(i) & ",")
        Next
    End Sub

VBA[编辑]

Sub Radix_Sort()
    Dim data() As Variant
    data = Array(69, 55, 4, 50, 47, 63, 28, 20, 934, 132, 56, 3, 27, 12, 10, 96, 125)
    Dim Max As Integer
    Max = data(0)        '存储数组中最大的数字,以获取最大位数
    Dim m As Integer
    m = 1                '存储当前处理的基数,1表示个位,10表示十位,以此类推
    Dim Length As Integer
    Length = UBound(data) '有17个数字,但这个Length的值其实是16,因为UBound是得到数列中最后那个数的下标,而VBA数列是从0开始标的。
    Dim x As Integer      '提取出需要比较的那一位上的数字,后文赋值时有详细解释。The value of the digit to be compared in the number.
 
    '获取数组最大值:
    For i = 1 To Length
        If data(i) > Max Then Max = data(i)
    Next
 
    Do While Max \ m > 0    '反斜杠“\”表示先做除法,再取商中的整数部分。
        Dim Counting(0 To 9) As Integer
        '声明Counting(),用来存放每个数字在某一位上出现的次数。比如当m=1时,counting(0)=3说明在原数组中有3个数的个位数是0。
 
        For i = 0 To 9
            Counting(i) = 0
        Next i
        '该循环每运行一次,也就是m的值每变化一次,counting()都要归零。
        '否则等到m=10的时候,coungting()还存着个位上各个数字的出现的次数,下面的循环就直接把十位数的出现次数加上去了
 
        'Loop A,给Counting()赋值。用来统计在个位、十位、百位…上,各个数字出现的次数:
        For i = 0 To Length
            x = (data(i) \ m) Mod 10
            '(data(i) \ m) Mod 10 得出的是data(i)在某一位上的数字。Mod为求余数。
            '比如,在m=10, data(16)=125的情况下,(data(0)\m) Mod 10 = 125/10,取商的整数部分,为12,再除以10,余数为2,这个2就是125十位上的数字。
            '所以Mod 10用来提取个位数上的数字,\m用来把想要提取的十位、百位等变成个位。
 
            Counting(x) = Counting(x) + 1
            '每碰到一个被排序位数上为x的数字,counting(x)+1。比方说整个数组中一共有3个数个位数为1,那么在m=1时,就会运行三次counting(1)=coungting(1)+1。
            '因为counting()数组中的数初始值都是0,所以如此运行三次,coungting(1)就会等于0+1+1+1=3.
 
            '输出此循环的计算过程:
            Debug.Print "Loop A: i = " & i & _
            "; m = " & m & _
            "; data(i) = " & data(i) & _
            "; (data(i)\m) Mod 10 = " & x & _
            "; Counting(" & x & ") = " & Counting(x)
        Next
 
        'Loop B,用来为Loop C做准备,后文有解释:
        For i = 1 To UBound(Counting)
            '输出此循环的计算过程:
            Debug.Print "Loop B: Counting(" & i & ") = " & Counting(i) & "; " & "Counting(" & i - 1 & ") = " & Counting(i - 1) & _
            "; " & "Counting(" & i & ") = " & Counting(i) + Counting(i - 1)
            'Counting()进行累加:
            Counting(i) = Counting(i) + Counting(i - 1)
        Next
 
        Dim b() As Integer
        '声明木桶:b(),用来按照个位、十位上的数字存被排序的数组中的数字。比如m=1时,b(0)用来存放个位数是0的数字。
        '但是因为b(0)只能存放一个数字,所以如果有3个数字个位是0,也就是counting(0)=3的情况下,b(0),b(1),b(2)都会被用来存放个位数是0的数字。
        '那么这时候,个位数为1的数字只能排在他们后面,所以个位数为1的数字就要从b(3)开始存放。所以这就是Loop B的作用,算出每个数字该存放在哪个木桶里。
        '在经过Loop B累加之后,counting(1)=counting(0)+counting(1) = 3 + 0 = 3,表示个位数为1的数字最多存放到b(2),从b(3)开始存放counting(3)。
        '而counting(2)从原来的2变成了5,表示个位数为2的数字可以存放在b(3)和b(4),从b(5)开始存放个位数为3的数字。
 
        ReDim b(Length)
        '不直接Dim b(Length) As Integer是因为VBA不支持。直接Dim b()括号中必须是一个常数,不能为变量。
 
        'Loop C,把数字放入桶内:
        For i = Length To 0 Step -1
            '重新给x赋值,让x随着此循环内i的变化而变化:
            x = (data(i) \ m) Mod 10
 
            '输出此循环的计算过程:
            Debug.Print "Loop C: i=" & i & _
            "; m=" & m & _
            "; data(" & i & ")=" & data(i) & _
            "; (data(" & i & ")\" & m & ") Mod 10 = " & x & _
            "; Counting(" & x & ") = " & Counting(x) & _
            "; b(" & (Counting(x) - 1) & ") = " & "data(" & i & ") = " & data(i)
 
            b(Counting(x) - 1) = data(i)
            '把data(i)放入相应的桶中。Counting(x)需要-1是因为x最多放到Counting(x)-1这个桶,Counting(x)是给x+1放的。详见前文的例子。
 
            Counting(x) = Counting(x) - 1
            '此捅已用过,下一次再碰到个位数、十位数…一样的数字,用小一号的桶。详见前文的举例
        Next
 
        For i = 0 To Length
            '从桶中取回结果:
            data(i) = b(i)
            '输出此轮排序结果:
            Debug.Print "Loop D: data(" & i & ") = "; "bi(" & i & ") ="; b(i)
        Next
        '基数向前移1位’
        m = m * 10
    Loop
End Sub

Python[编辑]

#!/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)]

参考文献[编辑]