Программирование на языке Pascal
Быстрая сортировка
Существует еще один метод улучшенной сортировки, имеющий среднюю сложность порядка N*log N: так называемая Быстрая сортировка12). Этот алгоритм является усовершенствованием обменных сортировок. Его реализация наиболее удобна в рекурсивном варианте, поэтому мы вернемся к ее изучению после того, как познакомимся с рекурсивными процедурами и функциями (см. лекцию 9).
 |
|
|
1)
Более подробную информацию о различных алгоритмах упорядочения смотрите в книге Дональда Кнута " Искусство программирования ЭВМ", том 3: "Сортировка и поиск".
2)
В названиях алгоритмов мы будем следовать Кнуту.
3)
Одно - при сдвиге и еще одно - при проверке необходимости сдвига
4)
Одно - при сдвиге и еще две - при переписывании вставляемого элемента.
5)
Напомним, что log N означает log2 N
6)
Если бы в строке {***} программы ПРВыб стоял знак строгого неравенства, то в качестве минимума была бы выбрана первая тройка. Однако очевидно, что выгоднее брать последний из совпадающих элементов: благодаря этому все они оказываются левее, чем тот превосходящий всех их элемент, с которым выбранный минимум меняется местами.
7)
Д. Кнут. Искусство программирования для ЭВМ. Т.3. Сортировка и поиск (любое издание).
8)
Н. Вирт. Алгоритмы и структуры данных (любое издание).
9)
Д. Л. Шелл назвал ее "сортировкой вставками с убывающим шагом".
10)
Для других входных данных это число может быть значительно меньше или же еще больше.
11)
Грохот - техническое "сито".
12)
В оригинале QuickSort.
| © 2003-2007 INTUIT.ru. Все права защищены. |
