0

给定n32 位整数（假设它们是正数），您希望通过首先查看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，如果currentDigit = 0这意味着我在32我的整数中，那么为了得到下一个shift位，我按位右移32 - currentDigit - shift，然后我应用 AND 运算来获得shift最不重要的位，这正是我想要的位。

第二个问题是递归。我不认为我在正确的组上递归，但由于我不知道第一个问题是否真的得到了正确的解决，我目前不能对此多说。

对此的任何反馈将不胜感激。

先感谢您。

编辑：添加主函数以显示我的基数函数是如何被调用的。

4

1 回答 1

1

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

为了解释为什么 MSD 首先很慢，我将使用卡片分类器进行类比。想象一下，您有 1,000 张卡片，每张卡片都有 3 位数字，从 000 到 999，以随机顺序排列。通常，您使用第 3 位数字运行分拣机，最终每个箱中都有 100 张卡片，箱 0 存放带有“0”的卡片，...存放箱 9 存放带有“9”的卡片。然后，您将 bin 0 和 bin 9 中的卡片连接起来，并使用第 2 位和第 1 位再次通过分拣机运行它们，从而生成一组已排序的卡片。这是 3 次运行，每次运行 1000 张卡片，因此共有 3000 张卡片通过了分拣机。

现在再次从随机排序的卡片开始，并按第一个数字排序。您不能连接这些集合，因为具有较高第 1 位数字但较低第 2 位数字的卡最终会乱序。所以现在你必须运行 10 次，每次运行 100 张卡片。这会产生 100 组，每组 10 张卡片，您再次通过分拣机运行，得到 1000 组每组 1 张卡片，现在卡片已被分类。所以通过分类器的卡片数量仍然是 3,000，与上面相同，但您必须运行 111 次（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;
}
于 2015-02-25T18:42:08.187 回答