Быстрая сортировка(QuickSort) - это рекурсивный алгоритм, который использует
подход "Разделяй и властвуй". Список, который нужно отсортировать
делится пополам, и для каждой из частей, процедура вызывает себя рекурсивно. Итак, рассмотрим. следующую схему сравнений/обменов. Имеются два
указателя i и j, причем вначале i = l, a j = N. Сравним Ki :
Kj, и если обмен не требуется, то уменьшим j на единицу и повторим
этот процесс. После первого обмена увеличим i на единицу и будем продолжать
сравнения, увеличивая i, пока не произойдет еще один обмен. Тогда опять
уменьшим j и т. д.; будем "сжигать свечку с обоих концов", пока
не станет i = j. Посмотрим, например, что произойдет с нашим файлом из шестнадцати
чисел:
Дано:
503
087
512
061
908
170
897
275
653
426
154
509
612
677
765
703
-j
1-й обмен
154
087
512
061
908
170
897
275
653
426
503
509
612
677
765
703
+i
2-й обмен
154
087
503
061
908
170
897
275
653
426
512
509
612
677
765
703
-j
3-й обмен
154
087
426
061
908
170
897
275
653
503
512
509
612
677
765
703
+i
4-й обмен
154
087
426
061
503
170
897
275
653
908
512
509
612
677
765
703
-j
5-й обмен
154
087
426
061
275
170
897
503
653
908
512
509
612
677
765
703
+i
6-й обмен
154
087
426
061
275
170
503
897
653
908
512
509
612
677
765
703
-j
(Чтобы выявить состояние i и j, ключи Ki
и Kj напечатаны жирным шрифтом.) Заметим, что в каждом
сравнении этого примера участвует ключ 503; вообще в каждом сравнении
будет участвовать исходный ключ K1 потому что он будет продолжать
обмениваться местами с другими ключами каждый раз, когда мы переключаем
направление. . моменту, когда i = j, исходная запись R1 займет
свою окончательную позицию, потому что, как нетрудно видеть, слева от
нее не будет больших ключей, а справа-меньших. Исходный файл окажется
разделен таким образом, что первоначальная задача сведется к двум более
простым: сортировке файла R1 : : : Ri-1 и (независимо)
сортировке файла Ri+1 : : : RN. К каждому из этих
подфайлов можно применить тот же самый метод. (Д. Кнут)
Вот его реализация на Delphi:
Быстрая сортировка самый рапространённый алгоритм. Его вы можете
найти в таких классах Delphi как TList и TStringList. Также посмотрите
интересный пример на сортировки: Demos-->Threads-->.
У этого алгоритма много вариантов оптимизации. Попробуйте что-нибудь реализовать.