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

ウィキのコードを使用して説明します。

リーリー

ここでコードを書き直し、議論を容易にするためにセクションにコメントを付けました。

例を示して、data を次のようにソートするとします。 リーリー

10進数でソートするので、0～9までのバケットを10個用意する必要があります。

基数ソートの基本を理解している場合は、d ラウンドを順番に実行し、各ラウンドで k 番目のビットを使用してバケットを割り当てることがわかります。この例では、最大の数値は 2 桁です。番号なので:

リーリー

ここでは 1 ターンに何が起こるかについてのみ話しています。ここで、1 桁を使用して並べ替えを割り当てる最初のラウンドに進むとします。

セクション 1

ここでは特に何もせず、

の0~9の値をすべて0にクリアします。 count

セクション 2

は、整数 k = (data[j] / radix) % 10; の k 番目の桁を計算します。このラウンドでは、data[j] の 1 桁を表します。 data[j]

この段落の意味は、各データ

をその 1 桁の番号に従って対応するバケットに入れることです。実際にデータを保存するためのバケットを生成しませんでしたが、対応する data[j] はバケットを反映します。内部にはいくつかのデータ項目があります。 count

セクション 3

ここが質問者の問題です。これを理解するには、まず次の段落を理解する必要があります。ここで質問者が各バケットに対応する count を加算します。

リーリー

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 番目の位置に従ってソートするタスクを完了します。

では、以下の分布は何を意味しますか:

リーリー

実際、セグメント 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 インデックス

の数も表します。

• final count は、バケット内のデータに割り当てられた最大インデックスに 1

を加えたものを表します。

5 番のバケットを例にとると、25 と 35 を含む 2 つの数値が tmp の最初の 6 (final count) の位置を占めるため、6、4、< 🎜 から 2 つの idx を逆算します。 > はそれぞれ 5 の 25 と 35 の位置です。 tmp

そのため、この段落の最後の数字から開始し (最初は 35、次に 25)、35 は

(5)、次に count[k]-1 に配置され、25 は count[k]--(4) に配置されます。 。 count[k]-1

セクション 5

特別なことは何もありません。

のデータを tmp にコピーして戻し、このラウンドの並べ替えを完了しますdata

結論

上記の説明が少しでも理解に役立つと幸いです

---

私が回答した質問: Python-QA