Читайте также:
|
|
Элементы массива мысленно делятся на 2 последовательности: "готовую" - которая стоит в слева и все элементы которой упорядочены, и "исходную" - состоит из неупорядоченных элементов исходного массива. На каждом шаге i, начиная с i=2, из исходной последовательности извлекается i-ый элемент и перекладывается в нужное место готовой последовательности путем сравнения с ее элементами.
Максимальное число сравнений: C = n-1
Минимальное число сравнений: C = 1
Среднее число сравнений: C = i/2
Среднее число пересылок: M = C + 2
Пример:
Исх.послед. 55 44 12 42 94 18 06 67
i=2 44 55 12 42 94 18 06 67
i=3 12 44 55 42 94 18 06 67
i=4 12 42 44 55 94 18 06 67
i=5 12 42 44 55 94 18 06 67
i=6 12 18 42 44 55 94 06 67
i=7 06 12 18 42 44 55 94 67
i=8 06 12 18 42 44 55 67 94
Сортировка с помощью прямого выбора
Пусть имеется массив An, где n - количество элементов в массиве. Сначала выбирается элемент с наименьшим значением и меняется местами с элементом A1. Этот процесс затем осуществляется с отставшимися n-1 элементами, n-2 элементами и так до тех пор пока не останется один самый больший элемент.
Число сравнений: C = (n2 - n)/2
Число перестановок: Mmin = 3 * (n-1)
Mmax = n2/4 + 3 * (n-1)
Пример:
Исх.послед. 55 44 12 42 94 18 06 67
06 44 12 42 94 18 55 67
06 12 44 42 94 18 55 67
06 12 18 42 94 44 55 67
06 12 18 42 94 44 55 67
06 12 18 42 44 94 55 67
06 12 18 42 44 55 94 67
06 12 18 42 44 55 67 94
Сортировка с помощью прямого обмена (Пузырьковая сортировка)
Идея данной сортировки основана на парном сравнение соседних элементов в массиве и перестановке их в требуемом порядке: процесс продолжается до полного упорядочения всех элементов.
Пример:
Исх.послед. 19 13 05 27 01 26 31 16 02 09 11 21
i = 1 13 05 19 01 26 27 16 02 09 11 21 31
i = 2 05 13 01 19 26 16 02 09 11 21 27 31
i = 3 05 01 13 19 16 02 09 11 21 26 27 31
i = 4 01 05 13 16 02 09 11 19 21 26 27 31
i = 5 01 05 13 02 09 11 16 19 21 26 27 31
i = 6 01 05 02 09 11 13 16 19 21 26 27 31
i = 7 01 02 05 09 11 13 16 19 21 26 27 31
Как видно из примера, после 1-го прохода самый больной элемент перемещается в конец массива, соответственно при 2-ом проходе данный элемент можно исключить из просмотра, что существенно сократит время сортировки.
Шейкерная сортировка
Данный метод является видоизменением метода прямого обмена, при нем происходит чередование просмотров, то есть изменения их направления: сначала слева - направо, затем справа - налево и т.д. Этот способ дает уменьшение числа сравнений по сравнению с методом прямого обмена.
Сортировка методом Шелла
Идея сортировки предложенная Шеллом состоит в перемещение значений путем перестановки пар, причем сравниваются значения, находящиеся на некотором расстоянии d. При этом значения, стоящие не на месте будут перемещаться быстрее, чем при простом обмене. На каждом новом шаге просмотра значение d обычно уменьшается, при
этом:
di = (di-1 + 1) / 2
При просмотре каждое значение сравнивается со значением, расположенным на d позиции дальше в векторе величин. Если верхнее значение больше нижнего значения, то делается перестановка и т.д.
Пример:
исх. массив | Просмотры | |||
d=6 | d=3 | d=2 | d=1 | |
09 x | 02 x | 01 x | ||
01 x | 02 x | |||
02 x | 09 x | 05 x | ||
09 x | 19 x | 05 x | 09 x | |
11 xx | ||||
21 x | 05 x | 13 xx | ||
27 x | 16 xx | |||
13 xx | 19 x | |||
05 x | 21 x | 21 xxx | ||
31 x | 26 x | |||
16 x | 27 x | |||
26 x | 31 xx |
Обозначения: x - обмен, хх - двойной обмен, ххх - тройной обмен
Дата добавления: 2014-12-15; просмотров: 28 | Поможем написать вашу работу | Нарушение авторских прав |