基数排序

radixSort.c

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


void radixSort(int *arr, int len, int max)
{
    int buckets[10][10] = {0};
    int order[10] = {0};
    int n = 1;
    while (n < max)
    {
        for(int i = 0; i < len; i++)
        {
            int lsd = arr[i]/ n % 10;
            buckets[lsd][order[lsd]] = arr[i];
            order[lsd]++;
        }
        int count = 0;
        for(int j = 0; j < 10;j++)
        {
            if (order[j] != 0) {
                for (int k = 0; k < order[j]; k++) {
                    if (buckets[j][k] > 0)
                        arr[count++] = buckets[j][k];
                }
            }
            order[j] = 0;
        }

        n *= 10;
    }

}


int main()
{
    int data[] = {342,58,576,356,412,231,976,652,809};
    int length = sizeof(data)/ sizeof(data[0]);
    for (int i = 0; i < length; ++i) {
        printf("%d ",data[i]);
    }
    printf("\n");

    radixSort(data,length,976);
    for (int i = 0; i < length; ++i) {
        printf("%d ",data[i]);
    }
    printf("\n");
    return  0;
}

代码分析详见这里