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

发表于 分类于 ， Waline： 阅读次数： 本文字数： 1k 阅读时长 ≈ 3 分钟

　　基数排序是一个经典的非比较排序算法，其基本思路为将待排序列分配至各个桶，再重新组合，达到排序的目的。在这里提出一种基于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);
    }
}