Читайте также:
|
Этот приём основан на следующих принципах:
1. Выбирается элемент с наименьшим ключом
2. Он меняется местами с первым элементом R1
3. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и так далее до тех пор, пока не останется один, самый большой элемент.
Этот метод требует наличие всех исходных элементов до начала сортировки, а элементы вывода порождает последовательно, один за другим, Картина, по существу, противоположна картине, возникающей при использовании метода вставок, в котором исходные записи поступают последовательно, но вплоть до завершения сортировки об окончательном результате ничего не известно.
О(nlogn) алгоритмы сортировки. Обменная сортировка.
• Это семейство алгоритмов сортировки, предусматривающих системный обмен местами между элементами пар, в которых нарушается упорядоченность, до тех пор, пока таких пар не останется.
(Пузырьковая сортировка).
• Заключается в сравнении двух соседних элементов массива, в результате которого меньшее число (более легкий пузырёк) перемещается на одну позицию влево. Обычно такой просмотр организуют с конца массива и после первого прохода самое маленькое число перемещается на первое место. Затем все повторяется от конца массива до второго элемента и так далее.
• Метод назван «методом пузырька», потому что маленькие элементы, подобно пузырькам, «всплывают» на соответствующую позицию.
Время работы этого алгоритма определяется тремя параметрами: числом проходов А, числом обменов В и числом сравнений С. Улучшение этого алгоритма происходит само собой. Из примера видно, что три последовательных элемента не влияют на порядок элементов из-за того, что они уже отсортированы. Один из примеров улучшения этого метода – запоминать, были или нет перестановки в процессе некоторого прохода.
Дата добавления: 2015-07-16; просмотров: 39 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Анализ сложных алгоритмов | | | Сортировка методом слияния.(двухпутевое слияние) |