Вот алгоритм сортировки, который можно использовать для массива целых чисел или структур, ключом которых является целое число. Особенно полезно, когда диапазон целых чисел соответствует размеру входных данных.

Основная идея состоит в том, чтобы определить частоту появления целых чисел и использовать ее для определения порядка сортировки.

Пример: скажем, мы получили массив {1,3,1,2}.

Сначала определите диапазон целых чисел, максимальное и минимальное, 1 и 3 для этого ввода.

Далее создайте массив, назовите его массивом counts, то есть размер целочисленного диапазона равен 1, то есть в данном случае 3 (3-1 1).
Выполните итерацию по входному массиву, увеличивая соответствующую запись в счетчиках. Количество заданного входного значения будет помещено в counts[value - min]. Для данного ввода counts[0] будет содержать счетчик для значения 1.

В результате получается массив counts: {2,1,1}

Теперь определите совокупное количество, которое по сути равно counts[i] = counts[i-1] counts[i].

В результате получается массив совокупных значений: {2,3,4}

Создайте выходной массив для отсортированных входных данных.

Теперь повторите входные данные в обратном порядке.

На каждом шаге извлекайте совокупное количество значений во входном массиве. Значение будет помещено в индекс выходного массива, соответствующий полученному счетчику - 1. Затем уменьшите совокупное значение счетчика.

На первом этапе извлекается значение 2 и совокупный счетчик 3. Значение должно быть помещено в выходные данные под индексом 2 (3-1).

На следующей итерации значение 1 и совокупный счетчик 2; поэтому эта '1' помещается в индекс 1 (2-1) вывода.

Продолжение: значение 3 и совокупный счетчик 4; поместив его в индекс 3 вывода.

Наконец, значение 1 во второй раз и совокупный счетчик 1 (поскольку счетчик был уменьшен при первом просмотре); поэтому эта '1' помещается в индекс 0 вывода.

, Посмотрите, как обратная итерация сохраняет порядок равных элементов, делая сортировку «стабильной»

Результирующий отсортированный массив: {1,1,2,3}

func CountingSort(in []int) []int {
    // find the min/max values
    min := slices.Min(in)
    max := slices.Max(in)
    // create the count array
    counts := make([]int, max-min 1)
    for _, v := range in {
        counts[v-min]  
    }
    // determine cumulative counts
    for i := 1; i 



Можно ли сделать его более эффективным? Оставляйте свои комментарии и предложения ниже.

Спасибо!

Код этого поста и всех постов из этой серии можно найти здесь