算法---8.基数排序

1. 基数排序



1.2 代码

#include <stdio.h>
#include <stdlib.h>
#define dbmsg(fmt, args ...) printf("%s:%s[%d]: "fmt"\n", __FILE__,__FUNCTION__, __LINE__,##args)
int dump_array(int* arr, int len)
{
    int i;
    for(i=0; i<len; i++)
    {
        printf("%d=0x%x ", arr[i], arr[i]);
    }
    printf("\n");
    return 0;
}
int get_position_num(int data,int pos)
{
    return( (data>>(4*(pos-1)))&0xF );
}
#define BUCKET_NUM 16
#define INT_BITS   32 //int 32bits 32/4
void radix_sort(int* arr, int len)
{
    int i,j, k, num_pos;
    int num, index;
    int *bucket[BUCKET_NUM];
    for(i=0; i<BUCKET_NUM; i++)
    {
        bucket[i] = (int *)malloc(sizeof(int) * (len + 1));   //一共16个bucket，每个bucket的大小是len,所以占用16*len个空间
        bucket[i][0] = 0;                             //bucket[i][0]代表这个下标的数据的个数
    }
    for(num_pos=1; num_pos<=INT_BITS/4; num_pos++) //32位int最大是0xFFFF FFFF, 8个F,所以要排8次
    {
        for (i=0; i<len; i++)                      //分配过程
        {
            num = get_position_num(arr[i], num_pos);
            printf("num=%d  ", num);
            index = ++bucket[num][0];
            bucket[num][index] = arr[i];
        }
        printf("\n");

        for(i=0, j=0; i<BUCKET_NUM; i++)              //收集
        {
            for (k=1; k<=bucket[i][0]; k++)           //将桶中的数据按下标由小到大，
                arr[j++] = bucket[i][k];
            bucket[i][0] = 0; //复位
        }
        dump_array(arr, len);
    }
    for (i=0; i<BUCKET_NUM; i++)
    {
        if(NULL != bucket[i])
            free(bucket[i]);
    }
}

int main ( int argc, char *argv[] )
{
    //int arr[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int arr[] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4, 0x321, 0x4321, 0x54321, 0x123, 0x1234, 0x12345};
    int len = sizeof(arr)/sizeof(int);
    dbmsg("array len=%d", len);
    dump_array(arr, len);
    radix_sort(arr, len);
    printf("after merge sort\n");
    dump_array(arr, len);
    return EXIT_SUCCESS;
}

注: 为什么需要分配一次收集一次呢？
    第1次将个位数
    第2次 对于同一个bucket来说个位数小的先进入bucket,个位数大的后进入bucket,
              所以对于这一个bucket来说，十位数相同，个位数是从小到大
     第3次 对于这一个bucket来说，百位数相同，剩余的两位由小到大
    .....
    最后    对于这一个bucket来说，最高位数相同，剩余的位数由小到大
  把bucket输出不就是有序的数了嘛。

第一趟以第1个F为基数进行排序

0
1   49=0x31 65=0x41 97=0x61 49=0x31
2
3
4   4=0x4
5
6   38=0x26
7   55=0x37
8
9
A
B   27=0x1b
C   76=0x4c
D   13=0xd
E
F

第二趟以第2个F为基数进行排序

0  4=0x4  13=0xd
1  27=0x1b
2  38=0x26
3  49=0x31 49=0x31  55=0x37   -->此时就能保证个位数有序
4  65=0x41 76=0x4c
5
6  97=0x61
7
8
9
A
B
C
D
E
F

1.4 代码打包
 8radix.rar(下载后改名为8radix.tar.gz)