无法让基数排序算法在 C++ 中工作

Question

给定 n 32 位整数（假设它们是正数），您希望通过首先查看总位中最重要的 shift 并对创建的每个桶进行递归排序来对它们进行排序通过这些位上的排序整数。

所以如果 shift 是 2，那么你将首先查看每个 32 位整数中的两个最高有效位，然后应用计数排序。最后，从您将获得的组中，您递归每个组并通过查看第三和第四个最高有效位开始对每个组的数字进行排序。您以递归方式执行此操作。

我的代码如下：

void radix_sortMSD(int start, int end, 
          int shift, int currentDigit, int input[])
{

    if(end <= start+1 || currentDigit>=32) return;

    /*
     find total amount of buckets
     which is basically 2^(shift)
    */
    long long int numberOfBuckets = (1UL<<shift);

    /*
     initialize a temporary array 
     that will hold the sorted input array
     after finding the values of each bucket.   
    */

    int tmp[end];

   /*
     Allocate memory for the buckets.
   */
   int *buckets = new int[numberOfBuckets + 1];

   /*
       initialize the buckets,
        we don't care about what's 
     happening in position numberOfBuckets+1
   */
   for(int p=0;p<numberOfBuckets + 1;p++)
         buckets[p] = 0;

   //update the buckets
   for (int p = start; p < end; p++)
      buckets[((input[p] >> (32 - currentDigit - shift)) 
                &   (numberOfBuckets-1)) + 1]++;

   //find the accumulative sum
   for(int p = 1; p < numberOfBuckets + 1; p++)
       buckets[p] += buckets[p-1];

   //sort the input array input and store it in array tmp   
   for (int p = start; p < end; p++){ 
    tmp[buckets[((input[p] >> (32 - currentDigit- shift)) 
            & (numberOfBuckets-1))]++] = input[p];
    }

   //copy all the elements in array tmp to array input
   for(int p = start; p < end; p++)
          input[p] = tmp[p];

   //recurse on all the groups that have been created
   for(int p=0;p<numberOfBuckets;p++){
       radix_sortMSD(start+buckets[p], 
       start+buckets[p+1], shift, currentDigit+shift, input);
    }

    //free the memory of the buckets
    delete[] buckets;
}

  int main()
  {

        int a[] = {1, 3, 2, 1, 4, 8, 4, 3};
        int n = sizeof(a)/sizeof(int);
        radix_sortMSD(0,n, 2,0,a);
        return 0;
   }

我可以想象这段代码中只有两个问题。

第一个问题是我是否真的在每次迭代中得到正确的整数位。我假设如果我在位置 currentDigit where if currentDigit = 0 这意味着我在位 32 我的整数，然后得到下一个 shift 位，我右移 32 - currentDigit - shift 个位置，然后我应用 AND 运算来获得 shift 最低有效位，这正是我想要的位。

第二期是递归。我不认为我在正确的组上进行了递归，但由于我不知道第一个问题是否真的得到了正确解决，所以我现在不能说更多。

如有任何反馈，我们将不胜感激。

提前致谢。

编辑：添加了 main 函数以显示如何调用我的基数函数。

Answer 1

另一个更新，转换为数组类型的模板。 Tmp 数组现在作为参数传递。删除了复制步骤，并向 return 排序数据最终所在的缓冲区添加了一个辅助函数。使用 400 万个 64 位无符号整数进行测试，它可以工作，但速度很慢。 numberOfBits = 4 时实现的最快时间。numberOfBits 不再需要准确地除以每个元素的位数。

为了解释为什么 MSD first 速度慢，我将使用卡片分类器类比。假设您有 1,000 张卡片，每张卡片有 3 个数字，从 000 到 999，顺序是随机的。通常你运行通过带有第 3 个数字的分拣机，最后在每个箱子里有 100 张卡片，箱子 0 存放带有“0”的卡片，...箱子 9 存放带有“9”的卡片.然后，您将 bin 0 到 bin 9 的卡片连接起来，然后运行使用第 2 个数字再次通过分类器，然后再次使用第 1 个数字，从而产生一组排序的卡片。那是 3 运行秒，每个运行上有 1000 张卡片，所以总共有 3000 张卡片通过了分类器。

现在再次从随机排序的卡片开始，按照第一个数字排序。您不能连接这些集合，因为第一位数字较高但第二位数字较低的卡片最终会乱序。所以现在你必须用 100 张卡片做 10 运行s。这会产生 100 组，每组 10 张卡片，您运行再次通过分类器，产生 1000 组，每组 1 张卡片，现在卡片已经排序。所以通过分类器的卡片数量运行仍然是 3,000，与上面相同，但是你必须做 111 运行s（1 有 1000 张卡片，10 有 100 张卡片，100 有 10 张卡片套）。

template <typename T>
void RadixSortMSD(size_t start, size_t end, 
          size_t numberOfBits, size_t currentBit, T input[], T tmp[])
{
    if((end - start) < 1)
        return;

    // adjust numberOfBits if currentBit close to end element
    if((currentBit + numberOfBits) > (8*sizeof(T)))
        numberOfBits = (8*sizeof(T)) - currentBit;

    // set numberOfBuckets
    size_t numberOfBuckets = 1 << numberOfBits;
    size_t bitMask = numberOfBuckets - 1;
    size_t shift = (8*sizeof(T)) - currentBit - numberOfBits;

    // create bucket info
    size_t *buckets = new size_t[numberOfBuckets+1];
    for(size_t p = 0; p < numberOfBuckets+1; p++)
        buckets[p] = 0;
    for(size_t p = start; p < end; p++)
        buckets[(input[p] >> shift) & bitMask]++;
    size_t m = start;
    for(size_t p = 0; p < numberOfBuckets+1; p++){
        size_t n = buckets[p];
        buckets[p] = m;
        m += n;
    }

    //sort the input array input and store it in array tmp   
    for (size_t p = start; p < end; p++){ 
        tmp[buckets[(input[p] >> shift) & bitMask]++] = input[p];
    }

    // restore bucket info
    for(size_t p = numberOfBuckets; p > 0; p--)
        buckets[p] = buckets[p-1];
    buckets[0] = start;

    // advance current bit
    currentBit += numberOfBits;
    if(currentBit < (8*sizeof(T))){
        //recurse on all the groups that have been created
        for(size_t p=0; p < numberOfBuckets; p++){
            RadixSortMSD(buckets[p], buckets[p+1],
                numberOfBits, currentBit, tmp, input);
        }
    }

    //free buckets
    delete[] buckets;
    return;
}

template <typename T>
T * RadixSort(T *pData, T *pTmp, size_t n)
{
size_t numberOfBits = 4;
    RadixSortMSD(0, n, numberOfBits, 0, pData, pTmp);
    // return the pointer to the sorted data
    if((((8*sizeof(T))+numberOfBits-1)/numberOfBits)&1)
        return pTmp;
    else
        return pData;
}

无法让基数排序算法在 C++ 中工作

Can't get the radix sort algorithm to work in C++

c++

sorting

algorithm

recursion

radix