Переходя к более практичному приложению, мы рассмотрим рекурсивный алгоритм сортировки массива. Алгоритмы сортировки выбором и сортировки вставками, рассмотренные в разделе 7.4, довольно просты, но они довольно медленны при применении к большим массивам. Доступны более быстрые алгоритмы сортировки. Одним из них является Quicksort, рекурсивный алгоритм, который в большинстве ситуаций оказывается самым быстрым алгоритмом сортировки.
Алгоритм быстрой сортировки основан на простой, но умной идее: при наличии списка элементов выберите любой элемент из списка. Этот элемент называется стержнем. (На практике я просто буду использовать первый элемент в списке.) Переместите все элементы, которые меньше, чем опорная точка, в начало списка, а все элементы, которые больше, чем опорная точка, переместите в конец списка. список. Теперь поместите точку опоры между двумя группами элементов. Это помещает стержень в позицию, которую он займет в окончательном, полностью отсортированном массиве. Его не нужно будет снова перемещать. Мы будем называть эту процедуру QuicksortStep.
QuicksortStep не является рекурсивным. Он используется как подпрограмма Quicksort. Скорость Quicksort зависит от быстрой реализации QuicksortStep. Поскольку это не является основным пунктом данного обсуждения, я представляю его без особых комментариев.
Посетите дополнительную информацию:https://www.wikiod.com/w/Category:Java_Language
