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

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