Radix Sort如何工作？

Question

我不知道为什么这对我来说是如此困难.我查看了wiki页面和伪代码(以及实际代码),试图了解基数排序算法的工作原理(关于存储桶).

我在这里看错了吗？我应该考虑一下桶排序吗？有人能给我一个愚蠢的版本吗？作为参考,这里是一个可能执行基数排序的代码块:

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

我也看过非递归解决方案:

void radixsort(int *a, int arraySize)
{
    int i, bucket[sortsize], maxVal = 0, digitPosition =1 ;
    for(i = 0; i < arraySize; i++) {
        if(a[i] > maxVal) maxVal = a[i];
    }

    int pass = 1; 
    while(maxVal/digitPosition > 0) {
        // reset counter 
        int digitCount[10] = {0};

        // count pos-th digits (keys) 
        for(i = 0; i < arraySize; i++)
            digitCount[a[i]/digitPosition%10]++;

        // accumulated count 
        for(i = 1; i < 10; i++)
            digitCount[i] += digitCount[i-1];

        // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];

        for(i = 0; i < arraySize; i++)
            a[i] = bucket[i];

        cout << "pass #" << pass++ << ": ";
        digitPosition *= 10;
    } 

}

具体来说,这条线给我带来了麻烦.我试过用笔和纸走过它,但我仍然无法弄清楚这是做什么的:

   // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];

Answer 1

在数学中,基数表示基数,其中十进制将是基数10.想象一下,你有一些数字,其中一些数字有多个像

5, 213, 55, 21, 2334, 31, 20, 430

为简单起见,假设您要使用十进制基数(= 10)进行排序.然后你将开始按单位分隔数字,然后再将它们组合在一起; 接下来你将数字除以数十,然后再将它们组合在一起; 然后是数百个,依此类推,直到所有的数字都被排序.每次循环时,只需从左到右阅读列表.您还可以想象您将数字分成多个桶.这是一个使用的插图5, 213, 55, 21, 2334, 31, 20, 430

按单位分开:

• 零:20,430

• 那些:21,31

• 三三两两:

• 三分:213

• 四肢:2334

• 五点:5,55

  回到一起:20,430,21,31,213,2334,5,55

要将它们重新组合在一起,首先要读取zeroes桶,然后读取桶,然后再读取桶ones,直到读取nines桶为止.

分开数十:

• 零:05

• 那些:213

• 二十:20,21

• 三人:430,31,2334,

• 四肢:

• 五:55

  回到一起:5,213,20,21,430,31,2334,55

分开数百:

• 零:005,020,021,031,055

• 那些:

• 二三:213

• 三个:2334

• 四肢:430

• 五岁以下儿童:

  回到一起:5,20,21,31,55,213,2334,430

数以千计:

• 零:0005,0020,0021,0031,0055,0213,0430

• 那些:

• 二三:2334

• 三分球:

• 四肢:

• 五岁以下儿童:

  回到一起:5,20,21,31,55,213,430,2334

你现在完成了.我在Java和python中都在Geekviewpoint上看到了一个很好的代码