基数排序如何工作？

我不知道为什么这对我来说如此难以理解。我浏览了 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];

在数学中，radix 表示基数，其中小数是以 10 为基数。想象一下，您有一些数字，其中一些数字有多个数字，例如

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

为简单起见，假设您想使用小数基数 (=10) 进行排序。然后你首先将数字按单位分开，然后再次将它们组合在一起；接下来，您将数字按十分开，然后再次将它们放在一起；然后按数百个依此类推，直到所有数字都排序完毕。每次循环时，只需从左到右阅读列表即可。您还可以想象您将数字分成不同的桶。这是一个使用说明5, 213, 55, 21, 2334, 31, 20, 430

按单位划分：

• 零：20、430

• 个数：21、31

• twos:

• 三分球：213

• 四人：2334

• 五：5、55

  重新组合起来：20、430、21、31、213、2334、5、55

要将它们重新组合在一起，请首先阅读zeroes桶，然后ones桶，然后依此类推，直到您阅读nines bucket.

以十位分隔：

• 零：05

• 个数：213

• 两人：20、21

• 三位数：430、31、2334、

• fours:

• 五：55

  重新组合：5、213、20、21、430、31、2334、55

相隔数百：

• 零：005、020、021、031、055

• ones:

• 两人：213

• 三分球：2334

• 四人：430

• fives:

  重新组合起来：5、20、21、31、55、213、2334、430

相隔数千：

• 零：0005、0020、0021、0031、0055、0213、0430

• ones:

• 两人：2334

• threes:

• fours:

• fives:

  重新组合在一起：5、20、21、31、55、213、430、2334

现在你已经完成了。我在 Geekviewpoint 上看到了一个很好的代码Java http://www.geekviewpoint.com/java/sorting/radixsort and in python http://www.geekviewpoint.com/python/sorting/radixsort