Java プログラミング スキル - データ構造とアルゴリズム「基数ソート」

[[394975]]

基数ソート

1. 基数ソートは「分散ソート」に属し、「バケット ソート」または「ビン ソート」とも呼ばれます。想像どおり、ソートする要素をキー値の各ビットの値に応じて特定のバケットに分散してソート効果を実現します。
2. 基数ソートは安定性ソートに属し、基数ソートは効率的な安定性ソート方法です。
3. 基数ソートはバケットソートの拡張です。
4. 基数ソートは 1887 年にヘルマン・ホレリスによって発明されました。実装方法は、整数を桁数に応じて異なる数値に分割し、各桁を個別に比較します。

ソートの基本的な考え方

比較するすべての値は同じ桁の長さになるようにし、短い数値には先頭にゼロを埋め込みます。次に、最下位ビットから始めて、1 つずつ並べ替えます。このように、最下位ビットから最上位ビットまでソートすると、シーケンスは順序付けられたシーケンスになります。

コード例

パッケージ com.xie.sort; 
 
パブリッククラスRadixSort {
公共 静的void main(String[] args) {
 int [] arr = 新しいint [8000000];
 ( int i = 0; i < 8000000; i++) {
            arr[i] = ( int )(Math.random()*800000000);
        }
        長い開始 = System.currentTimeMillis();
        基数ソート(arr);
        長い終了= System.currentTimeMillis();
        System.out.println ( "所要時間:" +( end -start)+ "ms" );
        /*
        800万データ、時間消費: 939ミリ秒
         */
    } 
 
    // 基数ソート
公共 静的void radixSort( int [] arr) { 
 
整数 最大値= arr[0];
 ( int i = 1; i < arr.length; i++) {
            もし（arr[i] >最大値）{
最大値= arr[i];
            }
        }
        //配列内の最長桁数
int最大長さ = (最大+ "" ).length(); 
 
        //ラウンド1（各要素の単位をソート）
        // 10 個のバケットを表す 2 次元配列を定義します。各バケットは 1 次元配列です。
        //1. 2次元配列には10個の1次元配列が含まれる
        //2. 数値を入れるときにデータがオーバーフローするのを防ぐために、各1次元配列（バケット）のサイズはarr.lengthに設定されます。
        //3. 基数ソートは、空間を時間の代わりに使う古典的なアルゴリズムである
int [][] バケット = 新しいint [10][arr.length]; 
 
        //各バケットに実際に保存されているデータの量を記録するため、各バケットに毎回入れられるデータの数を記録する 1 次元配列を定義します。
        //bucketElementCounts[0]はbucket[0]に格納されたデータの数を記録します。
 int [] バケット要素カウント = 新しいint [10]; 
 
        // バケットの順序に従って（1次元配列の添え字を順に取り出して元の配列に入れる）
整数 インデックス= 0;
 ( int i = 0, n = 10; i < maxLength; i++, n *= 10) {
 ( int j = 0; j < arr.length; j++)の場合{
                //桁数を取得する
int digitOfElement = arr[j] / n % 10;
                //対応するバケットを
                バケット[要素の桁数][バケット要素数[要素の桁数]] = arr[j];
                バケット要素数[要素の桁数]++;
            } 
 
インデックス= 0;
            //各バケットを走査し、バケット内のデータを元の配列に格納します
( int k = 0; k < bucketElementCounts.length; k++) {
                //バケットにデータがある場合は、元の配列に格納します
                バケット要素数[k]が0の場合
                    //k 番目のバケット (つまり、k 番目の 1 次元配列) をループ バケットに格納します。
 ( int l = 0; l < バケット要素カウント[k]; l++) {
                        // 要素を取り出して arr に格納します
                        arr[インデックス] = バケット[k][l];
インデックス++;
                    }
                }
                バケット要素数[k] = 0;
            }
        }
    }
 }

基数ソートの手順

1. 基数ソートではスペースと時間をトレードオフするため、大量のデータをソートするときに OutOfMemoryError が発生しやすくなります。
2. 基数ソートは安定しています。 [注: ソートするレコード シーケンスに同じキーワードを持つレコードが複数あると仮定します。ソート後もこれらのレコードの相対順序が変わらない場合、つまり元のシーケンスで r[i]=r[j] であり、r[i] が r[j] の前にあり、ソートされたシーケンスでも r[i] が依然として r[j] の前にある場合、このアルゴリズムは安定していると呼ばれ、そうでない場合は不安定です。]
3. 負の数を含む配列の基数ソートについては、https://code.i-harness.com/zh-CN/q/e98fa9 を参照してください。