40

なぜこれが頭を包み込むのが難しいのかわかりません。私はwikiページと、基数ソートアルゴリズムが（バケットに関して）どのように機能するかを理解しようとしている疑似コード（および実際のコード）を調べました。

私はここで間違ったことを調べていますか？多分バケットソートを検討する必要がありますか？誰かが私にそれがどのように機能するかについての唖然としたバージョンを与えることができますか？参考までに、基数ソートを実行すると思われるコードブロックを次に示します。

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does
void radixSort(int* input, int size, int digit)
{
    if (size == 0)
        return;

    int[10] buckets;    // assuming decimal numbers

    // Sort the array in place while keeping track of bucket starting indices.
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit),
    // then let bucket[i+1] = bucket[i]

    for (int i = 0; i < 10; ++i)
    {
        radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1);
    }
}

また、非再帰的なソリューションも検討しました。

void radixsort(int *a, int arraySize)
{
    int i, bucket[sortsize], maxVal = 0, digitPosition =1 ;
    for(i = 0; i < arraySize; i++) {
        if(a[i] > maxVal) maxVal = a[i];
    }

    int pass = 1; 
    while(maxVal/digitPosition > 0) {
        // reset counter 
        int digitCount[10] = {0};

        // count pos-th digits (keys) 
        for(i = 0; i < arraySize; i++)
            digitCount[a[i]/digitPosition%10]++;

        // accumulated count 
        for(i = 1; i < 10; i++)
            digitCount[i] += digitCount[i-1];

        // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];

        for(i = 0; i < arraySize; i++)
            a[i] = bucket[i];

        cout << "pass #" << pass++ << ": ";
        digitPosition *= 10;
    } 

}

具体的には、この行は私に問題を与えています。ペンと紙でそれを歩いてみましたが、それでもこれが何をしているのか理解できません：

   // To keep the order, start from back side
        for(i = arraySize - 1; i >= 0; i--)
            bucket[--digitCount[a[i]/digitPosition%10]] = a[i];
4

4 に答える 4

103

数学では、基数は基数を意味し、小数は基数10になります。たとえば、次のように1桁以上の数があるとします。

5, 213, 55, 21, 2334, 31, 20, 430

簡単にするために、ソートに10進基数（= 10）を使用するとします。次に、数値を単位で区切り、次にそれらを再びまとめることから始めます。次に、数字を数十で区切ってから、もう一度まとめます。次に、すべての数値がソートされるまで、数百というように続きます。ループするたびに、リストを左から右に読んでください。また、数字をバケツに分けていることも想像できます。これがを使ったイラストです5, 213, 55, 21, 2334, 31, 20, 430

単位で区切る：

  • ゼロ：20、430

  • もの：21、31

  • 2つ：

  • スリー：213

  • 四つんばい：2334

  • ファイブ：5、55

    一緒に戻る：20、430、21、31、213、2334、5、55

それらを元に戻すには、最初にバケットを読み取りzeroes、次にバケットを読み取りones、次にバケットを読み取るまで続けますnines。

数十で区切る：

  • ゼロ：05

  • もの：213

  • 2：20、21

  • スリー：430、31、2334、

  • 四つんばい：

  • ファイブ：55

    一緒に戻る：5、213、20、21、430、31、2334、55

数百で区切る：

  • ゼロ：005、020、021、031、055

  • もの：

  • 2：213

  • スリー：2334

  • 四つんばい：430

  • ファイブ：

    一緒に戻る：5、20、21、31、55、213、2334、430

数千単位で区切る：

  • ゼロ：0005、0020、0021、0031、0055、0213、0430

  • もの：

  • 2：2334

  • スリー：

  • 四つんばい：

  • ファイブ：

    一緒に戻る：5、20、21、31、55、213、430、2334

これで完了です。私はJavaとPythonの両方でGeekviewpointでこれのための素晴らしいコードを見ました

于 2013-02-06T02:56:19.320 に答える
3

これがクイックソートの基本的な流れです。

1回目のパスの場合：カウントソートを使用して、最下位桁（1桁）に基づいて配列をソートします。元のリストでは435が835より下で発生したため、435は835より下であることに注意してください。

2番目のパスの場合：カウントソートを使用して、次の桁（10桁）に基づいて配列をソートします。608は前のリストの704の下で発生したため、ここでは608が704の下にあることに注意してください。同様に、（835、435）と（751、453）についても同様です。

3番目のパスの場合：カウントソートを使用して、最上位桁（100桁）に基づいて配列をソートします。435は前のリストの453の下で発生したため、ここでは435が453の下にあることに注意してください。同様に、（608、690）と（704、751）も同様です。

詳細については、codingeekに関するこのブログを参照し、明確に理解することができます。

于 2017-02-13T10:04:39.860 に答える
2

カードのデッキを考えてみてください。まず、スーツごとに4つの山に並べ替えます。次に、これらの4つの山を重ねて、ランクに基づいて13の山に分類します。それらを組み合わせると、ソートされたデッキができます。

于 2013-02-05T21:54:25.250 に答える
0

私のコードがあなたを助けるかもしれません:)

基数ソートのPythonのコードは次のとおりです。

import random,time

from random import randint

A=[random.randint(1,1212) for i in range(23)]


length = len(str(max(A)))

print(length) 

rang = 10

print(A)

start=time.time()

for i in range(length):

B = [[] for k in range(rang)]

for x in A:

    figure =x // (10**i) % 10

    B[figure].append(x)

A = []

for k in range(rang):

    A+=B[k]

end=time.time()

print(end-start)

print(A)
于 2020-04-30T13:58:51.083 に答える