基数排序过程
假设输入元素为：10,21,17,34,44,11,654,123，我们选择 10 作为基数进行基数排序。
首先，我们根据个位对元素进行分类：
0: 10
1: 21 11
2:
3: 123
4: 34 44 654
5:
6:
7: 17
8:
9:
依次收集元素，得到序列 10,21,11,123,24,44,654,17，再根据十位对元素分类：
0:
1: 10 11 17
2: 21 123
3: 34
4: 44
5: 654
6:
7:
8:
9:
依次收集元素，得到序列 10,11,17,21,123,34,44,654，最后根据百位对元素分类：
0: 010 011 017 021 034 044
1: 123
2:
3:
4:
5:
6: 654
7:
8:
9:
依次收集元素，得到最终的有序序列 10,11,17,21,34,44,123,654。
基数排序的基本实现（基于桶排序）
上面所给的例子中，我们用 0~9 这 10 个桶来存放元素。在这个基本实现中，每个桶都用一个链表来存储。而这 10 个桶的头结点，用一个一维数组来存放，便于根据下标来访问桶。
在元素的分配过程中，我们始终将元素插入到桶的末尾，而收集的时候只需依次从前往后收集，这样能确保先进先出（本质上就是队列）。如果通过遍历的方式找到链表的末尾，时间复杂度将会变得相当高。因此我们在桶这一结构中加入了一个尾指针 tail，用于指向桶的最后一个结点，这样就能在 O(1) 的时间内将元素插入到链表末尾。
改进后的结构如下：
具体代码
// -----------------------------------------------------
// Copyright (c) 2017, Wray Zheng. All Rights Reserved.
// Distributed under the BSD License.
// -----------------------------------------------------
#include <iostream>
#include <algorithm>
#include <ctime>
#define RADIX 1000
using namespace std;
/* 定义桶内的结点 */
struct node {
int num;
node* next;
node(int num = 0, node* next = nullptr): num(num), next(next) {}
};
/* 定义每个桶的结构
* head为链表的头结点
* tail指向链表的尾结点 */
struct bucket {
node head;
node* tail;
bucket() : tail(nullptr) {}
};
/* bitIndex 表示当前作为关键字的位
* 根据 bitIndex 所对应的位将元素分配到桶中 */
void Distribute(int* data, int n, bucket* B, int bitIndex) {
int divider = 1;
for(int i = 0; i < bitIndex; i++) divider *= RADIX;
int bit;
node* p;
for(int i = 0; i < n; i++) {
bit = (data[i] / divider) % RADIX;
//将元素分配到对应桶中
//若尾指针为null，则插入到头结点后面
//若尾指针不为null，则插入到尾结点后面
p = B[bit].tail ? B[bit].tail : &B[bit].head;
p->next = new node(data[i], p->next);
B[bit].tail = p->next;
}
}
/* 从各个桶中收集元素到数组中 */
void Collect(int* data, int n, bucket* B) {
int index = 0;
//扫描每一个桶
for(int i = 0; i < RADIX; i++) {
node* p = &B[i].head;
//遍历收集桶内的所有元素
while(p->next) {
node* temp = p->next;
data[index] = temp->num;
index++;
p->next = temp->next;
delete temp;
}
B[i].tail = nullptr;
}
}
/* 获取最大数字的位数 */
int GetMaxBits(int* data, int n) {
int max = data[0];
for(int i = 1; i < n; i++) {
if(data[i] > max) max = data[i];
}
int t;
for(t = 0; max != 0; t++) max /= RADIX;
return t;
}
/* 基数排序 */
void radixSort(int* data, int n) {
bucket* B = new bucket[RADIX];
int maxBits= GetMaxBits(data, n);
for(int i = 0; i < maxBits; i++) {
//根据当前位将元素分配到各桶中
Distribute(data, n, B, i);
//从桶中依次收集各元素
Collect(data, n, B);
}
delete[] B;
}
/* 随机数产生函数
* 产生指定长度的随机序列，用于快速排序的测试 */
int* randomNums(int n) {
int* array = new int[n];
for (int i = 0; i < n; i++)
{
array[i] = i;
}
//将数组中元素的顺序打乱
random_shuffle(array, array + n - 1);
return array;
}
int main() {
int n = 1000000;
int* array = randomNums(n);
int start = clock();
radixSort(array, n);
int time_used = clock() - start;
cout << "Array Size: " << n << endl;
cout << "Time Used: " << time_used << " ms" << endl;
return 0;
}
假设有 n 个元素进行排序，最大元素有 d 位，基数为 r。理论上，该算法每趟排序的时间复杂度位 O(n+r)，总的时间复杂度为 O(d(n+r))。当元素的位数较少时，该算法效率非常高。
但是理论的分析与具体实现时遇到的问题并不完全一致。因为真正实现时，还需要考虑分配和收集元素时，频繁的内存分配问题。上述实现需要在元素分配时为每个元素都申请内存，在收集时为每个元素释放内存，即共需要进行 nd 次内存申请和 nd 次内存释放。由于内存的申请和释放是相对复杂的操作，耗时较长，这种频繁的内存分配无疑严重降低了算法的效率。
要优化该算法的实现，有两种思路：
- 一种是避免频繁地向系统申请和释放内存，可以采用内存池来实现；
- 另一种是弃用链表这一数据结构，采用其它方式来完成元素的分配收集。
基数排序的高效实现（基于计数排序）
如上面提到的，优化该算法有两个方向，这里我们要探讨的是第二种思路，即弃用链表，采用其它方式来完成元素的分配收集。
链表实现与我们的直观感受相同：分配与收集元素，分配时将元素添加到对应的桶中，收集时从对应桶中删除元素。为了更高效地实现该算法，我们将牺牲这种直观，采用一种类似计数排序的方式来直接完成分类的过程。
假设基数为 r，我们创建一个大小为 r 的数组 count，count 数组的作用是统计当前位每个数字出现的次数。
每一趟排序的过程如下：
- 将 count 数组的每个元素初始化为 0
- 遍历所有元素，把每个元素的当前位 k 作为 count 数组的下标，count[k]++
- 从 count 的第二项开始，count[i] = count[i] + count[i-1]
- 从后往前遍历待排序数组，假设元素当前位为 k，则 count[k] 中存的是当前位小于等于 k 的元素个数，因此当前元素最终的位置应该是第 count[k] 个，下标j = count[k] - 1，故令 output[j] = 当前元素
具体代码
// -----------------------------------------------------
// Copyright (c) 2017, Wray Zheng. All Rights Reserved.
// Distributed under the BSD License.
// -----------------------------------------------------
#include <iostream>
#include <algorithm>
#include <ctime>
#define RADIX 1000
using namespace std;
/* 获取最大数字的位数 */
int GetMaxBits(int* data, int n) {
int max = data[0];
for(int i = 1; i < n; i++) {
if(data[i] > max) max = data[i];
}
int t;
for(t = 0; max != 0; t++) max /= RADIX;
return t;
}
/* 基数排序中对每一位调用的计数排序 */
void countSort(int *data, int n, int bitIndex)
{
int bit;
int exp = 1;
for(int i = 0; i < bitIndex; i++) exp *= RADIX;
int* output = new int[n];
int count[RADIX] = {0};
//count数组用于记录每个基数出现的次数
for (int i = 0; i < n; i++) {
bit = (data[i] / exp) % RADIX;
count[bit]++;
}
//将count数组转换成output数组中对应的下标
for (int i = 1; i < RADIX; i++)
count[i] += count[i-1];
//将结果输出到 output 数组
for (int i = n - 1; i >= 0; i--)
{
bit = (data[i] / exp) % RADIX;
output[count[bit]-1] = data[i];
count[bit]--;
}
//将结果复制回 data 数组
for (int i = 0; i < n; i++)
data[i] = output[i];
delete[] output;
}
/* 基数排序 */
void radixSort(int* data, int n) {
int maxBits = GetMaxBits(data, n);
for(int i = 0; i < maxBits; i++) {
countSort(data, n, i);
}
}
/* 随机数产生函数
* 产生指定长度的随机序列，用于快速排序的测试 */
int* randomNums(int n) {
int* array = new int[n];
for (int i = 0; i < n; i++)
{
array[i] = i;
}
//将数组中元素的顺序打乱
random_shuffle(array, array + n - 1);
return array;
}
int main() {
int n = 1000000;
int* array = randomNums(n);
int start = clock();
radixSort(array, n);
int time_used = clock() - start;
cout << "Array Size: " << n << endl;
cout << "Time Used: " << time_used << " ms" << endl;
return 0;
}
两种算法实际花费的时间比较：
可以看到，优化后的基数排序速度要远远快于优化前的速度，而且随着问题规模的增大，优化后花费时间的增长趋势要比优化前平缓得多。
作者：Wray Zheng
原文：http://www.codebelief.com/article/2017/05/radix-sort-algorithm-implementation-and-improvement/
