サーチ…


バケットソート基本情報

バケットソートは、入力配列の要素がバケットに分散されたソートアルゴリズムです。すべての要素を配布した後、バケットは別のソートアルゴリズムで個別にソートされます。ときには再帰的な方法でソートされることもあります。

バケットソートの疑似コード

  1. nを入力リストLの長さとする。
  2. Lからの各要素i
  3. B [i]が空でない場合
  4. A [i]をB [i]に入れる。
  5. Else B [i]:= A [i]
  6. Concat B [i .. n]を1つのソートされたリストに戻す。

バケットソートの例: バケットソートの例

ほとんどの人は、少しの最適化のために挿入パラダイムを使用します。
補助空間: O{n}

C#の実装

public class BucketSort
{
    public static void SortBucket(ref int[] input)
    {
        int minValue = input[0];
        int maxValue = input[0];
        int k = 0;

        for (int i = input.Length - 1; i >= 1; i--)
        {
            if (input[i] > maxValue) maxValue = input[i];
            if (input[i] < minValue) minValue = input[i];
        }

        List<int>[] bucket = new List<int>[maxValue - minValue + 1];

        for (int i = bucket.Length - 1; i >= 0; i--)
        {
            bucket[i] = new List<int>();
        }

        foreach (int i in input)
        {
            bucket[i - minValue].Add(i);
        }

        foreach (List<int> b in bucket)
        {
            if (b.Count > 0)
            {
                foreach (int t in b)
                {
                    input[k] = t;
                    k++;
                }
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortBucket(ref input);
        return input;
    }
}


Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow