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

概述基本思想：将待排数据中的每组关键字依次进行桶分配。具体示例：278、109、063、930、589、184、505、269、008、083

基本思想：

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

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

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

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

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

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

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

最后针对k3的桶分配，输出序列为：

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数组。使用桶排序时，可以用链表的方法直接求出排序后的顺序。下面是一段用桶排序对二元组基数排序的程序：

#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,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 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,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个盒子里。这样， *** 作员就可逐个地把它们收集起来。其中第一个位置穿孔的放在最上面，第二个位置穿孔的其次，等等。

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

总结

以上是内存溢出为你收集整理的深入解析Radix Sort基数排序算法思想及C语言实现示例全部内容，希望文章能够帮你解决深入解析Radix Sort基数排序算法思想及C语言实现示例所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。