1

こんにちは、基数ソートのロジックを理解しようとしています。ウィキペディアのコードを参照しています。ここでは、配列と要素数を受け取るソートのソート関数を示します。コードは問題なく実行されていますが、コードのロジックを理解できません。while ループ内では、最初に 10 桁のバケット配列を初期化します。これは、配列の最初と 2 番目のインデックスの 1 と 2 の数を保持します。しかしその後、何をしようとしているのかを理解するのは非常に困難です。

static void sort(int a[],int n)
{
int i=0;
int m =a[0];
int b[]=new int[n];
int exp=1;


      for (i = 0; i < n; i++)
      {
        if (a[i] > m)
          m = a[i]; 
      }

      while (m / exp > 0)
      {
        int bucket[] =new int[10];
        for (i = 0; i < n; i++)
          bucket[a[i] / exp % 10]++;


        for (i = 1; i < 10; i++)
          bucket[i] += bucket[i - 1];
        for (i = n - 1; i >= 0; i--)
          b[--bucket[a[i] / exp % 10]] = a[i];
        for (i = 0; i < n; i++)
          a[i] = b[i];
        exp *= 10;

          System.out.println("\nPASS   : ");
          for(int c:a){
        System.out.print(c+",");
    }
          System.out.println();
      }

}

誰でもこれで私を助けることができますか？ありがとう

4

1 に答える 1

2

基数ソートの仕組みを知っていても、このコードを理解するには多少の努力が必要です。このコードからリバース エンジニアリングを試みるよりも、まず基数ソートの抽象的な説明を理解する方が簡単です。

コードに関するいくつかの技術的な観察:

  • 外部ループexpは、1、10、100... から連続する 10 の累乗までを制御し、現在ソートしている数値の 10 進数の桁を決定します。
  • バケットへの実際のソートは 2 パスです。最初の内部ループは各バケットのカウントを計算し、3 番目のループは数値をそれぞれのバケットに分散します (各バケット内とバケット内の両方で n から 1 にa[]なります)。
  • バケットは、補助b[]配列の間隔として表されます (そのオフセットは、最初の内部ループからのバケット数に基づいて、2 番目の内部ループで事前に計算されます)。
  • 2 番目のループの後にbucket[d]は、アクティブな桁 (並べ替える桁) が である数値を格納する間隔の上限 (排他的) のインデックスがありますd。バケット間隔は、この端から下に向かって埋められます。
于 2012-11-29T21:57:00.427 に答える