基数排序算法二进制实现

以二进制的方式实现基数排序，该排序算法适用于整数，max_bit为每个机器存储整数的位数,一般为32

假如有这样几个数(二进制表示)：

001000

000100

010000  

100000

每次把位置上带1的往下沉，实现过程：

第1步：不变   

001000

000100

010000  

100000

2：不变

001000

000100

010000  

100000

3：

001000

010000

100000

000100

4:

010000

100000

000100

001000

5:

100000

000100

001000

010000

6:

000100

001000

010000

100000

以下.....

 

/*
 *2008/06/18 By Yao Jianming
 */

#include
#include

void radixsort(int *array, int len)
{
    int max_bit = sizeof(int)*8;
    int count[2];
    int temp[len];
    for(int i=0; i        memset(count, 0, sizeof(count));
        memset(temp, 0, sizeof(temp));
        for(int j=0; j            count[(array[j] >> i) & 1]++;
        }
        count[1] += count[0];
        for(int k=len-1; k>=0; --k) {
            int digit = (array[k] >> i) & 1;
            temp[count[digit]-1] = array[k];
            count[digit]--;
        }
        memcpy(array, temp, sizeof(int)*len);
    }
}

int main()
{
    int data[] = {48, 4, 23, 16, 2, 55, 56, 1};
    radixsort(data, 8);
    for(int i=0; i<8; ++i) {
        printf("%d ", data[i]);
    }
    return 0;
}