我复制了完整的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;
}
我用 wiki 上面的 code 來說明一下好了:
這邊的 code 我改寫了一下並用 comments 標註了分段以方便討論。
我這邊舉個例子來說明一下好了, 假設我們要排序的
data如下:我們以 10 進位為基底來進行排序, 所以我們需要準備 10 個 buckets 編號為 0~9。
如果對radix sort 有基本認識的人會知道我們會依次進行d 個回合, 每回合利用第k 位來分配桶子, 以這個例子而言, 最大的數字為兩位數, 所以:
我們在這裡只探討一個回合內發生的事情。假設我們現在進行第一回合, 也就是利用個位數來分配排序。
分段1
此處沒什麼特別的, 我們將
count從 0~9 的值都清空為 0。分段2
k = (data[j] / radix) % 10;是要算出整數data[j]的第 k 位數字是多少, 在這個回合代表的就是data[j]的個位數字是多少。所以這段的意思是, 將每個資料
data[j]依據其個位數字放到對應的bucket 中, 雖然我們並沒有真實產生buckets 來存放資料, 但對應的count反應出了桶內有幾個資料項。分段3
這裡是個關鍵, 題主的問題點就在這裡, 不過這裡要看懂還必須看懂下一段, 我們先觀察他做的事情, 在這裡他將每個buckets 對應的
count累加起來。00)00)33)33)44)66)77)88)99)10分段4
本段是第 2 個關鍵, 在這裡我們從
data的最後一項依序往前將之擺放到tmp中, 且完成這回合依第 k 位分配排序的任務。那這下面這個分配是什麼意思呢:
其實我們可以這樣看 分段3 動作的意義:
00)00)33)33)44)66)77)88)99)10你會發現:
original count代表了該桶中的資料數量, 也代表他會被分配到多少個tmpindexfinal 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