|
Быстрая сортировка Быстрая сортировка выбирает элемент списка, называемый осевым, а затем переупорядочивает список таким образом, что все элементы, меньшие осевого, оказываются перед ним, а большие элементы - за ним. В каждой из частей списка элементы не упорядочиваются. Если i - окончательное положение осевого элемента, то нам известно лишь, что все значения в позициях с первой по i - 1 меньше осевого, а значения с номерами от i + 1 до N больше осевого. Затем алгоритм QuickSort вызывается рекурсивно на каждой из двух частей. При вызове процедуры QuickSort на списке, состоящем из одного элемента, он ничего не делает, поскольку одноэлементный список уже отсортирован. Поскольку основная работа алгоритма заключается в определении осевого элемента и последующей перестановке элементов, главная процедура в алгоритме QuickSort должна лишь проследить за границами обеих частей. Поскольку перемещение ключей происходит в процессе разделения списка на две части, вся работа по сортировке выполняется при возвращении по рекурсии. Вот алгоритм быстрой сортировки: QuickSort(list, first, last) list упорядочиваемый список элементов first номер первого элемента в сортируемой части списка last номер последнего элемента в сортируемой части списка if first < lat then pivot = PivotList(list, first, last) QuickSort(list, first, pivot - 1) QuickSort(list, pivot + 1, last) end if Расщепление списка У функции PivotList есть по крайней мере два варианта. Первый из них, который легко запрограммировать и понять, описан в настоящей статье. Второй вариант записать труднее, однако он работает быстрее. Функция PivotList берет в качестве осевого элемента первый элемент списка и устанавливает указатель pivot в начало списка. Затем она проходит по списку, сравнивая осевой элемент с остальными элементами списка. Обнаружив элемент, меньший осевого, она увеличивает указатель PivotPoint, а затем переставляет элемент с новым номером PivotPoint и вновь найденный элемент. После того, как сравнение части списка с осевым элементом уже произведено, список оказывается разбит на четыре части. Первая часть состоит из первого - осевого - элемента списка. Вторая часть начинается с положения first + 1, кончается в положении PivotPoint и состоит из всех просмотренных элементов, оказавшихся меньше осевого. Третья часть начинается в положении PivotPoint + 1 и заканчивается указателем параметра цикла index. Оставшаяся часть списка состоит из еще не просмотренных значений. Соответствующее разбиение приведено на рисунке ниже.  Вот алгоритм PivotList: PivotList(list, first, last) list обрабатываемый список first номер первого элемента last номер последнего элемента PivotValue = list[first] PivotPoint = first for index = first + 1 to last do if list[index] < PivotValue then PivotPoint = PivotPoint + 1 Swap(list[PivotPoint], list[index]) end if end for // перенос осевого значения на нужное место Swap(list[first], list[PivotPoint]) return PivotPoint |
