Читайте также:
|
Слияние означает объединение двух или более упорядоченных массивов в один упорядоченный массив.
Самый простой способ сделать это – сравнить два наименьших элемента, вывести наименьшее из них и повторить процедуру
Слияние означает объединение двух или более упорядоченных массивов в один упорядоченный массив.
Самый простой способ сделать это – сравнить два наименьших элемента, вывести наименьшее из них и повторить процедуру
структура
М1. Установить i←1, j←1, k←1.
М2. Если xi ≤ yj,, перейти к М3, в противном случае к М5.
М3. Установить zk ← xi, k ← k+1, i←i+1. Если i ≤ m, вернуться к М2.
М4. Установить (zk, …, z(m+n)) ← (yj, …, yn) и завершить выполнение.
М5. Установить zk ← yj,,, k ← k+1, j←j+1. Если j≤n, вернуться к шагу М2.
М6. Установить (zk, …, z(m+n))←(xi, …,xm) и завершить алгоритм.
А) Алгоритмы быстрой сортировки.
(Сортировка Хоара или сортировка с помощью разделения)
Этот алгоритм является примером использования рекурсии. Он был разработан в 1962 году, профессором Оксфордского университета Хоаром. (Основан на алгоритме сортировки обменами).
Принцип метода: для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Выберем наугад какой-либо элемент (х) и будем просматривать слева массив до тех пор, пока не обнаружим элемент Ri> x, затем будем просматривать массив справа, пока не встретим Rj<x. Теперь поменяем их местами и продолжим процесс просмотра и обмена, пока оба просмотра не встретятся в середине массива. В результате массив окажется разбитым на левую часть с ключами ≤ x, и правую – с ключами ≥ x.
Таким образом, относительно значения x массив получается отсортированным, но левая и правая части ещё не упорядочены.
Дата добавления: 2015-07-16; просмотров: 99 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Сортировка посредством выбора | | | Сортировка с помощью включений с уменьшающимися расстояниями (Сортировка Шелла) |