[基础算法复习]基数排序


基数排序每一遍对待排数的某一位进行计数排序,依次从最低位到最高位。
下面程序把非负数按16进制处理,每次取16进制的一位。这样比用10进制方便快捷很多。
缺点是不能处理负数。可以将所有数都增加一个基数所其成为正数。排序完成后,再减去这个基数。
但是对于32位最小的负数1<<31这样一个特例,是不行的。
用一个中间数组保存中间结果,每一遍排完后,交换两指针,这样可以避免多次数据复制。由于一共有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]; 
    }
}



posted on 2009-07-17 19:49 YZY 阅读(416) 评论(0)  编辑 收藏 引用 所属分类: Algorithm基础算法


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2009年7月>
2829301234
567891011
12131415161718
19202122232425
2627282930311
2345678

统计

常用链接

留言簿(2)

随笔分类

随笔档案

搜索

积分与排名

最新评论

阅读排行榜