algorithm
Подсчет сортировки
Поиск…
Подсчет сортировки
Сортировка сортировки - это целочисленный алгоритм сортировки для коллекции объектов, сортируемых в соответствии с ключами объектов.
меры
- Построить рабочий массив C , размер которого равен диапазону входного массива A.
- Перейдем через A , назначив C [x] в зависимости от количества раз x, появившегося в A.
- Преобразуйте C в массив, где C [x] ссылается на число значений ≤ x, итерируя через массив, присваивая каждому C [x] сумму своего предыдущего значения и все значения в C, которые выходят перед ним.
- Перемещайтесь назад через A , помещая каждое значение в новый отсортированный массив B по индексу, записанному на C. Это делается для заданного A [x], назначая B [ C [ A [x]]] A [x] и уменьшая C [ A [x]] в случае, если в исходном несортированном массиве были повторяющиеся значения.
Пример подсчета сортировки
Вспомогательное пространство: O(n+k)
Сложность времени: худший случай: O(n+k)
, наилучший случай: O(n)
, средний случай O(n+k)
Внедрение Psuedocode
Ограничения:
- Вход (массив, который нужно отсортировать)
- Количество элементов ввода (n)
- Клавиши в диапазоне 0..k-1 (k)
- Count (массив чисел)
псевдокод:
for x in input:
count[key(x)] += 1
total = 0
for i in range(k):
oldCount = count[i]
count[i] = total
total += oldCount
for x in input:
output[count[key(x)]] = x
count[key(x)] += 1
return output
Реализация C #
public class CountingSort
{
public static void SortCounting(int[] input, int min, int max)
{
var count = new int[max - min + 1];
var z = 0;
for (var i = 0; i < count.Length; i++)
count[i] = 0;
foreach (int i in input)
count[i - min]++;
for (var i = min; i <= max; i++)
{
while (count[i - min]-- > 0)
{
input[z] = i;
++z;
}
}
}
public static int[] Main(int[] input)
{
SortCounting(input, input.Min(), input.Max());
return input;
}
}
Modified text is an extract of the original Stack Overflow Documentation
Лицензировано согласно CC BY-SA 3.0
Не связан с Stack Overflow