0%

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

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

代码示例

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

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);
    }
}