基數(shù)排序每一遍對待排數(shù)的某一位進行計數(shù)排序，依次從最低位到最高位。
下面程序把非負數(shù)按16進制處理，每次取16進制的一位。這樣比用10進制方便快捷很多。
缺點是不能處理負數(shù)。可以將所有數(shù)都增加一個基數(shù)所其成為正數(shù)。排序完成后，再減去這個基數(shù)。
但是對于32位最小的負數(shù)1<<31這樣一個特例，是不行的。
用一個中間數(shù)組保存中間結果，每一遍排完后，交換兩指針，這樣可以避免多次數(shù)據(jù)復制。由于一共有8遍，結束后，array中為最后一次排完序的結果。
代碼如下：
void?_radix_sort(int?*src,int?*dst,int?len,int?offset);
int?radix_sort(int?*array,int?begin,int?end)
{
????if(array==NULL||begin>end)?return?0;
????int?len?=?end-begin+1;
????int?*tmp?=?malloc(sizeof(int)*len);
????int?*src,*dst;
????src?=?array;
????dst?=?tmp;
????int?i;
????for(i=0;i<32;i+=4){
????????_radix_sort(src,dst,len,i);
????????tmp?=?src;
????????src?=?dst;
????????dst?=?tmp;
????}
????free(dst);
????return?1;
}
void?_radix_sort(int?*src,int?*dst,int?len,int?offset)
{
????int?cnt[16];
????memset(cnt,0,sizeof(cnt));
????int?mask?=?0xF<<offset;
????int?i=0;
????for(i=0;i<len;++i){
????????cnt[?(src[i]&mask)>>offset?]?++;
????}
????for(i=1;i<16;++i){
????????cnt[i]+=cnt[i-1];
????}
????for(i=len-1;i>=0;--i){
????????dst[--cnt[(src[i]&mask)>>offset]]?=?src[i];?
????}
}