频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
排序算法系列:基数排序(Radix sort)(C语言)
2012-11-08 09:11:27      个评论      
收藏   我要投稿
通俗理解:结合计数排序,通过对待排数组中元素每一位进行排序,最终达到对整个数组排序的效果。观看动态过程
[cpp] 
#include <stdio.h> 
#include <stdlib.h> 
#define MAXK 10 
int get_int(void); 
int count_sort (int*array,int n,int d); 
int get_value(int a,int d); 
void radix_sort(int* a,int n,int d); 
 
//测试 
int  
main() 

    int n = 12; 
    int p[12] = {1234,3123,2539,5958,4365,3352,6654,7214,7684,9351,4685,3325}; 
    radix_sort(p,n,3); 
    for (int i=0;i<n;i++) 
        printf("%d ",p[i]); 
    return 0; 

 
//基数排序 
void 
radix_sort(int* a,int n,int d) 

    for (int i=0;i<=d;i++) 
        count_sort(a,n,i); 

 
int  
count_sort (int *array, int n,int d)   
{   
    printf("%d\n",d); 
    int k[MAXK] = {0};   
    int * temp,*b;   
    int i;     
    temp = (int *) malloc (sizeof (int)*n);  
    b = (int *) malloc (sizeof (int)*n);     
    if (NULL == temp) 
        return 0 ; 
    for (i=0;i<n;i++) 
        b[i] = get_value(array[i],d); 
    //显示b数组 
    for (i=0;i<n;i++) 
        printf("%d ",b[i]); 
    printf("\n"); 
    for (i = 0; i < n; i++)  
        k[b[i]]++;//记录与数组下标相等的数值的个数 
    //显示k数组 
    for (i=0;i<10;i++) 
        printf("%d ",k[i]); 
    printf("\n"); 
    for (i=1;i<10;i++) 
        k[i]+=k[i-1];//储存自己数组下标数值在目标数组对应的位置 
    for (i=n-1;i>=0;i--)   
        temp[--k[b[i]]]=array[i]; //将原数组按大小顺序储存到另一个数组  
    //显示temp数组 
    for (i=0;i<n;i++) 
        printf("%d ",temp[i]); 
    printf("\n"); 
    for (i = 0; i < n; i++)   
        array[i] = temp[i];  
    free (temp); 
    free (b);    
   
    return 1 ;   

 
int  
get_value(int a,int d) 

    int b=a; 
    for (;d>0&&a>0;d--) 
        b/=MAXK; 
    return b%MAXK; 

int 
get_int(void) 

    int input; 
    char ch; 
    while (scanf("%d",&input)!=1) 
    { 
        while((ch=getchar())!='\n') 
            putchar(input); 
        printf(" is not an integer.\nPlease enter an integer value,such as 25,-178,or 3;\n"); 
    } 
    return input; 

点击复制链接 与好友分享!回本站首页
相关TAG标签 基数 算法 语言
上一篇:排序算法系列:计数排序(Counting sort)(C语言)
下一篇:当C++遇到IOS应用开发之---List集合
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站