class DarkRaha extends com { // разработка приложений
            String a="Главная" b="Контакты" c="О сайте"
};

Мандельброт
IFS
фильтрация
rgb эффекты
интерполяция
определенный интеграл
диффиренциальные уравнения
простые, сложные проценты
сортировка

Алгоритмы

Методы сортировки

быстрая сортировка

Это основной алгоритм сортировки, ибо в большинстве случаев он дает наилучшие результаты (придумал Hoare). Основная идея заключается в следующем. Выберем некий элемент M внутри диапазона, например в середине. Затем все элементы большие этого числа переносятся в одну сторону, а меньшие в другую. На практике это выглядит так:

Продолжаем это до тех пор, пока больший элемент и меньший лежат по разные стороны. После этого вызываем алгоритм рекурсивно для двух новых диапазонов, границами которых служат последние индексы найденных меньшего и большего элементов.

Пузырьковая сортировка

Это самый простой и медленный способ сортировки. Также называет методом перестановок. Основная идея заколючается в том, чтобы менять местами два соседних элемента, если их расположение не удовлетворяет условию сортировки. Таким образом, за первый проход самый большой элемент будет в конце (или в начале) сортируемого множества. Дополнительно можно проверять наличие обмена элементов на каждом проходе, чтобы не делать лишние проходы. По сути быстрая сортировка является модификацией этого метода.

Сортировка методом вставки

Здесь основная идея в том, чтобы вставить следующий не отсортированный элемент в нужную позицию уже отсортированного диапазона. На практике это выглядит так:

Продолжаем процесс до конца сортируемого множества.

Сортировка методом Шелла

Это довольно трудный для понимания метод, основанный на сортировке простыми вставками (придумал Shell). Оснавная идея состоит в том, чтобы сортировать методом вставки не сразу все элементы, а по частям. Часто используется следующая последовательность. В первом проходе в сортировке участвует каждый 16 элемент, на втором проходе каждый 8, на третьем каждый 4, на втором каждый второй, и в конце обязательно проводится обычная сортировка вставками. Помимо приведенной последовательности (...,16,8,4,2,1), могут использоваться и другие последовательности.

Сортировка выборкой

В этом алгоритме основная идея заключается в том, чтобы на каждом проходе найти наименьший или наибольший элемент и поменять его с первым или последним не отсортированным элементом в зависимости от условия сортировки.


Существуют и другие методы сортировки как пиромидальная и слиянием, однако в большинстве случаев метода быстрой сортировки вполне достаточно.

Скачать класс AlgoSort.


Рейтинг@Mail.ru