基数排序（radix sort）

基数排序思想

如果我们有N个整数，范围从1到M（或从1到M - 1），我们可以利用这个信息得到一种快速的排序，叫做桶式排序（bucket sort）。我们留置一个数组，称之为Count,大小为M，并初始化为0。于是，Count有M个单元，开始时他们都是空的。当A[i]被读入时Count[A[i]]增1。在所有的输入被读进后，扫描数组Count,打印输出排好的表。

代码实现（C语言）

LMD（最低位优先法）

#include<stdio.h>
#include<math.h>

int main(void)
{
    int a [] = {3,15,18,10,34,20,13,20,100,254,486,598 };
    int * p = a;
    //计算数组长度
    int size = sizeof(a) / sizeof(int);
    //基数排序
    bucketSort3(p,size);
    //打印排序结果
    int i;
    for(i = 0; i < size; i++)
        printf("%d\n",a[i]);

    return 0;
}


//基数排序
void bucketSort3(int * p, int n)
{
    //获取数组中的最大数
    int maxNum = findMax(p,n);
    //获取分配次数
    int times = getTimes(maxNum);
    int i;
    printf("times:%d\n",times);
    for(i = 1; i <= times; i++)
        sort2(p,n,i);
}

int getTimes(int num)
{
    int count = 1;
    int temp = num / 10;
    while(temp != 0)
    {
        count++;
        temp= temp / 10;
    }

    return count;
}

int findMax(int * p,int n)
{
    int i;
    int max = 0;

    for(i = 0;i < n; i++)
    {
        if (p[i] > max)
            max = p[i];
    }
    return max;
}

//将数字按位数分配到各自的桶中，按桶的顺序输出排序结果

void sort2(int * p,int n, int loop)
{
    // 预设桶的大小
    int buckets[10][20] = {};
    int tempNum = (int)pow(10,loop - 1);
    int i,j;

    for(i = 0; i < n; i++ )
    {
        int index = (p[i] / tempNum) % 10;
        for(j = 0; j < 20; j++)
         {
             if(buckets[index][j] == NULL)
        {
            buckets[index][j] = p[i];
            break;
        }
         }

    }

    //将桶中的数，倒回到原有数组中

    int k = 0;

    for (i = 0; i < 10; i++)
    {
        for (j = 0; j < 20; j++)
        {
            if (buckets[i][j] != NULL)
            {
                p[k] = buckets[i][j];
                buckets[i][j] = NULL;
                k++;
            }


        }
    }
}

测试结果

image.png