phpstudy集成环境

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

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

我复制了完整的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 來說明一下好了:

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

你會發現:

以 編號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

【热门文章】
【热门文章】