排序算法系列：基數排序(Radix sort)（C語言）

通俗理解：結合計數排序，通過對待排數組中元素每一位進行排序，最終達到對整個數組排序的效果。觀看動態過程
[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; 
}