Последовательно просматриваются элементы массива, если встречается неупорядоченная пара Аk > Ak -1, то элементы этой пары меняются местами; просмотр продолжается до Аn. В результате первого просмотра наибольший элемент оказывается на первом месте. Второй просмотр начинается с первого элемента и заканчивается элементом Аn -1. алгоритм заканчивается, когда в просмотре участвуют только два первых элемента.
Сортировка обменами II
Последовательно просматриваются элементы массива, если встречается неупорядоченная пара Аk > Ak -1, то элементы меняются местами; после чего просмотр начинается с начала массива. Алгоритм заканчивается, когда в результате очередного просмотра не удается найти упорядоченной пары.
Сортировка выбором
Из элементов массива выбирается минимальный и меняется местами с первым элементом. В результате первого выбора минимальный элемент оказывается на первом месте. Второй выбор минимума начинается со второго элемента. Далее процесс возобновляется до тех пор, пока среди выбираемых не останутся два последних элемента.
|
|
Сортировка простыми вставками
Применяется в этом случае, когда часть массива уже упорядочена. Просматриваются последовательно А 2,…, An и каждый новый элемент Ai вставлять на подходящее место в уже упорядоченную совокупность A 1… Ai -1. Это место определяется последовательным сравнением Ai с упорядоченными элементами A 1… Ai- 1.
Сортировка бинарными вставками
Применяется, как и предыдущий метод, в тех случаях, когда часть массива уже упорядочена. Отличие от сортировки простыми вставками заключается в том, что позиция, в которую «вставляется» очередной элемент, определяется не последовательным сравнением, а алгоритм деления пополам.
«Быстрая» сортировка (алгоритм Хоара)
Выбрать «средний» элемент массива. Затем переставить остальные элементы таким образом, чтобы слева от выбранного элемента оказались все элементы меньшие его, а справа – все элементы больше его. Тем самым выбранный элемент окажется «на своем месте». После чего следует рекурсивно применить данный алгоритм к частям массива справа и слева от очередного среднего.