基數(shù)排序是一種非比較型整數(shù)排序算法，其原理是將整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。由于整數(shù)也可以表達字符串（比如名字或日期）和特定格式的浮點數(shù)，所以基數(shù)排序也不是只能使用于整數(shù)。

（1）什么是基數(shù)排序？

1. 通過鍵值得各個位的值，將要排序的元素分配至一些桶中，達到排序的作用

2. 基數(shù)排序法是屬于穩(wěn)定性的排序，基數(shù)排序法是效率高的穩(wěn)定排序法

3. 基數(shù)排序是桶排序的擴展

（2）實現(xiàn)原理

將所有待比較數(shù)值（自然數(shù)）統(tǒng)一為同樣的數(shù)位長度，數(shù)位較短的數(shù)前面補零。然后，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個有序序列。

（3）LSD 基數(shù)排序動圖演示

LSD 基數(shù)排序動圖

（4）C語言代碼實現(xiàn)如下：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
//定義基數(shù)為10進制
#define radix 10
//交換數(shù)值
void swap(int *a,int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
//打印數(shù)組
void printArray(char msg[],int arr[],int len){
    printf("%s:",msg);
    for (int i = 0; i < len; i++){
        printf("%d ", arr[i]);
    }
    printf("\n");
}
//基數(shù)排序
void radix_sort(int a[],int len){
    int maxvalue=a[0],minvalue=a[0];
    for(int x=0;x<len;x++){
        maxvalue=a[x]>maxvalue?a[x]:maxvalue;
        minvalue=a[x]<minvalue?a[x]:minvalue;
    }
    int* temp = (int*)malloc(len*sizeof(int));
    //獲取最大位數(shù)
    int n=1;
    int d = maxvalue-minvalue;
    while(d>=10){
        d=d/10;
        n++;
    }
    printf("總遍歷位數(shù)：%d,最小值：%d,最大值：%d\n",n,minvalue,maxvalue);
    //要獲取的位
    int divide=1;
    for(int i=1;i<=n;i++){
        //初始化計數(shù)器
        int counter[radix]={0};
        for(int j=0;j<len;j++){
            //找出a[j]相對minvalue值的對應(yīng)的位divide的值
            int pos = ((a[j]-minvalue)/divide)%radix;
            //a[j]換算成計數(shù)器數(shù)組下標pos并自增
            counter[pos]++;
        }
        //使用累加(counter[n]=counter[n]+counter[n-1]，有點類似斐波那契數(shù)列)計算出元素所在位置，保證結(jié)果有序
        for(int j=1;j<10;j++){
            counter[j]=counter[j]+counter[j-1];
        }
        //倒序遍歷數(shù)組a，可以保持結(jié)果穩(wěn)定性
        for(int j=len-1;j>=0;j--){
            //將a[j]映射到計數(shù)器下標pos，counter[pos]就是a[j]在新數(shù)組的位置
            int pos=((a[j]-minvalue)/divide)%radix;
            //獲取元素位置mappos，--counter[pos]：每放一個元素到數(shù)組temp，counter[pos]值自減，保證結(jié)果穩(wěn)定有序
            int mappos=(--counter[pos]);
            temp[mappos]=a[j];
        }
        //把temp有序數(shù)組賦值給a
        for(int j=0;j<len;j++){
            a[j]=temp[j];
        }
        printf("遍歷位數(shù)%d：\n",divide);
        for(int j=0;j<len;j++){
            printf("a[%d]=%d,a[%d]-%d=%d\n",j,a[j],j,minvalue,a[j]-minvalue);
        }
        printf("\n");
        //獲取數(shù)值的下個位，比如個位數(shù)，下個是十位數(shù)
        divide=divide*radix;
    }
    free(temp);
}
int main()
{
    int len=10;
    int arr[len];
    srand((unsigned)time(NULL));
    //隨機生成長度為"len"的數(shù)組
    for(int i=0;i<len;i++){
        arr[i]=rand()%200;
    }
    printArray("未排序前",arr,len);
    radix_sort(arr,len);
    printArray("基數(shù)排序",arr,len);
    //防止windows下控制臺窗口閃退
    int s;
    scanf("%d",&s);
    return 0;
}

如果我們編譯并運行上述程序，那么它應(yīng)該產(chǎn)生以下結(jié)果：

未排序前:80 155 178 14 59 36 195 15 141 143 
總遍歷位數(shù)：3,最小值：14,最大值：195
遍歷位數(shù)1：
a[0]=14,a[0]-14=0
a[1]=155,a[1]-14=141
a[2]=195,a[2]-14=181
a[3]=15,a[3]-14=1
a[4]=36,a[4]-14=22
a[5]=178,a[5]-14=164
a[6]=59,a[6]-14=45
a[7]=80,a[7]-14=66
a[8]=141,a[8]-14=127
a[9]=143,a[9]-14=129

遍歷位數(shù)10：
a[0]=14,a[0]-14=0
a[1]=15,a[1]-14=1
a[2]=36,a[2]-14=22
a[3]=141,a[3]-14=127
a[4]=143,a[4]-14=129
a[5]=155,a[5]-14=141
a[6]=59,a[6]-14=45
a[7]=178,a[7]-14=164
a[8]=80,a[8]-14=66
a[9]=195,a[9]-14=181

遍歷位數(shù)100：
a[0]=14,a[0]-14=0
a[1]=15,a[1]-14=1
a[2]=36,a[2]-14=22
a[3]=59,a[3]-14=45
a[4]=80,a[4]-14=66
a[5]=141,a[5]-14=127
a[6]=143,a[6]-14=129
a[7]=155,a[7]-14=141
a[8]=178,a[8]-14=164
a[9]=195,a[9]-14=181

基數(shù)排序:14 15 36 59 80 141 143 155 178 195