algorithm
Sortowanie wiader
Szukaj…
Wiadro Sortuj Podstawowe informacje
Sortowanie segmentów to algorytm sortowania, w którym elementy tablicy wejściowej są rozmieszczone w segmentach. Po rozmieszczeniu wszystkich elementów wiadra są sortowane indywidualnie według innego algorytmu sortowania. Czasami jest również sortowany metodą rekurencyjną.
Pseudo-kod dla sortowania kubełkowego
- Niech n będzie długością listy wejściowej L;
- Dla każdego elementu i od L
- Jeśli B [i] nie jest puste
- Wstaw A [i] do B [i];
- W przeciwnym razie [i]: = A [i]
- zwróć Concat B [i .. n] w jedną posortowaną listę;
Przykład sortowania kubełkowego:
Przeważnie ludzie używają paradygmatu wstawiania w celu optymalizacji.
Przestrzeń pomocnicza: O{n}
Implementacja 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
Licencjonowany na podstawie CC BY-SA 3.0
Nie związany z Stack Overflow