Сортировка по возрастанию методом Пузырька

Сортировка по возрастанию методом Пузырька

Последовательно просматриваем числа a₀, ..., a_n-1 находим наименьшее i такое, что a_i > a_i+1. Поменять a_i и a_i+1 местами, возобновить просмотр с элемента a_i+1 и т.д. Тем самым наибольшее число передвиниться на последнее место. Следующие просмотры начинать опять сначала, уменьшая на единицу количество просматриваемых элементов. Массив будет упорядочен после просмотра, в котором участвовали только первый и второй элементы.

Сортировка по возрастанию простым выбором

Допустим, что элементы a₀, ..., a_i-1 уже упорядочены, тогда среди оставшихся a_i, ..., a_n-1 находим минимальный элемент и меняем его местами с i-тым элементом. И так далее, пока массив не будет полностью упорядочен.

Сортировка по возрастанию методом простых вставок

Последовательно просматриваем a₁, ..., a_n-1 и каждый новый элемент a_i вставляем на подходящее место в уже упорядоченную совокупность a₀, ..., a_i-1. Это место определяется последовательным сравнением a_i с упорядоченными элементами a₀, ..., a_i-1.

Сортировка по возрастанию посчетом

Этот метод подходит для сортировки целых чисел из не очень большого диапазона (сравнимого с размером массива). Для каждого элемента находим количество элементов, меньших данного, и количество элементов, равных данному. Заполняем новый массив с позиции, равной сумме элементов меньших данного до суммы элементов, меньших данного + суммы элементов, равных данному - 1.

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

При сортировке Шелла сначала сравниваются и сортируются между собой элементы, отстоящие один от другого на некотором расстоянии d. После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1, то есть, обычной сортировкой вставками. Обычно d выбирают следующим образом: d1 выбирают сначала равным N/2, затем d1/2 и т.д.

Пример:

Пусть дан список A = (32,95,16,82,24,66,35,19,75,54,40,43,93,68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5,3,1.

На первом шаге сортируются подсписки A, составленные из всех элементов A, различающихся на 5 позиций, т. е. подсписки A_5,1 = (32,66,40), A_5,2 = (95,35,43), A_5,3 = (16,19,93), A_5,4 = (82,75,68), A_5,5 = (24,54).

В полученном списке на втором шаге вновь сортируются подсписки из отстоящих на 3 позиции элементов.

Сортировка черпаком

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