我用 wiki 上面的 code 来说明一下好了:

void radixsort(int data[], int n) //基数排序
{
    int d = maxbit(data, n);
    int *tmp = new int[n];
    int *count = new int[10]; //计数器
    int i, j, k;
    int radix = 1;
    
    for(i = 1; i <= d; i++) //进行d次排序
    {
        // 分段1
        for (j = 0; j < 10; j++) {
            count[j] = 0;
        }
        
        // 分段2    
        for (j = 0; j < n; j++) {
            k = (data[j] / radix) % 10;
            count[k]++;
        }
        
        // 分段3
        for (j = 1; j < 10; j++) {
            count[j] = count[j - 1] + count[j];
        }
        
        // 分段4
        for (j = n - 1; j >= 0; j--) {
            k = (data[j] / radix) % 10;
            tmp[count[k] - 1] = data[j];
            count[k]--;
        }
        
        // 分段5
        for (j = 0; j < n; j++) {
            data[j] = tmp[j];
        }
        
        radix = radix * 10;
    }
    delete []tmp;
    delete []count;
}

这边的 code 我改写了一下并用 comments 标注了分段以方便讨论。

我这边举个例子来说明一下好了, 假设我们要排序的 data 如下:

int data[10] = {72, 99, 6, 25, 17, 22, 35, 64, 98, 12};

我们以 10 进位为基底来进行排序, 所以我们需要准备 10 个 buckets 编号为 0~9。

如果对radix sort 有基本认识的人会知道我们会依次进行d 个回合, 每回合利用第k 位来分配桶子, 以这个例子而言, 最大的数字为两位数, 所以:

d == 2  // 進行兩個回合

我们在这里仅探讨一个回合内发生的事情。假设我们现在进行第一回合, 也就是利用个位数来分配排序。

分段1

此处没什么特别的, 我们将 count 从 0~9 的值都清空为 0。

分段2

k = (data[j] / radix) % 10; 是要算出整数 data[j] 的第 k 位数字是多少, 在这个回合代表的就是 data[j] 的个位数字是多少。

所以这段的意思是, 将每个资料data[j] 依据其个位数字放到对应的bucket 中, 虽然我们并没有真实产生buckets 来存放资料, 但对应的count 反应出了桶内有几个资料项。

分段3

此处是个关键, 题主的问题点就在这里, 不过这里要看懂还必须看懂下一段, 我们先观察他做的事情, 在这里他将每个buckets 对应的count 累加起来。

count[j] = count[j - 1] + count[j];

分段4

本段是第 2 个关键, 在这里我们从 data 的最后一项依序往前将之摆放到 tmp 中, 且完成这回合依第 k 位分配排序的任务。

那这下面这个分配是什么意思呢:

tmp[count[k] - 1] = data[j];
count[k]--;

其实我们可以这样看 分段3 动作的意义:

你会发现:

• original count 代表了该桶中的资料数量, 也代表他会被分配到多少个 tmp index

• final count 代表了该桶中资料分配到的最大 index 加 1

以编号5 的桶子为例, 包含25, 35 两数占了tmp 的前6(final count) 个位置, 所以从6 数回去两个idx, 4 跟5 分别就是25 和35 在tmp 中的位置。

所以我们这段才会从后面的数字开始放起(先35 再25), 35 放到count[k]-1(5), 再让count[k]--, 以让25 放到count[k]-1(4) 。

分段5

没有什么特别的, 把 tmp 中的资料抄回 data 中完成该回合的排序

结论

希望以上说明有让你明白一点

我回答过的问题: Python-QA