バケットソートとは

バケット ソートはソート アルゴリズムです。動作原理は、配列を限られた数のバケットに分割することです。バケット ソートは、鳩の穴ソートの誘導結果でもあります。配列内の値がソートされるとき、均等に分散されている場合、バケット ソートは線形時間を使用しますが、バケット ソートは比較ソートではなく、「O(n log n)」の下限の影響を受けません。

バケットソート

N 個のキーワードの値の範囲が 0 から 0 までであることがわかっている場合M-1 の間で、M が N よりもはるかに小さい場合、バケット ソート アルゴリズムはキーワードの各値に対して「バケット」を作成します。つまり、M 個のバケットが作成されます。N 個のキーワードをスキャンするとき、各キーは対応する単語を入力します。バケットに分割し、自然に並べられるバケットの順序でそれらを収集します。

はじめに:

バケット ソート (バケット ソート) またはいわゆるボックス ソートは、ソート アルゴリズムであり、動作原理です。配列を限られた数のバケットに分割することです。各バケットは個別に並べ替えられます (他の並べ替えアルゴリズムを使用したり、再帰的にバケットの並べ替えを使用し続けることも可能です)。バケット ソートは、鳩の穴ソートの帰納的な結果です。バケット ソートでは、ソート対象の配列内の値が均等に分散されている場合、線形時間 (Θ(n)) が使用されます。ただし、バケット ソートは比較ソートではないため、O(n log n) 下限の影響を受けません。

定義

仮定: 入力は、ランダム プロセスによって生成された区間 [0, 1) 内に一様に分布した実数です。間隔 [0, 1) を等しいサイズの n 個のサブ間隔 (バケット) に分割します。各バケット サイズは 1/n です: [0, 1/n)、[1/n、2/n)、[2/n] , 3/n),…,[k/n, (k 1)/n),…n 個の入力要素をこれらのバケットに分配し、バケット内の要素を並べ替えて、バケットの入力 0 ≤A[1. . n]

以上がバケットソートとはの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。