基数排序

维基百科,自由的百科全书
跳转至: 导航搜索
基数排序
分類 排序算法
數據結構 数组
最差時間複雜度 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

参考文献[编辑]