基数ソートは非比較ソートアルゴリズムであり、各ビットを最下位ビットから順にソートします。複雑さは配列の長さであるO（kn）であり、kは配列の最大桁数です。
基数の並べ替えでは、最初に下位順に並べ替えてから収集し、次に上位に応じて並べ替えてから収集し、以下同様に上位に並べ替えます。 一部の属性には優先順位があり、最初に低優先度で並べ替えられ、次に高優先度で並べ替えられます。 最後の順序は、高い優先度が最初であり、同じ高い優先度を持つ低い優先度が最初です。 基数ソートは、個別のソートと個別の収集に基づいているため、安定しています。
10.1 アルゴリズムの説明
- 配列の最大数を取得し、桁数を取得します。
- arrは元の配列であり、各ビットは最下位ビットから取得されて基数配列を形成します。
- 基数のカウントとソート（小さな範囲の数値のカウントとソートの特性を使用）。
10.2 可視化デモ
10.3 実装
/**
* Radix Sort
* @param array
* @return
*/
public static int[] RadixSort(int[] array) {
if (array == null || array.length < 2)
return array;
// 1.配列の最大数を取得し、桁数を取得します。
int max = array[0];
for (int i = 1; i < array.length; i++) {
max = Math.max(max, array[i]);
}
int maxDigit = 0;
while (max != 0) {
max /= 10;
maxDigit++;
}
int mod = 10, div = 1;
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < 10; i++)
bucketList.add(new ArrayList<Integer>());
for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
for (int j = 0; j < array.length; j++) {
int num = (array[j] % mod) / div;
bucketList.get(num).add(array[j]);
}
int index = 0;
for (int j = 0; j < bucketList.size(); j++) {
for (int k = 0; k < bucketList.get(j).size(); k++)
array[index++] = bucketList.get(j).get(k);
bucketList.get(j).clear();
}
}
return array;
}
10.4 性能評価
- 最良時間計算量：T(n) = O(n * k)
- 最悪時間計算量：T(n) = O(n * k)
- 平均時間計算量：T(n) = O(n * k)
基数で並べ替えるには2つの方法があります：
- MSD 上位から並べ替え
- LSD 下位から並べ替え
基数ソート vs カウントソート vs バケットソート
これらの3つの並べ替えアルゴリズムはすべてバケットの概念を使用していますが、バケットの使用には明らかな違いがあります。
- 基数ソート：キー値の各桁に従ってバケットを割り当てます
- カウントソート：各バケットは単一のキー値のみを格納します
- バケットソート：各バケットは特定の範囲の値を格納します