排序算法之基数排序
前期准备
我们提前定义一下基础操作：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <class E>
class Sort
{
protected:
// 得到最大值索引
static int v_max_index(vector<E> &a)
{
int biggest = (int)*max_element(begin(a), end(a));
return biggest;
}
// 得到最小值索引
static int v_min_index(vector<E> &a)
{
int biggest = (int)*min_element(begin(a), end(a));
return biggest;
}
}
具体过程
假定我们有一个待排数组a[]={213,119,32,10,1,21}。
我们新建两个辅助数组count[]和tmp[]，count[]记录当前位的元素个数，每位的数值是[0...9]这个范围，所以count[]的长度为10，tmp[]辅助存储a[]的元素，长度和a[]的相等，基数排序不是一个原地排序。
1
2
3
4
5
6
7
int l = a.size();
vector<E> temp(l);
vector<E> count(10, 0);
int k = 0;
//提取当前的位数的值
int digit = 1;
如下图：
首先，我们要定义一个方法max_digit()获取a[]的最大值的位数d，比如上面的最大值为213，所以d = 3。这个d控制最外层的循环，以便依次对个位、十位、百位∙∙∙∙∙∙进行处理，基数排序先对最低有效位进行排序。
1
2
3
4
5
6
7
8
9
10
11
12
// 得到最大位数
static int max_digit(vector<E> &a)
{
int max = v_max_index(a);
int d = 1;
while (max >= 10)
{
max = max / 10;
d++;
}
return d;
}
然后我们进行类似计数排序的过程，
1. 创建count[]数组
第一步是先将count[]所有元素重置为0，现在是刚开始的阶段，我们初始化位置控制变量p = 1 ，即从个位开始，我们先对个位的数值进行统计，初始化一个遍历指针i = 0，取出a[0] = 213，得到该元素的个位k = (a[0] / digit ) % 10 = (213 / 1) % 10 = 3，将count[k]加一，即个位为3的元素多了一个，之后i++进行下一轮循环，直到遍历完所有元素，如下图：
i=0，先取出a[0]进行处理：
i=1,取出a[1]：
如此重复上述过程直到到达最后一个元素：
部分代码如下：
1
2
3
4
5
for (int j = 0; j < l; j++)
{
k = (a[j] / digit) % 10;
count[k]++;
}
最后我们得到了一个个位的计数数组count[]={1,2,1,1,0,0,0,0,0,1}，下一步是将这个数组进行一个处理，使得其可以表征一些位置信息，比如个位为1的元素位置在个位为0的元素后面在个位为2的元素前面，怎么实现这个处理，其实很简单，只需当前位的个数加上减一位的个数：count[i] = count[i] + count[i - 1]，得到处理过的count[]，过程如下：
代码如下：
1
2
for (int j = 1; j < 10; j++)
count[j] = count[j] + count[j - 1];
2.使用上述生成的count[]进行排序
这个过程比较简单，就是倒过来遍历a[]，经过式$(1)$的变化得到经过个位排序的tmp[]，然后把tmp[]复制到a[]。
过程如下：
然后将count[1]的值减一，之后j = 4 :
然后将count[1]的值减一，之后j = 3 :
然后将count[0]的值减一，之后j = 2 :
然后将count[2]的值减一，上图的count[0]应为0，不想改图了，之后j = 1 :
然后将count[9]的值减一，之后j = 0 :
这样我们就排好了个位的顺序，然后我们将tmp[]的内容复制给a[]，将digit = digit * 10= 1 * 10 = 10来提取十位的数值，进行下一轮的循环，重复1和2的过程，直到最外层循环超过了最大值位数d为止，后面的具体过程就不具体讲了，可以自己动手模拟模拟。
这样我们可以写出代码了：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 基数排序
static void Radix(vector<E> &a)
{
int l = a.size();
vector<E> temp(l);
vector<E> count(10, 0);
int k = 0;
int digit = 1;
int d = max_digit(a);
for (int i = 1; i <= d; i++)
{
for (int j = 0; j < 10; j++)
count[j] = 0;
for (int j = 0; j < l; j++)
{
k = (a[j] / digit) % 10;
count[k]++;
}
for (int j = 1; j < 10; j++)
count[j] = count[j] + count[j - 1];
for (int j = l - 1; j >= 0; j--)
{
k = (a[j] / digit) % 10;
temp[count[k] - 1] = a[j];
--count[k];
}
for (int j = 0; j < l; j++)
a[j] = temp[j];
digit = digit * 10;
}
}
测试
首先需要一个生成测试用例的函数：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 测试用例生成
// n为生成的数量，RangeL和RangeR表示生成的数在这两个之间
static vector<E> generateRandomA(int n, int RangeL, int RangeR)
{
vector<E> a;
if (RangeL > RangeR)
{
int temp = RangeL;
RangeL = RangeR;
RangeR = temp;
}
srand((unsigned)time(NULL));
for (int i = 0; i < n; i++)
{
a.push_back((E)(rand() % (RangeR - RangeL + 1) + RangeL));
}
return a;
}
还需要一个时间测试函数，时间精确到纳秒(ns)：
1
2
3
4
static long long getCurrentTimeNano()
{
return std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now().time_since_epoch()).count();
}
将升序的数组反向排序：
1
2
3
4
5
// 将降序排列
static void re_vet(vector<E> &a)
{
std::sort(a.rbegin(), a.rend());
}
随后进行测试：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int main()
{
int max = 20000;
int min = 0;
int num = 30000;
vector<int> a = Sort<int>::generateRandomA(num, min, max);
startTime = (double) Sort<int>::getCurrentTimeNano();
Sort<int>::Radix(a5);
endTime = (double) Sort<int>::getCurrentTimeNano();
elapsedNanoseconds = (endTime - startTime)/1000000.0;
printf("基数排序平均情况所需时间: %f ms\n", elapsedNanoseconds);
startTime = (double) Sort<int>::getCurrentTimeNano();
Sort<int>::Radix(a5);
endTime = (double) Sort<int>::getCurrentTimeNano();
elapsedNanoseconds = (endTime - startTime)/1000000.0;
printf("基数排序有序情况所需时间: %f ms\n", elapsedNanoseconds);
//反向排序
Sort<int>::re_vet(a5);
startTime = (double) Sort<int>::getCurrentTimeNano();
Sort<int>::Radix(a5);
endTime = (double) Sort<int>::getCurrentTimeNano();
elapsedNanoseconds = (endTime - startTime)/1000000.0;
printf("基数排序逆序情况所需时间: %f ms\n", elapsedNanoseconds);
cout << endl;
}
结果：
1
2
3
4
5
待排数组有30000个元素。
基数排序平均情况所需时间: 4.363448 ms
基数排序有序情况所需时间: 4.207993 ms
基数排序逆序情况所需时间: 5.190794 ms
分析
空间复杂度：我们用到了和输入数组等大小的辅助数组和一个固定大小的辅助数组，故空间复杂度为$O(n+1) = O(n)$。
时间复杂度：其时间复杂度为$O (nlog(r)m)$，其中$r$为所采取的基数，而$m$为堆数。
基数排序是一个稳定的算法。
可视化过程：
输入：768个元素，范围在[0, 256]。
