Java ソートアルゴリズムの概要 (VIII): 基数ソート

基数ソートは「分散ソート」に属します。基数ソートは「バケットソート」またはビンソートとも呼ばれます。名前が示すように、キー値の部分的な情報を使用して、ソートする要素を特定の「バケット」に分散し、ソート効果を実現します。基数ソートは、時間計算量が O (nlog(r)m) の安定したソートです。ここで、r は基数、m はヒープの数です。場合によっては、基数ソートは他の比較ソート方法よりも効率的です。

効率分析:

時間効率: ソートするシーケンスが n レコード、d キーコード、キーコードの値の範囲が radix であると仮定します。チェーン radix ソートの時間計算量は O(d(n+radix)) です。1 回の割り当ての時間計算量は O(n)、1 回のコレクションの時間計算量は O(n) で、合計 d 回の割り当てとコレクションが実行されます。スペース効率: キューを指すには 2*radix の補助スペースが必要であり、静的リンクリストには n 個のポインタが必要です。

実施方法：

最上位桁優先方式 (MSD 方式とも呼ばれる) では、まず k1 でソートしてグループ化します。同じグループ内のレコードでは、キーコード k1 は同じです。次に、各グループを k2 でソートし、サブグループに分割します。その後、各サブグループが最下位キーコード kd でソートされるまで、次のキーコードがこのようにソートおよびグループ化されます。次に、グループを接続して順序付けられたシーケンスを取得します。 LSD 方式と呼ばれる最下位桁優先方式では、kd のソートから開始し、次に kd-1 をソートし、k1 がソートされるまでこれを繰り返して順序付けられたシーケンスを取得します。

コード実装:

公共 クラスRadixSort {
公共 静的  voidソート( int [] 数値, int d) {
整数k = 0 ;
整数n = 1 ;
整数m = 1 ;
 int [][] temp =新しい  int [数値.長さ][数値.長さ];
 int [] 順序 =新規  int [数値.長さ];
 (m <= d)の間{
 ( int i = 0 ; i < 数値.長さ; i++) {
 int lsd = ((数値[i] / n) % 10 );
 temp[lsd][order[lsd]] = 数値[i];
注文[lsd]++;
 }
 ( int i = 0 ; i < d; i++)の場合{
 （順序[i] != 0 ）の場合
( int j = 0 ; j < order[i]; j++) {
数値[k] = temp[i][j];
関数
}
順序[i] = 0 ;
 }
 10 ;
 0の場合
m++;
 }
 }
公共 静的  void main(String[] args) {
 int [] データ =
 { 73 、 22 、 93 、 43 、 55 、 14 、 28 、 65 、 39 、 81 、 33 、 100 };
 RadixSort.sort(データ、 10 );
 ( int i = 0 ; i < データ長; i++) {
 System.out.print(data[i] + " " );
 }
 }

基数ソートは通常、レコードのキーが整数型の場合にのみ使用されます。

紹介したさまざまな内部ソート方法の中で、クイックソート、マージソート、ヒープソートは、必要な計算時間の点で優れた方法です。ただし、マージソートにはサイズ n の補助スペースが必要であり、クイックソートにはスタックが必要です。不安定なクイックソート、ヒープソート、選択ソート、シェルソートを除き、他のソート方法は安定しています。

ソートアルゴリズムのパフォーマンスを評価する主な基準は、必要な計算時間とストレージスペースです。計算時間に影響を与える 2 つの重要な要素は、キーが比較される回数と記録される移動回数です。実際のアプリケーションでは、どの選別方法を使用するかは、特定のアプリケーションと機械の状態によって異なります。

【編集者のおすすめ】