基数排序

基数排序是将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，一次进行一次排序。这样从最低位排序一直到最高位排序完成之后，数列就变成一个有序序列

NOTE: 基数排序只能排序非负整数

一、效率

基数排序的时间复杂度为 O(k*n)其中n是排序元素个数，k是数字位数。需要注意的是这个时间复杂度不一定优于 O(n*log_n)

二、实现

基数排序的过程图示如下：

int maxbit( int data[], int size )      //辅助函数，求数据的最大位数
{
    int i;
    //先求出最大数，再求最大数的位数.
    int maxData = data[0];
    for ( i = 1; i < size; ++i )
    {
        if ( data[i] > maxData )
            maxData = data[i];
    }
    i = 1;
    while ( maxData >= 10 )
    {
        maxData /= 10;
        ++i;
    }
    return i;
}

void radix_sort( int data[], int size )
{
    int d = maxbit( data, size );
    //int *temp = (int *)malloc( sizeof(int)*size );
    int temp[size];
    int count[10];                  //计数器
    int i, j, k;
    int radix = 1;
    for ( i = 1; i <= d; i++ )
    {
        for ( j = 0; j < 10; j++ )
            count[j] = 0;               //每次分配前清空计数器

        //(1)
        //将data中第i位为j的个数保存在count[j]中
        for ( j = 0; j < size; j++ )
        {
            k = ( data[j] / radix ) % 10;   //k为data中每个数第i位的数字
            count[k]++;
        }
        //count[j]中保存第i位小于j的数字的个数
        for ( j = 1; j < 10; j++ )
        {
            count[j] = count[j-1] + count[j];
        }
        for ( j = size-1; j >= 0; j-- )
        {
            k = ( data[j] / radix ) % 10;
            //printf( "k = %d, data[%d] = %d\n", k, j, data[j] );
            temp[count[k]-1] = data[j];
            count[k]--;
        }
        //(2)
        for ( j = 0; j < size; j++ )
        {
            //printf( "%d ", temp[j] );
            data[j] = temp[j];
        }
        radix = radix * 10;
    }
}