学步园

using namespace std;

// 把32位整数看成8位的16进制整数
void RadixSort(vector& v)
{
    vector tempStor(v.size());
    vector offset(0x10);
    vector count(0x10);

    // 按照16进制对32位整数进行排序,总共进行8趟
    for (int digit = 0; digit < 8; digit++)
    {
        // 对vector中的整数按照第 digi位进行静态排序，静态排序的算法使用计数排序
        count.assign(count.size(),0);
        for (vector::iterator countIter = v.begin(); countIter != v.end(); countIter++)
        {
            int curDigitValue =  ( (*countIter)>>(digit*4) ) & 0xF; //取第digit位的16进制值
            count[curDigitValue]++;
        }

        // 计算每种数字的偏移量
        for (int iter = 1; iter < 0x10; iter++)
            offset[iter] = ( offset[iter-1] + count[iter-1] );

        // 把每个元素放到临时数组中正确的位置上
        for (int iter = 0; iter < v.size(); iter++)
        {
            int curDigitValue = ( ( v[iter] )>>(digit<<2) ) & 0xF; //取第digit位的16进制值
            tempStor[offset[curDigitValue]] = v[iter];
            offset[curDigitValue]++;
        }

        // 把临时数组拷回原始数组
        v.assign(tempStor.begin(), tempStor.end());
    }
}