Алгоритм 7. Сортировка подсчетом.

   Этот метод подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Идея вот в чем: для каждого элемента найти, сколько элементов, меньших определенного числа, и поместить это число на соответствующие место. Делается это так: за линейный проход по массиву мы для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный. При этом следим, чтобы два одинаковых элемента не были записаны в одно место. Если все равно непонятно, смотрите реализацию: Program CountingSort; Var A,B : array[1..1000] of byte; C : array[byte] of integer; N,i : integer; Begin {Определение размера массива A (N) и его заполнение} … {сортировка данных} for i:=0 to 255 do C[i]:=0; for i:=1 to N do C[A[i]]:=C[A[i]]+1; for i:=1 to 255 do C[i]:=C[i-1]+C[i]; for i:=N downto 1 do begin B[C[A[i]]]:=A[i]; C[A[i]]:=C[A[i]]-1; {здесь мы избегаем возможности записи двух одинаковых чисел в одну ячейку} end; {Вывод массива B} … End.    Этот простой метод не использует вложенных циклов и, учитывая небольшой диапазон значений, время его работы есть O(n).    Рассмотрев такое количество сортировок, можно задуматься: а будет ли результат их работы одинаковым? Странный вопрос, ведь все сортировки правильно сортируют данные, так почему же результат работы может быть разным? Хорошо, объясню: меньшие элементы всегда расположены перед большими, но порядок одинаковых элементов может быть нарушен. Если мы сортируем данные, которые состоят из одного ключа, то мы, конечно, не заметим разницы. Но если к ключу прилагается дополнительная информация, то одна сортировка может вернуть нам 1977 "Иванов" и 1977 "Сидоров", а другая — 1977 "Сидоров" и 1977 "Иванов". Значит, порядок одинаковых элементов может в процессе сортировки стать другим. Правда, это бывает далеко не всегда и не в каждой сортировке. В сортировках вставками, пузырьком, подсчетом и слиянием порядок элементов с одинаковыми ключами всегда такой же, как и в изначальном массиве. Такие сортировки называются устойчивыми, и сейчас я познакомлю вас с улучшенной сортировкой подсчетом, которая позволяет сортировать числа большего диапазона, используя другую устойчивую сортировку.

Алгоритм 8. Цифровая сортировка.

   Этой сортировкой можно сортировать целые неотрицательные числа большого диапазона. Идея состоит в следующем: отсортировать числа по младшему разряду, потом устойчивой сортировкой сортируем по второму, третьему, и так до старшего разряда. В качестве устойчивой сортировки можно выбрать сортировку подсчетом, в виду малого времени работы. Реализация такова: Program RadixSort; Var A,B : array[1..1000] of word; N,i : integer; t : longint; Procedure Sort; {сортировка подсчетом} Var C : array[0..9] of integer; j : integer; Begin For j:=0 to 9 do C[j]:=0; For j:=1 to N do C[(A[j] mod (t*10)) div t]:= C[(A[j] mod (t*10)) div t]+1; For j:=1 to 9 do C[j]:=C[j-1]+C[j]; For j:=N downto 1 do begin B[C[(A[j] mod (t*10)) div t]]:=A[j]; C[(A[j] mod (t*10)) div t] := C[(A[j] mod (t*10)) div t]-1; end; End; Begin {Определение размера массива A (N) и его заполнение} … {сортировка данных} t:=1; for i:=1 to 5 do begin Sort; A:=B; t:= t*10; end; {Вывод массива A} … End.    Так как сортировка подсчетом вызывается константное число раз, то время работы всей сортировки есть O(n). Заметим, что таким способом можно сортировать не только числа, но и строки, если же использовать сортировку слиянием в качестве устойчивой, то можно сортировать объекты по нескольким полям.