Внедрение метода подсчета для сортировки больших наборов малых целых чисел в C#

Когда ваша задача сортировки включает в себя большие массивы небольших целых чисел, таких как классы, возрасты или категориальные коды, классические алгоритмы на основе сравнения, такие как QuickSort или MergeSort, могут ощущаться как перебор. Эти алгоритмы работают во времени O (n log n), но если диапазон возможных значений ограничен, вы можете сортировать в линейном времени O (n + k) с [[FLT: 0]] Сортировка сортировки [[FLT: 1]]. Этот алгоритм сортировки без сравнения использует тот факт, что вы можете подсчитывать события, а не сравнивать элементы, обеспечивая стабильный сорт, который является простым и невероятно быстрым для правильных входов.

Как работает счетчик

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

Основной подход: прямая реконструкция

Простейшая версия Counting Sort работает в два прохода:

Считаете частоты — итерируйте через входной массив и прирасти счетчик для каждого значения, которое вы видите.
Перезаписывайте вход — пройдите через счетчик массива от наименьшего до наибольшего и за каждое значение запишите его обратно в массив ввода столько раз, сколько его количество.

Это дает отсортированный выход, но не сохраняет относительный порядок дубликатов (он не стабилен). Стабильность имеет значение, когда вы сортируете ключ, сохраняя исходный порядок записей с равными ключами.

Стабильный вариант: кумулятивные счета

Чтобы сделать счет стабилен, мы добавляем третий проход:

Подсчитывайте частоты, как раньше.
Преобразовать частотный массив в кумулятивный счетный массив.После этого шага удерживает число элементов ≤ i.
Итерировать входной массив в обратном направлении (от последнего элемента к первому). Для каждого элемента используйте его кумулятивный счетчик, чтобы найти его положение в выходном массиве, поместить его и уменьшить счет.

Поскольку мы пересекаем в обратном направлении, относительный порядок равных элементов сохраняется. Выходной массив отделен от входа, поэтому эта версия использует дополнительное пространство O(n) для вывода, тогда как базовая версия может сортировать на месте, перезаписывая вход.

Сортировка подсчета в C#

Ниже приведены две реализации C#: базовая версия на месте (для сценариев, где стабильность не нужна) и стабильная версия, которая использует вспомогательный массив.

Базовый (нестабильный) счет

Этот вариант сортирует входной массив непосредственно без дополнительного буфера вывода. Он эффективен для памяти, но не стабилен.

public static void CountingSortBasic(int[] array, int maxValue)
{
 int[] counts = new int[maxValue + 1];

 // Count each element's frequency
 for (int i = 0; i < array.Length; i++)
 {
 counts[array[i]]++;
 }

 // Overwrite the original array in sorted order
 int index = 0;
 for (int value = 0; value <= maxValue; value++)
 {
 while (counts[value]-- > 0)
 {
 array[index++] = value;
 }
 }
}

Стабильный счетчик

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

public static int[] CountingSortStable(int[] array, int maxValue)
{
 int[] counts = new int[maxValue + 1];
 int[] output = new int[array.Length];

 // Step 1: Count occurrences
 foreach (int num in array)
 {
 counts[num]++;
 }

 // Step 2: Transform counts to cumulative counts
 for (int i = 1; i <= maxValue; i++)
 {
 counts[i] += counts[i - 1];
 }

 // Step 3: Build the output array (iterate input in reverse for stability)
 for (int i = array.Length - 1; i >= 0; i--)
 {
 int value = array[i];
 output[counts[value] - 1] = value;
 counts[value]--;
 }

 return output;
}

В обеих реализациях является наибольшим целым числом, которое появляется в массиве. Если истинный максимум неизвестен, вы можете вычислить его с помощью подготовительного сканирования (O(n)). Стабильная версия возвращает новый сортированный массив, оставляя оригинал без изменений.

Анализ сложности

Пусть n будет числом элементов и k = max — мин + 1 (диапазон возможных значений).

Время: Сортировка счёта выполняется в O(n + k) времени. Фаза счёта — O(n), кумулятивный префикс — O(k), а реконструкция — O(n). Когда k — O(n), алгоритм является линейным.
Space: Базовая версия использует дополнительное пространство O(k) для счётного массива. Стабильная версия использует O(n+k), поскольку она также выделяет выходной массив. Это делает Counting Sort непригодным, когда диапазон велик относительно количества элементов.
Сравнение с другими видами: Сортировочные, такие как QuickSort и MergeSort, требуют, по меньшей мере, сравнения O(n log n). Для малых k (например, k <10000 и n >100000) счётная сортировка может быть на порядки быстрее.

