algorithm
Сортировка Pigeonhole
Поиск…
Pigeonhole Сортировать базовую информацию
Pigeonhole Sort - это алгоритм сортировки, который подходит для сортировки списков элементов, где число элементов (n) и количество возможных значений ключа (N) примерно одинаковы. Для этого требуется время O (n + Range), где n - количество элементов в входном массиве, а «Range» - количество возможных значений в массиве.
Рабочий (псевдо-код) для Pigeonhole Сортировать:
- Найти минимальное и максимальное значения в массиве. Пусть минимальное и максимальное значения равны «min» и «max» соответственно. Также найдите диапазон как «max-min-1».
- Настройте массив изначально пустых «голубинок» того же размера, что и диапазон.
- Посетите каждый элемент массива, а затем поместите каждый элемент в его яму. Элементный вход [i] помещается в отверстие на входе индекса [i] - мин.
- Начните цикл по всей решетке пигмента и поместите элементы из непустых отверстий обратно в исходный массив.
Тип Pigeonhole аналогичен сортировке сортировки, поэтому здесь приведено сравнение Сортировки Pigeonhole Sort и counting sort.
Пример Pigeonhole Сортировать:
Вспомогательный объем: O(n)
Сложность времени: O(n + N)
Реализация C #
public class PigeonholeSort
{
private static void SortPigeonhole(int[] input, int n)
{
int min = input[0], max = input[n];
for (int i = 1; i < n; i++)
{
if (input[i] < min) min = input[i];
if (input[i] > max) max = input[i];
}
int range = max - min + 1;
int[] holes = new int[range];
for (int i = 0; i < n; i++)
{
holes[input[i] - min] = input[i];
}
int index = 0;
for (int i = 0; i < range; i++)
{
foreach (var value in holes)
{
input[index++] = value;
}
}
}
public static int[] Main(int[] input)
{
SortPigeonhole(input, input.Length);
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
Лицензировано согласно CC BY-SA 3.0
Не связан с Stack Overflow