2015-01-30
426
Пусть m = log 2 N, где N — количество элементов. Будем считать, что количество элементов, меньших разделителя, равно количеству элементов, больших разделителя, т.е. массив разбивается пополам на две равные части. Определим количество сравнений в этом случае:
N + 2·(N / 2) + … + m·(N / m) = O(N·m) = O(N·log2N).
Если каждый раз одна из частей массива содержит не более одного элемента, то порядок будет O(N2).
Характер разбиения массива, а, следовательно, и порядок функции ВС, зависит от соотношения разделителя и остальных элементов массива. Для определения «хорошего» разделителя имеются различные алгоритмы.
Пирамидальная сортировка
Пирамидальная сортировка является улучшенной сортировкой выбором. Из массива, состоящего из N элементов, выбирается максимальный и меняется местами с последним. Затем рассмат-ривается массив из N = N – 1 элементов. Процесс повторяется до тех пор, пока количество рассматриваемых элементов больше одного. Пира-мидальная сортировка отличается от сортировки выбором поиском максимального элемента. Чтобы понять пирамидальную сортировку, массив нужно интерпретировать как бинарное дерево, в корне которого находится первый элемент массива, на втором уровне — второй и третий, на третьем — с четвертого по седьмой и т.д. Для i-го элемента массива можно определить номер P элемента, являющегося родителем, как P = i div 2; номер L элемента, являющегося левым сыном, как L = 2·i; номер R элемента, являющегося правым сыном, как R=2·i+1. Если в массиве (в дереве) N элементов, то последний элемент, имеющий хотя бы одного левого сына, имеет номер (N div 2). Массив M (см. таблицу 10) можно представить деревом на рис.5.
|
|
|
Таблица 10
