基數(shù)排序(Radix sort)是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達(dá)字符串（比如名字或日期）和特定格式的浮點(diǎn)數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。基數(shù)排序的發(fā)明可以追溯到1887年赫爾曼·何樂禮在打孔卡片制表機(jī)(Tabulation Machine)上的貢獻(xiàn)。
它是這樣實(shí)現(xiàn)的：將所有待比較數(shù)值（正整數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補(bǔ)零。然后，從最低位開始，依次進(jìn)行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列。
基數(shù)排序時對每一維進(jìn)行調(diào)用子排序算法時要求這個子排序算法必須是穩(wěn)定的。
基數(shù)排序與直覺相反：它是按照從底位到高位的順序排序的。
偽代碼：
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位數(shù)，每一個數(shù)位可以取k種可能的值，如果所用穩(wěn)定排序需要Θ(n+k)時間，基數(shù)排序能以Θ(d(n+k))的時間完成。
證明：如果采用計(jì)數(shù)排序這種穩(wěn)定排序，那么每一遍處理需要時間Θ(n+k)，一共需處理d遍，于是基數(shù)排序的運(yùn)行時間為Θ(d(n+k))。當(dāng)d為常數(shù)，k=O(n)時，有線性運(yùn)行時間。
注：將關(guān)鍵字分成若干位方面，可以有一定的靈活性。
引理8.4：給定n個b位數(shù)和任何正整數(shù)r<=b，如果采用的穩(wěn)定排序需要Θ(d(n+k))時間，則RADIX-SORT能在Θ((b/r)(n+2r))時間內(nèi)正確地對這些數(shù)進(jìn)行排序。
證明：對于一個r<=b,將每個關(guān)鍵字看成由d=b/r位組成的數(shù)，每一個數(shù)字都是(0~ -1)之間的一個整數(shù)，這樣就可以采取計(jì)數(shù)排序。K= ，d=b/r，總的運(yùn)行時間為Θ((b/r)(n+ ))。
對于給定的n值和b值，如何選擇r值使得最小化表達(dá)式(b/r)(n+2r)。如果b< lgn，對于任何r<=b的值，都有(n+2r)=Θ(n)，于是選擇r=b，使計(jì)數(shù)排序的時間為Θ((b/b)(n+2b)) = Θ(n)。 如果b>lgn，則選擇r=lgn，可以給出在某一常數(shù)因子內(nèi)的最佳時間：當(dāng)r=lgn時，算法復(fù)雜度為Θ(bn/lgn)，當(dāng)r增大到lgn以上時，分子 增大比分母r快，于是運(yùn)行時間復(fù)雜度為Ω(bn/lgn)；反之當(dāng)r減小到lgn以下的時候，b/r增大，而n+ 仍然是Θ(n)。
以下引自麻省理工學(xué)院算法導(dǎo)論——筆記：
以下代碼實(shí)例轉(zhuǎn)自：http://www.docin.com/p-449224125.html
1 以下是用C++實(shí)現(xiàn)的基數(shù)排序代碼：
2 #include <cstdio>
3 #include <cstdlib>
4 // 這個是基數(shù)排序用到的計(jì)數(shù)排序，是穩(wěn)定的。
5 // pDigit是基數(shù)數(shù)組,nMax是基數(shù)的上限，pData是待排序的數(shù)組， nLen是待排序數(shù)組的元素個數(shù)
6 // 必須pDigit和pData的下標(biāo)相對應(yīng)的，即pDigit[1]對應(yīng)pData[1]
7 int RadixCountingSort(int *pDigit, int nMax,int *pData,int nLen){
8 // 以下是計(jì)數(shù)排序
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這里注意，是把待排序的數(shù)組賦值
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]; // 申請存放基數(shù)(某個位數(shù))的空間
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; // 求出某位上的數(shù)當(dāng)做基數(shù)
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("經(jīng)排序后的數(shù)列是：\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) 編輯 收藏 引用 所屬分類:
算法