基數(shù)排序每一遍對(duì)待排數(shù)的某一位進(jìn)行計(jì)數(shù)排序，依次從最低位到最高位。
下面程序把非負(fù)數(shù)按16進(jìn)制處理，每次取16進(jìn)制的一位。這樣比用10進(jìn)制方便快捷很多。
缺點(diǎn)是不能處理負(fù)數(shù)?？梢詫⑺袛?shù)都增加一個(gè)基數(shù)所其成為正數(shù)。排序完成后，再減去這個(gè)基數(shù)。
但是對(duì)于32位最小的負(fù)數(shù)1<<31這樣一個(gè)特例，是不行的。
用一個(gè)中間數(shù)組保存中間結(jié)果，每一遍排完后，交換兩指針，這樣可以避免多次數(shù)據(jù)復(fù)制。由于一共有8遍，結(jié)束后，array中為最后一次排完序的結(jié)果。
代碼如下：
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];?
????}
}