基數排序(Radix sort)是一種非比較型整數排序算法，其原理是將整數按位數切割成不同的數字，然后按每個位數分別比較。由于整數也可以表達字符串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用于整數。基數排序的發明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(Tabulation Machine)上的貢獻。
它是這樣實現的：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列。
基數排序時對每一維進行調用子排序算法時要求這個子排序算法必須是穩定的。
基數排序與直覺相反：它是按照從底位到高位的順序排序的。
偽代碼：
RADIX-SORT(A,d)
1 for i <-- 1 to d
2 do use a stable sort to sort array A on digit i
引理8.3： 給定n個d位數，每一個數位可以取k種可能的值，如果所用穩定排序需要Θ(n+k)時間，基數排序能以Θ(d(n+k))的時間完成。
證明：如果采用計數排序這種穩定排序，那么每一遍處理需要時間Θ(n+k)，一共需處理d遍，于是基數排序的運行時間為Θ(d(n+k))。當d為常數，k=O(n)時，有線性運行時間。
注：將關鍵字分成若干位方面，可以有一定的靈活性。
引理8.4：給定n個b位數和任何正整數r<=b，如果采用的穩定排序需要Θ(d(n+k))時間，則RADIX-SORT能在Θ((b/r)(n+2r))時間內正確地對這些數進行排序。
證明：對于一個r<=b,將每個關鍵字看成由d=b/r位組成的數，每一個數字都是(0~ -1)之間的一個整數，這樣就可以采取計數排序。K= ，d=b/r，總的運行時間為Θ((b/r)(n+ ))。
對于給定的n值和b值，如何選擇r值使得最小化表達式(b/r)(n+2r)。如果b< lgn，對于任何r<=b的值，都有(n+2r)=Θ(n)，于是選擇r=b，使計數排序的時間為Θ((b/b)(n+2b)) = Θ(n)。 如果b>lgn，則選擇r=lgn，可以給出在某一常數因子內的最佳時間：當r=lgn時，算法復雜度為Θ(bn/lgn)，當r增大到lgn以上時，分子 增大比分母r快，于是運行時間復雜度為Ω(bn/lgn)；反之當r減小到lgn以下的時候，b/r增大，而n+ 仍然是Θ(n)。
以下引自麻省理工學院算法導論——筆記：
以下代碼實例轉自：http://www.docin.com/p-449224125.html
1 以下是用C++實現的基數排序代碼：
2 #include <cstdio>
3 #include <cstdlib>
4 // 這個是基數排序用到的計數排序，是穩定的。
5 // pDigit是基數數組,nMax是基數的上限，pData是待排序的數組， nLen是待排序數組的元素個數
6 // 必須pDigit和pData的下標相對應的，即pDigit[1]對應pData[1]
7 int RadixCountingSort(int *pDigit, int nMax,int *pData,int nLen){
8 // 以下是計數排序
9 int *pCount = new int[nMax];
10 int *pSorted = new int[nLen];
11 int i,j;
12 for(i=0; i<nMax; ++i)
13 pCount[i] = 0;
14 for(i=0; i<nLen; ++i)
15 ++pCount[pDigit[i]];
16 for(i=1; i<nMax; ++i)
17 pCount[i] += pCount[i-1];
18 for(i=nLen-1; i>=0; --i){
19 --pCount[pDigit[i]];
20 pSorted[pCount[pDigit[i]]] = pData[i]; // z這里注意，是把待排序的數組賦值
21 }
22 for(i=0; i<nLen; ++i)
23 pData[i] = pSorted[i];
24 delete [] pCount;
25 delete [] pSorted;
26 return 1;
27 }
28 int RadixSort(int *pData, int nLen){
29 int *pDigit = new int[nLen]; // 申請存放基數(某個位數)的空間
30 int nRadixBase = 1;
31 bool flag = false;
32 while(!flag){
33 flag = true;
34 nRadixBase *= 10;
35 for(int i=0; i<nLen; ++i){
36 pDigit[i] = pData[i]%nRadixBase; // 求出某位上的數當做基數
37 pDigit[i] /= nRadixBase/10;
38 if(pDigit[i] > 0)
39 flag = false;
40 }
41 if(flag)
42 break;
43 RadixCountingSort(pDigit,10,pData,nLen);
44 }
45 delete[] pDigit;
46 return 1;
47 }
48 main()
49 {
50 int nData[10]={43,65,34,5,8,34,23,0,45,34};;
51 RadixSort(nData, 10);
52 printf("經排序后的數列是：\n");
53 for (int i = 0; i < 10; ++i)
54 printf("%d ", nData[i]);
55 printf("\n");
56 return 0;
57 }
posted on 2012-11-13 16:52
王海光 閱讀(693)
評論(0) 編輯 收藏 引用 所屬分類:
算法