Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента небезразличен, т.к. можно подобрать пример, при котором алгоритм с выбором медианы в качестве опорного элемента будет выдавать неправильный ответ. Известные стратегии: выбирать постоянно один и тот же элемент, например, последний по положению; выбирать элемент со случайно выбранным индексом.
Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:
повторить рекурсивно для «меньших» и «больших».
сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.
выбрать элемент, называемый опорным.
Быстрая сортировка (англ. quicksort), часто называемая qsort по имени реализации в стандартной библиотеке языка Си широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Один из быстрых известных универсальных алгоритмов сортировки массивов (в среднем O(n log n) обменов при упорядочении n элементов), хотя и имеющий ряд недостатков.
Вы находитесь здесь: » »
tema:algoritm_bystroj_sortirovki [ЛИКТ 590]
Комментариев нет:
Отправить комментарий