问题描述
我复制了完整的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 hereint 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; }
问题解答
回答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次排序 {// 分段1for (j = 0; j < 10; j++) { count[j] = 0;}// 分段2 for (j = 0; j < n; j++) { k = (data[j] / radix) % 10; count[k]++;}// 分段3for (j = 1; j < 10; j++) { count[j] = count[j - 1] + count[j];}// 分段4for (j = n - 1; j >= 0; j--) { k = (data[j] / radix) % 10; tmp[count[k] - 1] = data[j]; count[k]--;}// 分段5for (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。
分段2k = (data[j] / radix) % 10; 是要算出整數 data[j] 的第 k 位數字是多少, 在這個回合代表的就是 data[j] 的個位數字是多少。
所以這段的意思是, 將每個資料 data[j] 依據其個位數字放到對應的 bucket 中, 雖然我們並沒有真實產生 buckets 來存放資料, 但對應的 count 反應出了桶內有幾個資料項。
Bucket No.datacount0{ }01{ }02{72, 22, 12}33{}04{64}15{25, 35}26{6}17{17}18{98}19{99}1分段3此處是個關鍵, 題主的問題點就在這裡, 不過這裡要看懂還必須看懂下一段, 我們先觀察他做的事情, 在這裡他將每個 buckets 對應的 count 累加起來。
count[j] = count[j - 1] + count[j];Bucket No.dataoriginal countfinal count0{ }001{ }0 (+0)02{72, 22, 12}3 (+0)33{}0 (+3)34{64}1 (+3)45{25, 35}2 (+4)66{6}1 (+6)77{17}1 (+7)88{98}1 (+8)99{99}1 (+9)10分段4
本段是第 2 個關鍵, 在這裡我們從 data 的最後一項依序往前將之擺放到 tmp 中, 且完成這回合依第 k 位分配排序的任務。
那這下面這個分配是甚麼意思呢:
tmp[count[k] - 1] = data[j];count[k]--;
其實我們可以這樣看 分段3 動作的意義:
Bucket No.dataoriginal countfinal countcorresponding idx of tmp0{ }00X1{ }0 (+0)0X2{72, 22, 12}3 (+0)30, 1, 23{}0 (+3)3X4{64}1 (+3)435{25, 35}2 (+4)64, 56{6}1 (+6)767{17}1 (+7)878{98}1 (+8)989{99}1 (+9)109你會發現:
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
