データ構造とアルゴリズム-線形ソート

1.レビュー
時間複雑度O(n 2)、小規模データに適したバブルソート、選択ソート、挿入ソート、および適用が広範な時間複雑度O(nlogn)のヒルソート、集計ソート、高速ソートのいくつかの非線形ソートについて前述した.実際には、これらのソートには、データの比較と移動に基づいている特性がありますが、今日紹介したこれらの線形ソートでは、データの比較と移動に関与しないため、時間の複雑さはO(n)です.
2.バケツのソート
バケツソートの考え方は、ソートするデータを一定の範囲で秩序あるバケツに分け、バケツ内でソートし、バケツから順番にデータを取り出すことで、データ全体が秩序正しくなります.
例えば、[0-50]サイズのデータのセットを並べ替えると、5つのバケツに分けることができます.各バケツに格納されているデータの範囲は、[1-10]、[11-20]、[21-30]です.このように、下図のように、バケツ内のデータを並べ替えて、順番に取り出すと、データ全体が秩序正しくなります.
実際,バケツソートの応用シーンは非常に限られており,データに対する要求は比較的厳しい.まず、各バケツのデータ範囲が秩序正しく、上のように順番に並べてこそ、バケツから取り出したデータが秩序正しく保たれることを保証することができ、次に、データが各バケツに均一に区分されることを保証し、データがあるバケツまたはいくつかのバケツに集中すると、時間の複雑さが低下する.極端な場合、データがすべて1つのバケツに分割されると、非線形ソートになります.
簡単なバケツのソートをシミュレートします.

public class BucketSort {

    //    ：    10000   ，   0-100000  
    //  100  ，           ：0-999, 1000-1999, 2000-2999，    
    public static void bucketSort(int[] data){
        //  100  ，  ArrayList   
        ArrayList> buckets = new ArrayList<>(100);
        for (int i = 0; i < 100; i++) {
            buckets.add(new ArrayList<>());
        }
        //    ，        
        for (int i = 0; i < data.length; i++) {
            buckets.get(data[i] / 1000).add(data[i]);
        }
        //        
        int k = 0;
        for (int i = 0; i < buckets.size(); i++) {
            ArrayList list = buckets.get(i);
            Integer[] integers = list.toArray(new Integer[10]);
            Arrays.sort(integers);
            //   data 
            for (int j = 0; j < integers.length; j++) {
                data[k ++] = integers[j];
            }
        }
    }
}

2.カウントソート
カウントソートは実はバケツソートの特殊な状況であり、ソートするデータの範囲が大きくなければ、例えばnであれば、n個のバケツを区分することができ、バケツごとに数値の同じデータを格納し、それから遍歴して取り出すことができ、このようにデータ全体が秩序化されます.
例えば、年齢によって10万人をソートする必要がありますが、年齢の範囲は大きくありません.年齢が最小で0、最大で120と仮定することができます.では、121バレルを直接区分し、配列を巡り、年齢の同じデータを同じバケツに保存し、取り出してソートを完了します.簡単ではないでしょうか.
ここではコードを説明しません.上のバケツのソートとよく似ています.バケツ内のソートがなくなった部分は、自分で書いてみてください.
3.基数ソート
基数ソートを見てみましょう.もし私たちが10万個の携帯電話番号をソートするなら、どうすればいいですか.携帯電話の番号は11桁で、長すぎて、バケツで並べ替えたり、カウントしたりするのに適していません.安定したソートにより,番号の最後のビットから11回比較することができる.安定したソートを使用するため、前のソート順が乱されることはありません.このプロセスをシミュレートするために簡単な文字配列を使用しました.