Читайте также:
|
Этот метод подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Идея вот в чем: для каждого элемента найти, сколько элементов, меньших определенного числа, и поместить это число на соответствующие место. Делается это так: за линейный проход по массиву мы для каждого из возможных значений подсчитываем, сколько элементов имеют такое значение. Потом добавляем к каждому из найденных чисел суму всех предыдущих. Получая, таким образом, сколько есть элементов, значения которых не больше данного значения. Далее, опять-таки за линейный проход, формируем из исходного массива новый отсортированный. При этом следим, чтобы два одинаковых элемента не были записаны в одно место. Если все равно непонятно, смотрите реализацию:
| 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. 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 "Иванов". Значит, порядок одинаковых элементов может в процессе сортировки стать другим. Правда, это бывает далеко не всегда и не в каждой сортировке. В сортировках вставками, пузырьком, подсчетом и слиянием порядок элементов с одинаковыми ключами всегда такой же, как и в изначальном массиве. Такие сортировки называются устойчивыми, и сейчас я познакомлю вас с улучшенной сортировкой подсчетом, которая позволяет сортировать числа большего диапазона, используя другую устойчивую сортировку.
Дата добавления: 2015-09-11; просмотров: 36 | Поможем написать вашу работу | Нарушение авторских прав |
| <== предыдущая лекция | | | следующая лекция ==> |
| Алгоритм 6. Быстрая сортировка | | | Сказки двух миров. Вступление Стефана А. Аппельбаума. |