|
|
Быстрая сортировка (C.A.R.Hoare)
Шаг 1. Упорядочиваемое множество разбивается на несколько непересекающихся подмножеств по следующему правилу:
определяется центральный элемент, разбивающий исходное множество на два множества, первое из которых содержит элементы, предшествующие центральному элементу, а второе – остальные.
Шаг 2. Для каждого из множеств разбиение повторяется до тех пор, пока все полученные множества не будут содержать не более одного элемента и алгоритм завершает работу.
Примечание:
Выбор функции определения центрального элемента можно решать различными способами. Главное при выборе центрального элемента – это по возможности добиться разбиения множества на почти равные два подмножества. Центральный элемент сразу занимает свое место в упорядоченном множестве.
Характеристики алгоритма:
Рекурсивный алгоритм.
Устойчивая сортировка.
Сложность от  до 
Пути улучшения алгоритма:
На первом шаге при распределении элементов по множествам, содержащих небольшое количество элементов, использовать сортировку двоичными вставками.
|
|
