基本思想：

將待排數(shù)據(jù)中的每組關(guān)鍵字依次進(jìn)行桶分配。
具體示例：

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

我們將每個(gè)數(shù)值的個(gè)位，十位，百位分成三個(gè)關(guān)鍵字： 278 -> k1(個(gè)位)=8，k2(十位)=7，k3=(百位)=2。

然后從最低位個(gè)位開始(從最次關(guān)鍵字開始)，對(duì)所有數(shù)據(jù)的k1關(guān)鍵字進(jìn)行桶分配(因?yàn)?，每個(gè)數(shù)字都是 0-9的，因此桶大小為10)，再依次輸出桶中的數(shù)據(jù)得到下面的序列。

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

再對(duì)上面的序列接著進(jìn)行針對(duì)k2的桶分配，輸出序列為：

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

最后針對(duì)k3的桶分配，輸出序列為：

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

效率分析：

基數(shù)排序的性能比桶排序要略差。每一次關(guān)鍵字的桶分配都需要O(N)的時(shí)間復(fù)雜度，而且分配之后得到新的關(guān)鍵字序列又需要O(N)的時(shí)間復(fù)雜度。假如待排數(shù)據(jù)可以分為d個(gè)關(guān)鍵字，則基數(shù)排序的時(shí)間復(fù)雜度將是O(d*2N) ，當(dāng)然d要遠(yuǎn)遠(yuǎn)小于N，因此基本上還是線性級(jí)別的?；鶖?shù)排序的空間復(fù)雜度為O(N+M)，其中M為桶的數(shù)量。一般來說N>>M，因此額外空間需要大概N個(gè)左右。

但是，對(duì)比桶排序，基數(shù)排序每次需要的桶的數(shù)量并不多。而且基數(shù)排序幾乎不需要任何“比較”操作，而桶排序在桶相對(duì)較少的情況下，桶內(nèi)多個(gè)數(shù)據(jù)必須進(jìn)行基于比較操作的排序。因此，在實(shí)際應(yīng)用中，基數(shù)排序的應(yīng)用范圍更加廣泛。

舉例：
假設(shè)我們有一些二元組(a,b)，要對(duì)它們進(jìn)行以a為首要關(guān)鍵字，b的次要關(guān)鍵字的排序。我們可以先把它們先按照首要關(guān)鍵字排序，分成首要關(guān)鍵字相同的若干堆。然后，在按照次要關(guān)鍵值分別對(duì)每一堆進(jìn)行單獨(dú)排序。最后再把這些堆串連到一起，使首要關(guān)鍵字較小的一堆排在上面。按這種方式的基數(shù)排序稱為MSD(Most Significant Dight)排序。

第二種方式是從最低有效關(guān)鍵字開始排序，稱為LSD(Least Significant Dight)排序。首先對(duì)所有的數(shù)據(jù)按照次要關(guān)鍵字排序，然后對(duì)所有的數(shù)據(jù)按照首要關(guān)鍵字排序。要注意的是，使用的排序算法必須是穩(wěn)定的，否則就會(huì)取消前一次排序的結(jié)果。由于不需要分堆對(duì)每堆單獨(dú)排序，LSD方法往往比MSD簡(jiǎn)單而開銷小。下文介紹的方法全部是基于LSD的。

通常，基數(shù)排序要用到計(jì)數(shù)排序或者桶排序。使用計(jì)數(shù)排序時(shí)，需要的是Order數(shù)組。使用桶排序時(shí)，可以用鏈表的方法直接求出排序后的順序。下面是一段用桶排序?qū)ΧM基數(shù)排序的程序：

#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中的每個(gè)元素按照的范圍值放入對(duì)應(yīng)桶中
    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; //把桶中每個(gè)元素取出
    delete Bucket[k];
  }
}
void RadixSort(data *A,int N,int K)
{
  for (int j=1;j>=0;j--) //從低優(yōu)先到高優(yōu)先 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;
}

基數(shù)排序是一種用在老式穿卡機(jī)上的算法。一張卡片有80列，每列可在12個(gè)位置中的任一處穿孔。排序器可被機(jī)械地"程序化"以檢查每一迭卡片中的某一列，再根據(jù)穿孔的位置將它們分放12個(gè)盒子里。這樣，操作員就可逐個(gè)地把它們收集起來。其中第一個(gè)位置穿孔的放在最上面，第二個(gè)位置穿孔的其次，等等。

對(duì)于一個(gè)位數(shù)有限的十進(jìn)制數(shù)，我們可以把它看作一個(gè)多元組，從高位到低位關(guān)鍵字重要程度依次遞減?？梢允褂没鶖?shù)排序?qū)σ恍┪粩?shù)有限的十進(jìn)制數(shù)排序。

最新評(píng)論