序文：Javaデータ構造とアルゴリズムのトピックは、随時更新されます。読者はそれを監督することを歓迎します。この記事は、最も単純なソートアルゴリズムであるバケットソートから始まり、実装のアイデア、コード実装、パフォーマンス特性、バケツソートの適用シナリオを分析します。
0.その他のソートアルゴリズムインデックス
//www.vevb.com/article/120879.htm
1。バケツソーティングのアイデア
簡単な例：
6人の英語テストスコア（1〜10ポイント）のソート。スコアが[6、5、8、8、10、9]の場合、バケツでソートするというアイデアは10バケツを準備することであり、数字は順番に1〜10であり、スコアは6ポイントのバケツに6ポイント、2つの8ポイントなど、No。8バケツに配置されます...これはバケットソートの基本的なアイデアです。
実際、これは単純なバージョンです。 1〜10,000などのソートする要素のスパン範囲が比較的大きい場合、10,000バケツが必要ですか？実際、この場合、1つの要素が常にバケツに配置されるわけではありませんが、多くの場合、複数の要素がバケツに配置されます。実際、実際のバケットソートとハッシュリストには同じ原則があります。
実際のソートでは、各バケットの要素は通常、他のソートアルゴリズムを使用してソートされているため、より多くの場合、バケットソートは他のソートアルゴリズムと組み合わせて使用されます。
2。バケットソートコード
バケットソートのアイデアを分析した後、まずソートする要素の範囲を知る必要があります。上記を例にとって、長さ10の配列を10バケツとして宣言し、結果を1つずつバケットに入れ、バケットの値は+1で、最後にアレイサブスクリプが逆に出力します。アレイの各位置の値は数回出力されるため、基本的なバケットソートを実現できます。
Public Class Bucketsort {private int [] Buckets; private int [] array; public backetsort（int range、int [] array）{this.buckets = new int [range]; this.array = array; } /*sorting* / public void sort（）{if（array！= null && array.length> 1）{for（int i = 0; i <array.length; i ++）{buckets [array [i]] ++; }}}/*sorting output*/public void sortout（）{//（int i = backets.length-1; i> = 0; i - ）{for（int j = 0; j <buckets [i]; j ++）{system.out.print（i+"/t"）; }}}}テストコード：
public class sorttest {public static void main（string [] args）{testbucketssort（）; } private static void testbucketssort（）{int [] array = {5,7,5,4,6,4,1,2}; BucketSort BS = new BucketSort（10、Array）; bs.sort（）; bs.sortout（）; //出力プリントソート}}3。バケツソートパフォーマンス特性
バケットソーティングは、実際には、すべての要素をソートすることを繰り返して、順番に指定された位置に配置する必要があります。出力ソート時間が追加されている場合、すべてのバケットを通過する必要があります。したがって、バケットソートの時間の複雑さはo（n+m）、nはソートする要素の数、mはバケツの数、つまりソートされる要素の範囲です。このアルゴリズムは非常に高速なソートアルゴリズムですが、空間的な複雑さは比較的大きいです。
配置する要素のサイズの範囲が比較的大きい場合、配置する要素の数は比較的少ない場合、スペース廃棄物はより深刻です。配置される要素の分布は毎月均一であり、スペース使用率が高いほど、これは実際にはまれです。
上記のパフォーマンス分析を通じて、バケットソートの特性を取得できます。高速かつシンプルですが、同時にスペースの利用は低いです。ソートするデータが大きい場合、スペース使用率は耐えられません。
4。バケツソート適用シナリオ
バケットソートの特性によれば、バケットソートは一般に、データ範囲が比較的限られているか、ハッシュマッピングを介して特定の値を迅速に取得する必要があるなど、特定の要件があり、各数値をカウントする必要があるなど、特定の要件があります。しかし、これらはすべて、データの範囲を確認することに基づいています。スコープスパンが大きすぎる場合は、他のアルゴリズムの使用を検討してください。