c语言基数排序

1.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

/* 基数排序
 * 1.求出数组中最大的元素
 * 2.求出最大元素是几位数, 设为i位
 * 3.对所有的数进行i轮排序. 
 *   首先排个位, 然后是十位, 然后百位
 * 4.每一轮的排位都需要分桶, 桶是有顺序的,
 *   然后把桶里的数按顺序放入原来的数组中.
 * 5.直到i轮排序结束后, 数组排序完成.      */

/*获取数字的位数*/
int figure(int num)
{
    int count = 1;
    int temp = num / 10;

    while(temp != 0)
    {
        count++;
        temp /= 10;
    }

    return count;
}

/*查询数组中的最大数*/
int max(int *a, int n)
{
    int max = a[0];
    int i;

    for(i=1; i<n; i++)
    {
        if(a[i] > max)
        {
            max = a[i];
        }
    }

    return max;
}

/*将数字分配到各自的桶中, 然后按照桶的顺序输出排序结果*/
void sort2(int *a, int n, int loop)
{
    int *buckets[10] = {NULL};
    int c[10] = {0};
    int d[10] = {1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
    int i, j, k;
    int row;
    int temp = d[loop-1];

    /*统计每个桶的元素个数*/
    for(i=0; i<n; i++)
    {
        row = (a[i] / temp) % 10;

        c[row]++;
    }

    /*为每个桶分配空间*/
    for(i=0; i<10; i++)
    {
        buckets[i] = (int *)malloc(c[i]*sizeof(int));
    }

    memset(c, 0x00, sizeof(c));

    /*将数组中的数据分配到桶中*/
    for(i=0; i<n; i++)
    {
        row = (a[i] / temp) % 10;

        buckets[row][c[row]] = a[i];

        c[row]++;
    }

    k = 0;

    /*将桶中的数, 倒回到原有数组中*/
    for(i=0; i<10; i++)
    {
        for(j=0; j<c[i]; j++)
        {
            a[k] = buckets[i][j];
            k++;
        }
    }

    /*释放桶内存*/
    for(i=0; i<10; i++)
    {
        free(buckets[i]);
        buckets[i] = NULL;
    }
}

/*基数排序*/
void sort3(int *a, int n)
{
    int m = max(a, n);
    int loop = figure(m);
    int i;

    for(i=1; i<=loop; i++)
    {
        sort2(a, n, i);
    }
}

int main()
{
    int a[] = {2, 343, 342, 1, 123, 43, 4343, 433, 687, 654, 3};
    int *p = a;
    int size;
    int i;

    /*计算数组长度*/
    size = sizeof(a) / sizeof(int);

    /*基数排序*/
    sort3(p, size);

    /*打印排序后结果*/
    for(i=0; i<size; i++)
    {
        printf("%d\n", a[i]);
    }

    return 0;
}

2.编译源码

$ gcc -o example example.c -std=c89

3.运行及其结果

$ ./example
1
2
3
43
123
342
343
433
654
687
4343