# 6. 分配类排序
1. 多关键字排序
两个关键字的优先级，先分高级的叫 “高位优先” 排序法，先分低级的叫 “低位优先” 排序法
2. 链式基数排序
排序时先按最低位的值对记录进行初步排序，在此基础上再按次低位的值进行进一步排序。依此类推，由低位到高位，每一趟都是在前一趟的基础上，根据关键字的某一位对所有记录进行排序，直至最高位，这样就完成了基数排序的全过程。
// 理解就好不用硬看 | |
#define RADIX 10 | |
#define KEY_SIZE 6 | |
#define LIST_SIZE 20 | |
typedef int KeyType; | |
typedef struct { | |
KeyType keys[KEY_SIZE]; /* 子关键字数组 */ | |
OtherType other_data; /* 其它数据项 */ | |
int next; /* 静态链域 */ | |
}RecordType1; | |
typedef struct { | |
RecordType1 r[LIST_SIZE+1]; /* r [0] 为头结点 */ | |
int length; | |
int keynum; | |
} SLinkList; /* 静态链表 */ | |
typedef int PVector[RADIX]; | |
/* 记录数组 r 中记录已按低位关键字 key [i+1]，…，key [d] 进行过 “低位优先” 排序。 | |
本算法按第 i 位关键字 key [i] 建立 RADIX 个队列，同一个队列中记录的 key [i] 相同。head [j] | |
和 tail [j] 分别指向各队列中第一个和最后一个记录（j=0，1，2，…，RADIX-1）。head [j]=0 | |
表示相应队列为空队列 */ | |
void Distribute(RecordType1 r[], int i, PVector head, PVector tail){ | |
for ( j=0 ; j<=RADIX-1 ; ++j)head[j]=0; /* 将 RADIX 个队列初始化为空队列 */ | |
p= r[0].next ; /* p 指向链表中的第一个记录 */ | |
while( p!=0 ){ | |
j=Order(r[p].key[i]); /* 用记录中第 i 位关键字求相应队列号 */ | |
if ( head[j]==0 ) head[j]=p ; /* 将 p 所指向的结点加入第 j 个队列中 */ | |
else r[tail[j]].next=p; | |
tail[j]=p; | |
p= r[p].next ; | |
} | |
} /* Distribute */ | |
/* 本算法从 0 到 RADIX-1 扫描各队列，将所有非空队列首尾相接，重新链接成一个链表 */ | |
void Collect (RecordType r[], PVector head, PVector tail){ | |
j=0; | |
while (head[j]==0 ) ++j ;/* 找第一个非空队列 */ | |
r[0].next =head[j] ; | |
t=tail[j] ; | |
while ( j<RADIX-1 ){ /* 寻找并串接所有非空队列 */ | |
++j ; | |
while ( (j<RADIX-1 ) && (head[j]==0 ) ) ++j ; /* 找下一个非空队列 */ | |
if(head[j]!=0 ){ /* 链接非空队列 */ | |
r[t].next =head[j] ; | |
t=tail[j] ; | |
} | |
} | |
r[t].next =0; /* t 指向最后一个非空队列中的最后一个结点 */ | |
} /* Collect */ | |
/* length 个记录存放在数组 r 中，执行本算法进行基数排序后，链表中的记录将按关键字从小到大的顺序相链接。 */ | |
void RadixSort (RecordType r[],int length ){ | |
n= length; | |
for ( i=0 ; i<= n-1 ; ++i) r[i].next=i+1 ; /* 构造静态链表 */ | |
r[n].next =0 ; | |
d= keynum; | |
for ( i =d-1 ; i>= 0; --i ){ /* 从最低位子关键字开始，进行 d 趟分配 和 收集 */ | |
Distribute(r，i，head，tail); /* 第 i 趟分配 */ | |
Collect(r，head，tail) /* 第 i 趟收集 */ | |
} | |
} /* RadixSort */ |
