c++ - 解释基数排序

Question

我正在尝试理解基数排序。特别是，我无法理解基数函数——更具体地说，j 和 k 循环。我不确定到底发生了什么。据我所见，j 循环似乎正在为 k 循环设置索引以用于形成排序的输出数组。如果有人能帮忙解释一下背后的逻辑，那就太好了!

// RADIX SORT BEGIN //

// Get the maximum value in arr[]
int getMax(int arr[], int size)
{
    int max = arr[0]; // Set max to presumably the first one
    int i = 1;
    while (i < size)
    {
        if (arr[i] > max) // We have a new max ladies and gents
            max = arr[i];
        i++;
    }
    return max;
}

// Do a sort of arr[] based off the digit represented by exp
void radixing(int arr[], int size, int exponent)
{
    int output[size];
    int count[10] = {0};

    // Tally the amount of numbers whose LSB based off current exponent
    // is 0-9, represented by each
    // index in the array
    for (int i = 0; i < size; i++)
        count[ (arr[i]/exponent) % 10 ]++;

    for (int j = 1; j < 10; j++)
        count[ j ] += count [j - 1];

    for (int k = size - 1; k >= 0; k--)
    {
        output[ count[ (arr[k]/exponent) % 10 ] -1 ] = arr[k];
        count[ (arr[k]/exponent) % 10 ]--;
    }

    // Finalize output into the original array
    for (int o = 0; o < size; o++)
        arr[o] = output[o];
}

// Main radix sort function
void radixsort(int arr[], int size)
{
    // Find the max in the array to know the number of digits to traverse
    int max = getMax(arr, size);

    // Begin radixing by sorting the arr[] based off every digit until max
    // Exponent is 10^i where i starts at 0, the current digit number
    for (int exponent = 1; (max / exponent) > 0; exponent = exponent * 10)
        radixing(arr, size, exponent);
}
// RADIX SORT END //

Answer 1

我不会分解算法中的每个步骤，而是会告诉您它打算完成什么，您可以使用这些信息来了解它的工作原理。这看起来像是在执行所谓的 LSD 基数排序。

如果您曾经使用过卡片分类器(如今很难找到)，它的作用与此算法相同。这个想法是从最低有效数字开始，然后朝着最多的方向努力。卡片分类器将有 10 个箱子——每个数字一个。将选择一列(指数)，卡片将根据所选列的数字落入适当的箱子。

算法所做的是计算给定指数列中每个数字的记录数，然后按顺序输出那么多记录。实际上，它使用计数来计算输出数组的偏移量。

现在对于给定列(指数)的记录按顺序移动到下一个更高的指数。

编辑:有点修饰。