c++ - 基数排序，有一句话看不懂？

Question

我复制了完整的c++办基数排序的算法实现如下：

        for(int i = 1;i<10;i++) {
            bucket[i] +=bucket[i-1];//这句话到底是做什么的？ wiki上面说是 //将tmp中的位置依次分配给每个桶 我表示还是看不懂？
        }

class RadixSort {
public:
    int* radixSort(int* A, int n) {
        // write code here
        int bucket[10] ={0};
        int count = getMaxCount(A,n);
        int index;
        int *temp = new int[n];
        for(int k = 1;k<=count;k++) {
            for(int i = 0;i<10;i++) {
                bucket[i] = 0;
            }
            for(int i = 0;i<n;i++) {
              index = getValueAt(A[i],k);
              bucket[index]++; 
            }
            for(int i = 1;i<10;i++) {
                bucket[i] +=bucket[i-1];//这句话到底是做什么的？ wiki上面说是 //将tmp中的位置依次分配给每个桶 我表示还是看不懂？
            }
            for(int i = n-1;i>=0;i--) {
                int pos = -- bucket[getValueAt(A[i],k)];
                temp[pos] = A[i];
            }
            for(int i = 0;i < n; i++) {
                A[i] = temp[i];
            }
             
        }
        delete[] temp;
        return A;
         
    }
    int getMaxCount(int* A,int n) {
        int max = A[0];
        int count = 1;
        for(int i= 1;i<n;i++) {
            if(A[i]>max) {
                max = A[i];
            }
        }
        while(max/10 > 0) {
            count++;
            max /= 10;
        }
        return count;
    }
    int getValueAt(int val,int pos) {
        while(--pos) {
            val /= 10;
        }
        return val%10;
         
    }

Answer 1

我用 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 反应出了桶内有几个资料项。

Bucket No.	data	count
0	{ }	0
1	{ }	0
2	{72, 22, 12}	3
3	{}	0
4	{64}	1
5	{25, 35}	2
6	{6}	1
7	{17}	1
8	{98}	1
9	{99}	1

分段3

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

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

Bucket No.	data	original count	final count
0	{ }	0	0
1	{ }	0 (+0)	0
2	{72, 22, 12}	3 (+0)	3
3	{}	0 (+3)	3
4	{64}	1 (+3)	4
5	{25, 35}	2 (+4)	6
6	{6}	1 (+6)	7
7	{17}	1 (+7)	8
8	{98}	1 (+8)	9
9	{99}	1 (+9)	10

分段4

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

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

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

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

Bucket No.	data	original count	final count	corresponding idx of tmp
0	{ }	0	0	X
1	{ }	0 (+0)	0	X
2	{72, 22, 12}	3 (+0)	3	0, 1, 2
3	{}	0 (+3)	3	X
4	{64}	1 (+3)	4	3
5	{25, 35}	2 (+4)	6	4, 5
6	{6}	1 (+6)	7	6
7	{17}	1 (+7)	8	7
8	{98}	1 (+8)	9	8
9	{99}	1 (+9)	10	9

你会发现:

• 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