0%

基于16进制的整型基数排序

  基数排序是一个经典的非比较排序算法,其基本思路为将待排序列分配至各个桶,再重新组合,达到排序的目的。在这里提出一种基于16进制的分配法,每一轮有0x0~0xf共16个桶,重复分配8次,可以达到整型排序的目的。而负数在计算机内部使用其补码表示,因此在最后一趟收集的过程中,先收集0x8~0xf桶,再收集0x0~0x7桶,即可顺利的完成排序。

代码示例

  以下是使用C++编写的基于16进制的整型基数排序代码示例,使用位运算符提高运算速度。

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
void radix_sort_merge(vector<int> &data, vector<vector<int>> &buckets, int &index, int start, int end)
{
for (int i = start; i < end; i++)
for (auto iter = buckets[i].begin(); iter != buckets[i].end(); iter++)
data[index++] = *iter;
}

void radix_sort(vector<int> &data)
{
vector<vector<int>> buckets(16);
for (unsigned int times = 0, hex = 0xf; times <= 28; times += 4, hex <<= 4)
{
for (auto iter = buckets.begin(); iter != buckets.end(); iter++)
iter->clear();
for (auto iter = data.begin(); iter != data.end(); iter++)
buckets[(*iter & hex) >> times].push_back(*iter);
int index = 0;
if (times == 28)
{
radix_sort_merge(data, buckets, index, 8, 16);
radix_sort_merge(data, buckets, index, 0, 8);
}
else
radix_sort_merge(data, buckets, index, 0, 16);
}
}