基数排序
基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
实现原理
基数排序的发明可以追溯到1887年赫尔曼·何乐礼在打孔卡片制表机(Tabulation Machine)上的贡献。它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。
LSD和MSD是基数排序中的两种不同排序顺序，分别代表Least Significant Digital（最低有效位优先）和Most Significant Digital（最高有效位优先）。
LSD（Least Significant Digital）：LSD从数值的最右边（低位）开始排序。这种排序方式从数据的最低位开始处理，逐步向高位进行，适用于位数较多的数据排序，因为它从较低位开始，可以更快地处理大量数据。
MSD（Most Significant Digital）：MSD则从数值的最左边（高位）开始排序。与LSD相反，MSD从数据的最高位开始处理，逐步向低位进行。这种方式适用于位数较少但高位有较大差异的数据排序。
基本步骤
以LSD为例，对一串数据278 109 063 930 589 184 505 269 008 083进行基数确定,最高位是百位,故分发趟数为3.是十进制数据,即基数为0~9,
开始分发:
-
第一趟分发:
回收:
-
第二趟分发:
回收:
-
第三趟分发:
回收:
-
排序完成
过程分析:
第一趟分发回收使个位有序;
第二趟分发回收使十位有序;(在个位有序的前提下,使十位有序)
第三趟分发回收使百位有序;(在个位和十位有序的前提下,使百位有序)
效率分析
时间效率：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。 空间效率：需要2*radix个指向队列的辅助空间，以及用于静态链表的n个指针。
代码实现
分发回收过程符合先进先出方式,因此可以使用队列.
sort
std::queue<int> q[10]; //0~9一共10个基数,需要10个队列(先进先出)
//获取对应位的值
int GetDigit(int value, int k) {
int tmp;
while (k-- >= 0) {
tmp = value % 10;
value /= 10;
}
return tmp;
}
//获取最大位数
int getNumberOfDigits(int number) {
if (number == 0) return 1; // 特殊情况：0 的位数为 1
if (number < 0) number = -number; // 转换为正数
return (int)log10(number) + 1; //log后取整+1就能得到位数
}
//分发
void Distribute(int *a,int size, int k) {
for (int i = 0 ; i < size; ++i) {
int digit = GetDigit(a[i],k);
q[digit].push(a[i]);
}
}
//收集
void Collect(int *a, int size) {
//回收:考回原数组
int j = 0;
for (int i = 0; i < size;i++) {
while (!q[i].empty()) {
a[j++] = q[i].front();
q[i].pop();
}
}
}
void RadixSort(int* a, int size) {
int k = 3; //扩展:getMaxNum:获取最大的数,计算有多少位
//int k = getNumberOfDigits(999); //k=3
for (int i = 0; i < k; i++) {
Distribute(a, size, i);
Collect(a, size);
}
}
main
int a[] = {278,109,63,930,589,184,505,269,8,83}; //自定义数组
RadixSort(a,10);
PrintArray(a,10);
