Учебное пособие C#. Алгоритмы и структуры данных н. А. Тюкачев, В. Г. Хлебостроев издание третье, стереотипное 1 / 23
Download 1.85 Mb. Pdf ko'rish
|
C# Алгоритмы и структуры данных 2018 Тюкачев, Хлебостроев
|
3.3.2. Б
ЫСТРАЯ СОРТИРОВКА Быстрая сортировка основана на сортировке обменом, которая среди всех сортировок является наименее эффективной: классический пример – сортировка методом пузырька. Однако оказывается, что усовершенствование сортировки, основанной на обмене, дает лучший из всех известных методов сортировки массивов. Этот метод изобрел К. Хоор и дал ему название быст- рая сортировка. Хотя этот метод можно было бы назвать сортировкой сег- ментацией. Идея этого метода основана на том факте, что наибольшая эффектив- ность достигается, если производить обмены элементов, отстоящих друг от друга на большом расстоянии. Так, например, если исходный массив упоря- дочен по убыванию, то всего за N/2 обменов его можно отсортировать: по- менять местами первый и последний элементы, второй и предпоследний и так далее, продвигаясь от концов массива к его середине. Этот экзотический пример приводит к рассмотрению следующего алгоритма. Выберем некоторым образом элемент x и будем просматривать массив, двигаясь слева направо, пока не найдем элемент a[i]>x, затем будем просмат- ривать массив справа налево, пока не найдем элемент a[j]<x. Поменяем мес- тами эти элементы и продолжим «просмотр с обменом», пока индексы i и j не встретятся где-то в середине массива. В результате массив разделится на две части: в левой значения элементов будут меньше, чем x, а в правой — больше x. Это пока не сортировка — только разделение. Для полной сортировки не- обходимо то же самое проделать с левой и правой частями массива, затем с частями этих частей, и так до тех пор, пока каждая часть не будет содержать только один элемент. Мы получили типичный рекурсивный подход: − параметризация — обрабатывается подмассив a[i, j], для всего массива i = 1, j = N; − тривиальный случай i = j, когда не выполняется никаких дейст- вий. В качестве x будем брать значение среднего элемента. Оказывается, что такой выбор в подавляющем большинстве случаев распределения элементов в исходном массиве приводит к хорошим результатам. Более подробно о вы- боре x можно прочитать в [32]. Реализация функции быстрой сортировки приведена в листинге 3.8. 11 / 23 |
