バケットソートは、カウントソートのアップグレードバージョンです。 関数のマッピング関係を利用しており、高効率の秘訣はマッピング関数の決定にあります。 バケットソートの動作原理：入力データが均一に分散されていると仮定すると、データは限られた数のバケットに分割され、各バケットは個別にソートされます（別のソートアルゴリズムを使用することも、再帰的に使用し続けることもできます）。バケットソートが実行される方法）。
9.1 アルゴリズムの説明
- 定長の配列を空バケットとして用意する。
- 入力データをトラバースし、データを1つずつ対応するバケットに入れる。
- 空でないすべてのバケットを並べ替える。
- 空ではないバケットからソートされたデータを連結する。
バケットソートを再帰的に使用して各バケットをソートする場合は、バケット数が1のときに手動でBucketSizeを減らし、次のサイクルでバケット数を増やす必要があります。そうしないと、無限ループに陥り、メモリオーバーフローが発生します。
9.2 動作例
9.3 実装
public static ArrayList<Integer> BucketSort(ArrayList<Integer> array, int bucketSize) {
if (array == null || array.size() < 2)
return array;
int max = array.get(0), min = array.get(0);
// Find the maximum and minimum values
for (int i = 0; i < array.size(); i++) {
if (array.get(i) > max)
max = array.get(i);
if (array.get(i) < min)
min = array.get(i);
}
int bucketCount = (max - min) / bucketSize + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketCount);
ArrayList<Integer> resultArr = new ArrayList<>();
for (int i = 0; i < bucketCount; i++) {
bucketArr.add(new ArrayList<Integer>());
}
for (int i = 0; i < array.size(); i++) {
bucketArr.get((array.get(i) - min) / bucketSize).add(array.get(i));
}
for (int i = 0; i < bucketCount; i++) {
// If there are duplicate numbers in the sorted array
if (bucketSize == 1) {
for (int j = 0; j < bucketArr.get(i).size(); j++)
resultArr.add(bucketArr.get(i).get(j));
} else {
if (bucketCount == 1)
bucketSize--;
ArrayList<Integer> temp = BucketSort(bucketArr.get(i), bucketSize);
for (int j = 0; j < temp.size(); j++)
resultArr.add(temp.get(j));
}
}
return resultArr;
}
9.4 性能評価
バケットソートの最良の場合は線形時間O（n）です。バケットソートの時間計算量は、他の部分の時間計算量がO（n）であるため、各バケット間のデータのソートの時間計算量に依存します。 明らかに、分割されるバケットが小さいほど、各バケット間のデータが少なくなり、並べ替えにかかる時間が短くなります。 ただし、対応する空間（メモリ）消費量は増加します。
- 最良時間計算量：T(n) = O(n+k)
- 最悪時間計算量：T(n) = O(n+k)
- 平均時間計算量：T(n) = O(n2)