Вариации и расширения

Обработка отрицательных целых чисел

Сортное подсчётное число изначально работает с неотрицательными целыми числами. Для обработки отрицательных значений сместите весь диапазон так, чтобы минимум стал нулем. Например, если числа колеблются от -1000 до 1000, компенсируйте каждый элемент +1000. Массив счёта тогда имеет размер .

public static int[] CountingSortWithNegative(int[] array)
{
 if (array.Length == 0) return array;

 int min = array.Min();
 int max = array.Max();
 int range = max - min + 1;

 int[] counts = new int[range];
 int[] output = new int[array.Length];

 foreach (int num in array)
 counts[num - min]++;

 for (int i = 1; i < range; i++)
 counts[i] += counts[i - 1];

 for (int i = array.Length - 1; i >= 0; i--)
 {
 int value = array[i];
 output[counts[value - min] - 1] = value;
 counts[value - min]--;
 }

 return output;
}

Картирование нецелых ключей

Если ваши данные состоят из символов (байт) или перечислений, которые могут быть отлиты в целые числа, вы все равно можете применить его. Для более крупных объектов вы можете извлечь целочисленный ключ и сортировать объекты соответственно — именно так Radix Sort часто использует Counting Sort в качестве своей внутренней подпрограммы.

Radix Sort Combo

Radix Sort обрабатывает цифры (или биты) индивидуально, и Counting Sort является естественным выбором для каждого прохода, когда основание (например, 10 или 256) мало.

Практические соображения в C#

Отпечаток памяти и большой k

Самая большая ошибка заключается в выделении массива подсчетов, большего, чем доступная память. Например, сортировка 1000 элементов с диапазоном 1 000 000 пустого пространства. Всегда проверяйте, что k не на порядки больше, чем n — иначе используйте сорт сравнения или гибридный подход.

Параллелизм и Span<T>

Для чрезвычайно больших массивов можно распараллеливать фазу подсчета, разделяя вход на потоки. Каждый поток подсчитывает свой сегмент в частный массив, а затем агрегируются частичные результаты. Использование и для массива подсчета может уменьшить кучу распределений, когда диапазон мал.

Случаи с уклоном

[[ФЛТ:0]] Пустая решётка[[ФЛТ:1]] — немедленно возвращайтесь.
Один элемент — сортировка тривиальна.
Все идентичные значения — счётная матрица имеет одну ненулевую запись; реконструкция выполняется в O(n).
Большой диапазон, но скудные данные — Сортировка подсчета становится неэффективной, потому что большинство записей подсчета равны нулю.

Когда использовать счет (и когда не использовать)

Situation	Recommendation
Small integer range (k ~ n)	Excellent choice – linear time, simple code.
Large integer range (k >> n)	Avoid – memory waste and O(k) overhead.
Need stability	Use the stable variant (cumulative counts).
Strings or objects	Consider Radix Sort or a comparison sort.
Extremely large datasets	Counting Sort can be parallelized; but watch memory.

Сравнительные показатели и эффективность

В типичном бенчмарке с n = 1 000 000 и k = 1000 Counting Sort завершается примерно в 20-30% времени, затрачиваемого (который использует интрозорт.] Разрыв расширяется по мере уменьшения k. Ниже приведено приблизительное сравнение (время выполнения на современном процессоре с .NET 8):

n = 1,000,000 | k = 1,000
Array.Sort (QuickSort variant) : 68 ms
CountingSortBasic : 12 ms
CountingSortStable : 18 ms

Когда диапазон увеличивается до 10 000, Counting Sort все еще выигрывает, но маржа сужается. Для k = 100 000 накладные расходы на память (≈ 400 КБ для массива подсчета) начинают повредить кэш процессора, и производительность может ухудшиться.

Заключение

Counting Sort - обманчиво простой алгоритм, который обеспечивает линейную производительность, когда данные соответствуют его ограничениям. Для разработчиков C#, имеющих дело с большими массивами небольших целых чисел, это ценный инструмент, который может значительно сократить время сортировки. Следите за диапазоном ваших данных: если он мал и известен, Counting Sort будет опережать любую альтернативу на основе сравнения. Для более общей сортировки используйте встроенную , но всегда будьте готовы к падению Counting Sort, когда цифры выстраиваются в линию - буквально и образно.

Для дальнейшего чтения, обратитесь к статье Wikipedia о Counting Sort , Microsoft docs на Array.Sort , и практическое руководство от GeeksforGeeks .