数据结构之基数排序

基数排序：基本思想是对数字的每一位进行排列，先对各位进行排序，在对十位进行排序，再对百位...对每一位进行排序，要求采用稳定的排序算法.

// 计数排序算法：a为等排序数组 （一位数，要和atemp区分开，b为排序好的数组，c为中间数组，atemp为原始数组（包括三位数） 
void counting_sort(int a[],int b[], int c[],int atemp[])
{
    int i,j;
    for(i = 0;i < NUM; i++)
        c[i] = 0;
    for(j = 0;j < NUM; j++)
        c[a[j]] += 1; 
    for(i = 1; i < NUM; i++)
        c[i] = c[i] + c[i -1];
    for(j = 9; j >=0; j--)
    {
        b[c[a[j]] - 1] = atemp[j];
        c[a[j]] -= 1;
    }
}

项目完整代码如下：

#include <stdio.h>
#include <stdlib.h>
#define NUM 10          //数组元素个数

// 计数排序算法：a为等排序数组 （一位数，要和atemp区分开，b为排序好的数组，c为//中间数组，atemp为原始数组（包括三位数） 
void counting_sort(int a[],int b[], int c[],int atemp[])
{
    int i,j;
    for(i = 0;i < NUM; i++)
        c[i] = 0;
    for(j = 0;j < NUM; j++)
        c[a[j]] += 1; 
    for(i = 1; i < NUM; i++)
        c[i] = c[i] + c[i -1];
    for(j = 9; j >=0; j--)
    {
        b[c[a[j]] - 1] = atemp[j];
        c[a[j]] -= 1;
    }
}
int main()
{   
    int i,j;
    int a[10] = {236, 16, 25, 95, 48, 30, 99, 78, 456, 61};
    int atemp[10];
    int b[10];
    int c[10];
    
    //个位排序 
    for(i = 0;i < NUM; i++) 
        atemp[i] = a[i] % 10;
    counting_sort(atemp, b, c, a);
    for(i = 0; i < NUM; i++)
        a[i] = b[i];

    //十位排序 
    for(i = 0;i < NUM; i++) 
        atemp[i] = a[i] /10 % 10;
    counting_sort(atemp, b, c, a);
    for(i = 0; i < NUM; i++)
        a[i] = b[i];
        
    //百位排序 
    for(i = 0;i < NUM; i++) 
        atemp[i] = a[i] /100 % 10;
    counting_sort(atemp, b, c, a);
    
    for(i = 0; i < NUM; i++)
//      a[i] = b[i];
        printf("%5d", b[i]); 
    printf("\n");
    return 0;
}