基數(shù)排序
不同于之前所介紹的各類排序，前邊介紹到的排序方法或多或少的是通過(guò)使用比較和移動(dòng)記錄來(lái)實(shí)現(xiàn)排序茄唐，而基數(shù)排序的實(shí)現(xiàn)不需要進(jìn)行對(duì)關(guān)鍵字的比較凸郑，只需要對(duì)關(guān)鍵字進(jìn)行“分配”與“收集”兩種操作即可完成辜限。
例如對(duì)無(wú)序表{50蛮位，123，543预吆，187龙填，49，30，0岩遗，2扇商，11，100}進(jìn)行基數(shù)排序宿礁，由于每個(gè)關(guān)鍵字都是整數(shù)數(shù)值案铺，且其中的最大值由個(gè)位、十位和百位構(gòu)成梆靖，每個(gè)數(shù)位上的數(shù)字從 0 到 9控汉，首先將各個(gè)關(guān)鍵字按照其個(gè)位數(shù)字的不同進(jìn)行分配分配表如下圖所示：
通過(guò)按照各關(guān)鍵字的個(gè)位數(shù)進(jìn)行分配，按照順序收集得到的序列變?yōu)椋簕50返吻，30姑子，0，100思喊，11壁酬，2次酌，123恨课，543，187岳服，49}剂公。在該序列表的基礎(chǔ)上，再按照各關(guān)鍵字的十位對(duì)各關(guān)鍵字進(jìn)行分配吊宋，得到的分配表如下圖所示：
由上表順序收集得到的記錄表為：{0纲辽、100、2璃搜、11拖吼、123、30这吻、543吊档、49、50唾糯、187}怠硼。在該無(wú)序表的基礎(chǔ)上，依次將表中的記錄按照其關(guān)鍵字的百位進(jìn)行分配移怯，得到的分配如下圖所示：
最終通過(guò)三次分配與收集香璃，最終得到的就是一個(gè)排好序的有序表：{0、2舟误、11葡秒、30、49、50同云、100糖权、123、187炸站、543}星澳。
例子中是按照個(gè)位-十位-百位的順序進(jìn)行基數(shù)排序，此種方式是從最低位開始排序旱易，所以被稱為最低位優(yōu)先法（簡(jiǎn)稱“LSD法”）禁偎。
同樣還可以按照百位-十位-各位的順序進(jìn)行排序，稱為最高位優(yōu)先法（簡(jiǎn)稱“MSD法”）阀坏，使用該方式進(jìn)行排序同最低位優(yōu)先法不同的是：當(dāng)無(wú)序表中的關(guān)鍵字進(jìn)行分配后如暖，相當(dāng)于進(jìn)入了多個(gè)子序列，后序的排序工作分別在各個(gè)子序列中進(jìn)行（最低位優(yōu)先法每次分配與收集都是相對(duì)于整個(gè)序列表而言的）忌堂。
例如還是對(duì){50盒至，123，543士修，187枷遂，49，30棋嘲，0酒唉，2，11沸移，100}使用最高位優(yōu)先法進(jìn)行排序痪伦，首先按照百位的不同進(jìn)行分配，得到的分配表為：
由上圖所示雹锣，整個(gè)無(wú)序表被分為了 3 個(gè)子序列网沾，序列 1 和序列 2 中含有多個(gè)關(guān)鍵字，序列 3 中只包含了一個(gè)關(guān)鍵字蕊爵，最高位優(yōu)先法完成排序的標(biāo)準(zhǔn)為：直到每個(gè)子序列中只有一個(gè)關(guān)鍵字為止辉哥，所以需要分別對(duì)兩個(gè)子序列進(jìn)行再分配，各自的分配表如下圖所示：
上表中在辆，序列 1 中還有含有兩個(gè)關(guān)鍵字的子序列证薇，所以還需要根據(jù)個(gè)位進(jìn)行分配，最終按照各子序列的順序同樣會(huì)得到一個(gè)有序表匆篓。
基數(shù)排序的具體實(shí)現(xiàn)（采用LSD法）
基數(shù)排序較宜使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)作為存儲(chǔ)結(jié)構(gòu)浑度，相比于順序存儲(chǔ)結(jié)構(gòu)更節(jié)省排序過(guò)程中所需要的存儲(chǔ)空間，稱之為“鏈?zhǔn)交鶖?shù)排序”鸦概。
其具體的實(shí)現(xiàn)代碼為：
#include <stdio.h>
#include <stdlib.h>
//構(gòu)成關(guān)鍵字的組成部分的最大個(gè)數(shù)設(shè)置8
//基數(shù)設(shè)置10箩张，例如關(guān)鍵字是數(shù)字甩骏，無(wú)疑由0~9組成，基數(shù)就是10先慷；如果關(guān)鍵字是字符串（字母組成）饮笛，基數(shù)就是 26
//靜態(tài)鏈表的結(jié)點(diǎn)結(jié)構(gòu)
typedef struct{
int data;//存儲(chǔ)的關(guān)鍵字
int keys[8];//存儲(chǔ)關(guān)鍵字的數(shù)組（此時(shí)是一位一位的存儲(chǔ)在數(shù)組中）
int next;//做指針用，用于是靜態(tài)鏈表论熙，所以每個(gè)結(jié)點(diǎn)中存儲(chǔ)著下一個(gè)結(jié)點(diǎn)所在數(shù)組中的位置下標(biāo)
}SLCell;
//靜態(tài)鏈表結(jié)構(gòu)
typedef struct{
SLCell r[10000];//靜態(tài)鏈表的可利用空間福青，其中r[0]為頭結(jié)點(diǎn)
int keynum;//當(dāng)前所有的關(guān)鍵字中最大的關(guān)鍵字所包含的位數(shù)，例如最大關(guān)鍵字是百脓诡，說(shuō)明所有keynum=3
int recnum;//靜態(tài)鏈表的當(dāng)前長(zhǎng)度
} SLList;
typedef int ArrType[10];//指針數(shù)組无午，用于記錄各子序列的首尾位置
//排序的分配算法，i表示按照分配的位次（是個(gè)位祝谚，十位還是百位）宪迟，f表示各子序列中第一個(gè)記錄和最后一個(gè)記錄的位置
void Distribute(SLCell *r,int i,ArrType f,ArrType e){
int j;
//初始化指針數(shù)組
for (j=0; j<10; j++) {
f[j]=0;
}
//遍歷各個(gè)關(guān)鍵字
int p;
for (p=r[0].next; p; p=r[p].next) {
int j=r[p].keys[i];//取出每個(gè)關(guān)鍵字的第 i 位，由于采用的是最低位優(yōu)先法交惯，所以次泽，例如，第 1 位指的就是每個(gè)關(guān)鍵字的個(gè)位
if (!f[j]) {//如果只想該位數(shù)字的指針不存在席爽，說(shuō)明這是第一個(gè)關(guān)鍵字意荤，直接記錄該關(guān)鍵字的位置即可
f[j]=p;
}else{//如果存在，說(shuō)明之前已經(jīng)有同該關(guān)鍵字相同位的記錄拳昌，所以需要將其進(jìn)行連接袭异，將最后一個(gè)相同的關(guān)鍵字的next指針指向該關(guān)鍵字所在的位置钠龙，同時(shí)最后移動(dòng)尾指針的位置炬藤。
r[e[j]].next=p;
}
e[j]=p;//移動(dòng)尾指針的位置
}
}
//基數(shù)排序的收集算法，即重新設(shè)置鏈表中各結(jié)點(diǎn)的尾指針
void Collect(SLCell *r,int i,ArrType f,ArrType e){
int j;
//從 0 開始遍歷碴里，查找頭指針不為空的情況沈矿，為空表明該位沒(méi)有該類型的關(guān)鍵字
for (j=0;!f[j]; j++);
r[0].next=f[j];//重新設(shè)置頭結(jié)點(diǎn)
int t=e[j];//找到尾指針的位置
while (j<10) {
for (j++; j<10; j++) {
if (f[j]) {
r[t].next=f[j];//重新連接下一個(gè)位次的首個(gè)關(guān)鍵字
t=e[j];//t代表下一個(gè)位次的尾指針?biāo)诘奈恢? }
}
}
r[t].next=0;//0表示鏈表結(jié)束
}
void Sort(SLList *L){
ArrType f,e;
int i;
//根據(jù)記錄中所包含的關(guān)鍵字的最大位數(shù)，一位一位的進(jìn)行分配與收集
for (i=0; i<L->keynum; i++) {
//秉著先分配后收集的順序
Distribute(L->r, i, f, e);
Collect(L->r, i, f, e);
}
}
//創(chuàng)建靜態(tài)鏈表
void creatList(SLList * L){
int key,i=1,j;
scanf("%d",&key);
while (key!=-1) {
L->r[i].data=key;
for (j=0; j<=L->keynum; j++) {
L->r[i].keys[j]=key%10;
key/=10;
}
L->r[i-1].next=i;
i++;
scanf("%d",&key);
}
L->recnum=i-1;
L->r[L->recnum].next=0;
}
//輸出靜態(tài)鏈表
void print(SLList*L){
int p;
for (p=L->r[0].next; p; p=L->r[p].next) {
printf("%d ",L->r[p].data);
}
printf("\n");
}
int main(int argc, const char * argv[]) {
SLList *L=(SLList*)malloc(sizeof(SLList));
L->keynum=3;
L->recnum=0;
creatList(L);//創(chuàng)建靜態(tài)鏈表
printf("排序前：");
print(L);
Sort(L);//對(duì)靜態(tài)鏈表中的記錄進(jìn)行基數(shù)排序
printf("排序后：");
print(L);
return 0;
}
