深入解析Radix Sort基数排序算法思想及C语言实现示例

时间:2021-07-19 08:27:55

基本思想:

将待排数据中的每组关键字依次进行桶分配。
具体示例:

?
1
278、109、063、930、589、184、505、269、008、083

我们将每个数值的个位,十位,百位分成三个关键字: 278 -> k1(个位)=8,k2(十位)=7,k3=(百位)=2。

然后从最低位个位开始(从最次关键字开始),对所有数据的k1关键字进行桶分配(因为,每个数字都是 0-9的,因此桶大小为10),再依次输出桶中的数据得到下面的序列。

?
1
930、063、083、184、505、278、008、109、589、269

再对上面的序列接着进行针对k2的桶分配,输出序列为:

?
1
505、008、109、930、063、269、278、083、184、589

最后针对k3的桶分配,输出序列为:

?
1
008、063、083、109、184、269、278、505、589、930

效率分析:

基数排序的性能比桶排序要略差。每一次关键字的桶分配都需要O(N)的时间复杂度,而且分配之后得到新的关键字序列又需要O(N)的时间复杂度。假如待排数据可以分为d个关键字,则基数排序的时间复杂度将是O(d*2N) ,当然d要远远小于N,因此基本上还是线性级别的。基数排序的空间复杂度为O(N+M),其中M为桶的数量。一般来说N>>M,因此额外空间需要大概N个左右。

但是,对比桶排序,基数排序每次需要的桶的数量并不多。而且基数排序几乎不需要任何“比较”操作,而桶排序在桶相对较少的情况下,桶内多个数据必须进行基于比较操作的排序。因此,在实际应用中,基数排序的应用范围更加广泛。


举例:
假设我们有一些二元组(a,b),要对它们进行以a为首要关键字,b的次要关键字的排序。我们可以先把它们先按照首要关键字排序,分成首要关键字相同的若干堆。然后,在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起,使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。

第二种方式是从最低有效关键字开始排序,称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序,然后对所有的数据按照首要关键字排序。要注意的是,使用的排序算法必须是稳定的,否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序,LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。

通常,基数排序要用到计数排序或者桶排序。使用计数排序时,需要的是Order数组。使用桶排序时,可以用链表的方法直接求出排序后的顺序。下面是一段用桶排序对二元组基数排序的程序:

 

?
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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct data
{
  int key[2];
};
struct linklist
{
  linklist *next;
  data value;
  linklist(data v,linklist *n):value(v),next(n){}
  ~linklist() {if (next) delete next;}
};
void BucketSort(data *A,int N,int K,int y)
{
  linklist *Bucket[101],*p;//建立桶
  int i,j,k,M;
  M=K/100+1;
  memset(Bucket,0,sizeof(Bucket));
  for (i=1;i<=N;i++)
  {
    k=A[i].key[y]/M; //把A中的每个元素按照的范围值放入对应桶中
    Bucket[k]=new linklist(A[i],Bucket[k]);
  }
  for (k=j=0;k<=100;k++)
  {
    for (p=Bucket[k];p;p=p->next) j++;
    for (p=Bucket[k],i=1;p;p=p->next,i++)
      A[j-i+1]=p->value; //把桶中每个元素取出
    delete Bucket[k];
  }
}
void RadixSort(data *A,int N,int K)
{
  for (int j=1;j>=0;j--) //从低优先到高优先 LSD
    BucketSort(A,N,K,j);
}
int main()
{
  int N=100,K=1000,i;
  data *A=new data[N+1];
  for (i=1;i<=N;i++)
  {
    A[i].key[0]=rand()%K+1;
    A[i].key[1]=rand()%K+1;
  }
  RadixSort(A,N,K);
  for (i=1;i<=N;i++)
    printf("(%d,%d) ",A[i].key[0],A[i].key[1]);
  printf("\n");
  return 0;
}

基数排序是一种用在老式穿卡机上的算法。一张卡片有80列,每列可在12个位置中的任一处穿孔。排序器可被机械地"程序化"以检查每一迭卡片中的某一列,再根据穿孔的位置将它们分放12个盒子里。这样,操作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面,第二个位置穿孔的其次,等等。

对于一个位数有限的十进制数,我们可以把它看作一个多元组,从高位到低位关键字重要程度依次递减。可以使用基数排序对一些位数有限的十进制数排序。