algorithm
Seau Sort

Seau Trier les informations de base

Bucket Sort est un algorithme de tri dans lequel les éléments du tableau d'entrée sont répartis dans des compartiments. Après avoir distribué tous les éléments, les compartiments sont triés individuellement par un autre algorithme de tri. Parfois, il est également trié par méthode récursive.

Pseudo-code pour le tri par godet

1. Soit n la longueur de la liste d'entrée L;
2. Pour chaque élément i de L
3. Si B [i] n'est pas vide
4. Mettez A [i] dans B [i];
5. Sinon B [i]: = A [i]
6. retourner Concat B [i .. n] dans une liste triée;

Exemple de type de seau:

La plupart du temps, les gens utilisent le paradigme d'insertion pour peu d'optimisation.
Espace auxiliaire: O{n}

Implémentation 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;
    }
}