基本的なアイデア
RadixSortはバケットソートに基づいて開発されており、どちらもソートの割り当ての高度な実装です。 Distributivesortの基本的なアイデア：ソートプロセスでは、キーワードを比較する必要はありませんが、「配布」と「収集」プロセスを使用してソートを実装します。それらの時間の複雑さは、線形順序に達する可能性があります：o（n）。
Cardinality Sortingは安定したソーティングアルゴリズムですが、特定の制限があります。
1.キーワードは分解できます。
2。記録されたキーワードの数は小さく、密度が高い場合は優れています。 3.数字の場合は、署名しないことが最善です。そうしないと、対応するマッピングの複雑さが増加します。最初に個別に並べ替えることができます。
バケットソート（RadixSort）を見てみましょう。
バケットソートは、Box Sorting（Binsort）とも呼ばれます。その基本的なアイデアは、いくつかのバケツをセットアップし、R [0]、R [1]、r [n-1]をソートするレコードをスキャンし、特定の範囲のすべてのレコードをKTHバケット（割り当て）にロードし、シーケンス番号に従って各非空白バケツのヘッドとテールをシーケンス（収集）に接続することです。
たとえば、ポイントa <2 <<j <q <k、13 "バケツ"でシャッフルされた52のトランプを並べ替えるには、設定する必要があります。ソートすると、各カードが対応するバケツにポイントごとに配置され、バケットが順番に接続され、ポイントの段階的な順序で配置されたカードのデッキを取得します。
バケットソートでは、バケットの数はキーワードの値範囲に依存します。したがって、バケットソートには、キーワードタイプが有限であることが必要であり、それ以外の場合は無制限のバケットが必要になる場合があります。
一般的に言えば、同じキーワードを持つレコードの数が各バケットに保存されていることは予測不可能であるため、バケツのタイプはリンクリストとして設計する必要があります。
ソートが安定していることを確認するには、梱包および収集プロセス中の接続は、ファーストインファーストの原則に従って実行する必要があります。
バケットソートの場合、割り当てプロセスの時間はo（n）です。収集プロセスの時間はO（M）（リンクリストが使用され、入力を並べ替えて並べ替えられたレコードに保存）またはO（M+N）です。したがって、バケットソートの時間はO（M+N）です。バケツmの数の大きさの順序がo（n）の場合、バケットソートの時間は線形です。つまり、o（n）です。
ほとんどの場合、上記の主要なソートアルゴリズムの複雑さはo（n2）であり、いくつかのソートアルゴリズムはo（nlogn）です。しかし、バレルソートは、O（n）の時間の複雑さを達成できます。ただし、バケットソートの欠点は次のとおりです。まず、スペースの複雑さが比較的高く、追加のオーバーヘッドが必要です。ソートには、2つのスペースオーバーヘッドがあり、1つはソートする配列を保管し、もう1つはいわゆるバケットです。たとえば、ソートされる値は0からm-1で、その後Mバケットが必要であり、このバケットアレイには少なくともMスペースが必要です。第二に、ソートされる要素は特定の範囲内でなければなりません。
Cardinality Sortingは、バケットソートの改善であり、パフォーマンスを改善するのではなく、より大きな要素値に「バケットソート」を適しています。
トランプの例を使用して説明しましょう。カードは、2つのキーワードで構成されています。スーツ（ピーチ<ハート<メイ<スクエア） +額面（a <2 <3 <4 <... <k）。カードのサイズが最初にスーツによって決定され、同じスーツのカードが数によって決定される場合。この問題を解決するための2つのアルゴリズムがあります。
つまり、スーツが異なる場合、額面が何であれ、スーツの色が低いカードは、スーツの色が高いスーツの色よりも小さくなります。同じスーツの色でのみ、サイズの関係は額面のサイズによって決まります。これは、複数のキーコードの順序です。
ソート結果を取得するために、2つの並べ替え方法について説明します。
方法1：最初にスーツと色を並べ替えて、それらを4つのグループ、つまりプラムブロッサムグループ、スクエアグループ、レッドハートグループ、ブラックハートグループに分けます。次に、各グループを額面で並べ替え、最後に4つのグループを一緒に接続します。
方法2：最初に、13の顔面図に従って13の数値グループ（No. 2、3、...、a）を指定し、対応する数値グループに順に順番に順番にカードを入れ、それらを13杭に分割します。次に、4つの番号付けグループ（梅の花、正方形、赤いハート、ブラックハート）を与え、グループ2のカードを取り出して、対応する色のグループに入れてから、グループ3のカードを取り出して、対応する色のグループに入れて、このようにして、4色すべてのグループを顔面図に応じて注文します。
マルチキーコードソートは、メインキーコードから2番目のキーコード、または2番目のキーからメインキーコードまで順番にソートされ、2つの方法に分割されます。
MSDメソッドと呼ばれる最も重要なビット優先度（MostSignificAntDigitFirst）メソッド：
1）最初にK1で並べ替えてグループ化し、シーケンスをいくつかのサブシーケンスに分割します。同じシーケンスのグループの記録では、キーコードK1は等しい。
2）次に、各グループをK2でサブグループに並べ替えます。その後、各サブグループが最もセカンダリキーコードKDによってソートされるまで、次のキーコードをこのように並べ替え続けます。
3）次に、グループを接続して、順序付けられたシーケンスを取得します。スーツと顔面でカードを並べ替えて導入された方法は、MSDメソッドです。
LSDメソッドと呼ばれる最も重要でないDigitFirstメソッド：
1）KDからソートを開始し、KD-1をソートし、K1に従って最小サブシーケンスに分割されるまで順番に繰り返します。
2）最後に、各サブシーケンスを接続して、順序付けられたシーケンスを取得します。スーツと額面でカードをソートすることで導入された2番目の方法は、LSDメソッドです。
数値または文字タイプの単一のキーワードは、複数の数字または複数の文字で構成されるマルチキーワードと見なすことができます。この時点で、「割り当てコレクト」メソッドを使用してソートすることができます。このプロセスは、各数値または文字の可能な値の数がカーディナリティと呼ばれるカーディナリティソートメソッドと呼ばれます。たとえば、トランプのスーツのベースは4で、額面のベースは13です。トランプを整理する場合、最初にスタイルまたは額面で整理することができます。色に応じて並べ替えるときは、最初に赤、黒、正方形、花の順に4つのスタック（分布）に分割し、次にこの順序でそれらを積み重ね（収集）、次に額面の順序で13スタック（分布）に分割し、次にこの順序で一緒に積み重ねます（収集）。このようにして、二次的な割り当てとコレクションは、整然とした方法でトランプを配置できます。
「割り当てコレクト」プロセスでは、ソートの安定性を確保する必要があります。
Cardinality Sortingのアイデアは、データ内のキーワードの各グループを順番にソートすることです。たとえば、ソートされる次のシーケンス：
135、242、192、93、345、11、24、19
たとえば、各値のシングル、10桁、および数百桁を3つのキーワードに分割します。
135-> k1（一桁）= 5、k2（10桁）= 3、k3（100桁）= 1。
次に、最低のシングルビット（最後のキーワードから開始）から開始し、すべてのデータのすべてのK1キーワードがバケツに割り当てられます（各数値は0-9であるため、バケットサイズは10です）、次のシーケンスを取得するためにバケツのデータをシーケンスで出力します。
（11）、（242、192）、（93）、（24）、（135、345）、（19）（最もキーワードから始まり、100桁を無視し、1桁の数字に従って割り当てる）
次に、上記のシーケンスがK2に割り当てられ、出力シーケンスは次のとおりです。
（11、19）、（24）、（135）、（242、345）、（192、93）（2番目のキーワードをソートするための最もキーワードを参照し、100桁を無視し、10桁の数に従って割り当てます）
最後に、K3のバケット割り当ての場合、出力シーケンスは次のとおりです。
（011、019、024、093）、（135、192）、（242）、（345）（2番目のキーワードを参照して最高のキーワードをソートし、10桁と単一の数字を無視し、100桁の数字に従って割り当てます）
ソートは完了しました。
Javaの実装
public void radixSort（）{int max = array [0]; for（int i = 0; i <array.length; i ++）{//配列の最大値を見つけます（array [i]> max）{max = array [i]; }} int keysnum = 0; //キーワードの数には、1桁、10桁、および数百を使用しています...キーワードの数は最大桁です。 keysnum ++; } list <arraylist <integer >> backets = new arrayList <arrayList <integer >>（）; for（int i = 0; i <10; i ++）{//各桁の可能な数値は0〜9です。したがって、10バケツバケツを設定します。 //バケットは、（int i = 0; i <keysnum; i ++）{//最新のキーワードで起動するarraylist <integer>}で構成されています（int j = 0; j <array.length; j ++）{//すべてのアレイを連れて行く要素を連れて行く要素に、for（j <array.length; j ++）{// 258など。これで、10桁の数を取り出す必要があります。258％100 = 58,58/10 = 5 int key = array [j]％（int）math.pow（10、i+1）/（int）math.pow（10、i）; buckets.get（key）.add（array [j]）; //キーワードキーを使用してこの要素をバケツに入れます} //バケット内の要素を配列int counter = 0にコピーします。 //（int j = 0; j <10; j ++）{arraylist <integer> bucket = bucket.get（j）; //キーワードjを備えたバケツwhile（backet.size（）> 0）{array [counter ++] = bucket.remove（0）; //バケット内の最初の要素を配列にコピーして削除}} system.out.print（ "thread"+（i+1）+"wheel sort："）;画面（）; }}印刷の結果は次のとおりです。
アルゴリズム分析
一見すると、カーディナリティの実行効率は良好であるように思われ、あなたがしなければならないことは、オリジナルのデータ項目を配列からリンクリストにコピーしてからコピーすることだけです。 10個のデータ項目がある場合、各ビットのプロセスを繰り返す20個の複製があります。 5桁の数字がソートされていると仮定すると、20*5 = 100コピーが必要です。 100個のデータ項目がある場合、200*5 = 1000コピーがあります。コピーの数は、データ項目の数、つまりO（n）に比例します。これは、私たちが見た中で最も効率的なソートアルゴリズムです。
残念ながら、データ項目が多いほど、キーワードが長くなります。データ項目が10回増加した場合、キーワードは1つ（もう1つの並べ替えのラウンド）で追加する必要があります。コピーの数とデータ項目の数はキーワードの長さに比例します。キーワードの長さはNの対数であると考えることができます。したがって、ほとんどの場合、枢機sortingの実行効率はo（n*logn）に逆になります。
要約します
上記は、Cardinality SortingとJava Languageの実装の紹介に関するこの記事の全体的な内容です。私はそれが誰にでも役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。