[聲明] 本文引用與：
GameRes 游戲開發(fā)網(wǎng)一.引言
前一段在http://www.allaboutprogram.com/上看到有關(guān)于排序方法的時間復(fù)雜度的研究，說的是在一般情況下，最好的時間復(fù)雜度是 O( n*LOG(n) )， 而在特定的情況下，比如要排序的數(shù)據(jù)是整數(shù)，而且比較集中，也可以簡化為 O(n)。
后來我也給abp寫了封信，說明了一下對于一般的整數(shù)（int 或者unsigned int），也可以進行復(fù)雜度為 O(n)的排序。我后來給了他一個我寫的STL的版本，實現(xiàn)了復(fù)雜度為O(n)的int排序。但實測起來，至少在n = 1000*1024的時候，還是比STL的sort 要慢。
應(yīng)abp的要求，我寫了這篇文章，作為復(fù)雜度為O(n)的這種排序 ---- Radix Sort的介紹。今天，我在網(wǎng)上找到一小段代碼，和我寫的幾乎一樣，不過沒有用STL，實測性能在n =1024*1000的時候，VC 6 上 release 模式，排序時間：(tick)
n Radix Sort STL Sort
100*1024 20 20
1000*1024 250 320
4000*1024 991 1513
10000*1024 2093 3606
圖一是一張曲線圖，可見Radix Sort 的確可能比STL Sort 快，而且，因為Radix Sort時間復(fù)雜度小，在更長的時間內(nèi)表現(xiàn)更為充分。這一點，在曲線圖里看得很清楚。n 從100* 1024增長到10000*1024， 排序時間也從20 增長到2093， 可以看出的確是O(n)的。
下面介紹一下Radix Sort 的算法。
二． Radix Sort 的簡單算法
考慮一種簡單情況，如果你給一些unsigned char 排序，除了教科書上的很多方法外，還有一種簡單的。可以這樣考慮。試想排一系列的unsigned char, 值從0~ 255 ， 放在 u_char data_array[ARRAY_SIZE] 中，分配一個數(shù)組 u_char membuffer[255];
for(int i=0;i<255;i++)
membuffer[i]=0;
for(int i=0;i<ARRAY_SIZE;i++)
membuffer[data_array[i]]++;
這樣，就把數(shù)字填到了membuffer內(nèi)部，然后，比如這個是輸出的數(shù)組
u_char sorted_array[ARRAY_SIZE];
int k=0;
for(int i=0;i<255;i++)
for(int j=0;j<membuffer[i]; j++)
sorted_array[k++]=i;
圖例：在256個entry的數(shù)組中，可能產(chǎn)生一系列的重復(fù)值。如下：
每個entry中實際并不記錄值，而是記錄重復(fù)的次數(shù)。
1 3 4 5 7 
1 4
4
這樣，就把n = ARRAY_SIZE 的unsigned char 進行了排序。
三.擴展到int 的排序
那么，如何擴展到對于一般的整數(shù)進行排序呢？可以這樣考慮。一個 int,是由 ４個 char 組成（在32-bit int的系統(tǒng)上）在 Little Endian 字節(jié)順序（ Least Siginficant Byte first , 比如 80x86架構(gòu) ）下， <- low memory address high memory address ->
char 0 char 1 char 2 char 3
如果是 0x12345678 那么
char 0 就是 0x78
char 1 就是 0x56
char 2 就是 0x34
char 3 就是 0x12
如果我們用最低位字節(jié) （char 0）來作為 sort key對int 排序，然后使用次低做sort key, 然后用次高，最后用最高字節(jié)排序，實際的結(jié)果就是對整個int 進行了排序。
下面的a, b, c, d指int 的不同char, 讓我們進行一下升序排序(ascending sort)
abcd
bacd
dcba
caba
bbac
首先用最低位字節(jié)排序：
dcba
caba
bbac
abcd
bacd
然后用次低位：
bbac
dcba
caba
abcd
bacd
使用次高位：
caba
bacd
bbac
abcd
dcba
然后使用最高位字節(jié)排序：
abcd
bacd
bbac
caba
dcba
于是經(jīng)過四次排序，就得到了一個升序的int排序。
為了方便理解, 給出一個排int 的實際算法 ，這是我寫的STL版本的Radix Sort ,可以 排任意多int，實際內(nèi)存占用并不太多。（沒有用2^32 的可怕的內(nèi)存量）
using namespace std;
typedef vector <int> HASH;
typedef unsigned char u_char;
HASH hashtable[256]; //256 entries hash table
const int array_size=1024*4000;
void SortInt( int * data, int size);
void SortIntByChar(int * data, int size, int pos);
inline u_char GetHashvalue( int value, int pos)
{
return ((u_char*)&value)[pos];
}
void SortIntByChar(int * data, int size, int pos)
{
int i;
//clear hashtable
for(i=0;i<256; ++i)
{
hashtable[i].clear();
}
//add into hash table
for(i=0;i< size; ++i)
{
hashtable[GetHashvalue(data[i], pos)].push_back(data[i]);
}
//output int
int k=0;
if(pos!=3)
{
for(i=0;i< 256; ++i)
{
for(int j=0;j< hashtable[i].size(); ++j)
{
data[k++]=hashtable[i][j];
}
}
}
else //most significant byte
{
for(i=128;i< 256; ++i)
{
for(int j=0;j< hashtable[i].size(); ++j)
{
data[k++]=hashtable[i][j];
}
}
for(i=0;i< 128; ++i)
{
for(int j=0;j< hashtable[i].size(); ++j)
{
data[k++]=hashtable[i][j];
}
}
}
}
void SortInt( int * data, int size)
{
SortIntByChar(data, size, 0);
SortIntByChar(data, size, 1);
SortIntByChar(data, size, 2);
SortIntByChar(data, size, 3);
}
這里的方法，和前面說的最簡單的并沒有太大不同，不同的是，因為int是無法裝入char的數(shù)組的，所以，使用了一個vector<int> ，為256個entry中的任何一個。這樣，就把int的值裝入了。
經(jīng)過測試，這個效果并不太好，對于n=1000*1024下為500 ticks ，比 STL Sort 的 320 ticks要慢。那么，前面的250 ticks 如何得來的呢？這就是有關(guān)優(yōu)化的問題。使用了STL，所以慢。因為在 clear() 和push_back（）中，作了過多你在這里不關(guān)心的事情。這里給出上面測試用的快速版本，未使用STL
void radix (int byte, long N, const long *source, long *dest)
{
long count[256];
long index[256];
memset (count, 0, sizeof (count));
for ( int i=0; i<N; ++i ) ++count[((source[i])>>(byte*8))&0xff];
if(byte!=3)
{
index[0]=0;
for ( i=1; i<256; ++i ) index[i]=index[i-1]+count[i-1];
}
else
{
index[128]=0;
for ( i=128+1; i<256; ++i ) index[i]=index[i-1]+count[i-1];
index[0]=index[255]+count[255];
for ( i=1; i<128; ++i ) index[i]=index[i-1]+count[i-1];
}
for ( i=0; i<N; ++i ) dest[index[((source[i])>>(byte*8))&0xff]++] = source[i];
}
void radixsort (long *source, long *temp, long N)
{
radix (0, N, source, temp);
radix (1, N, temp, source);
radix (2, N, source, temp);
radix (3, N, temp, source);
}
不同的是，他多用了一個index數(shù)組來記錄每一個entry的開始的對應(yīng)于全體數(shù)據(jù)的index. 這樣，就不必使用STL 的vector。
這個版本的作者是Nils Pipenbrinck aka ，是我從網(wǎng)上找到的，本來是排unsigned long的，被我改成了 signed long 。
四.擴展到float 的排序
圖二是IEEE 754 規(guī)范中單精度 float的格式：即VC 中的float。
在這里只討論float，不討論double。最高位(bit 31) 是符號位，如果為1，則表示為負，為0則為非負。Exp 有8位，是表示指數(shù)部分的，Significand 是小數(shù)部分。在把十進制表示的浮點數(shù)生成IEEE754各部分的時候，還有一些normalize 等操作，比較麻煩。因為這里主要討論排序，所以不仔細說了。
但有幾點可以這樣看：
負數(shù)小于正數(shù)，正數(shù)的絕對值越大值越大，負數(shù)相反。對于正數(shù)，指數(shù)大的肯定大。相同的指數(shù)，尾數(shù)大的更大。這樣，也可以強行比較字節(jié)，從低字節(jié)開始比。可是第三個字節(jié)的最高位(bit23)有1位實際上是exp的最低位。
可以這樣想，假設(shè) A 和B 是兩個正的float，A. bit 23代表A的第23位，那么：
那么，把指數(shù)的最低位放到和尾數(shù)一起組成的字節(jié)比較仍然可以比出浮點數(shù)的大小來。最后一次比較，最高字節(jié)的最高位是符號位。這可以特別處理。所以，比較浮點數(shù)和比較int 并沒有太大的不同，就是有些符號處理的問題要注意。
Pierre Terdiman 給出了排序float的算法。測試結(jié)果和STL排序float比較一下，如下：
N Radix Sort (float) STL Sort (float)
100*1024 30 30
1000*1024 641 431
4000*1024 2334 1903
10000*1024 5788 5498
（圖三）
可以看出，至少在n=10000*1024的范圍里，Pierre Terdiman 的Radix Sort 方法還是比 STL sort 要慢。但我測了一下Pierre Terdiman 的int 排序，也是比STL sort慢。推測可能是他的算法優(yōu)化不夠。從道理上講，的確是O(n) 的復(fù)雜度，就是N 不是充分大的時候體現(xiàn)不出來。
我曾看過在一個Nvidia 的工具的source code，據(jù)稱是最好的float 排序，但現(xiàn)在不在手邊。等我找到了也加上來。不同的source code的算法倒是基本上一樣，就是優(yōu)化的程度不同。但小小的優(yōu)化帶來的結(jié)果也可能是顯著的。
五．源代碼和參考資料
列出我寫的整數(shù)排序方法，
Nils Pipenbrinck aka 的整數(shù)排序方法,
和 Pierre Terdiman的整數(shù)和浮點排序方法。
“Radix Sort Tutorial” by Nils：http://www.allaboutprogram.com/RadixSortRevisited.mht
“Radix Sort Revisited” by Pierre Terdiman：http://www.allaboutprogram.com/RadixSortTutorial.mht