Изменения

Перейти к: навигация, поиск

Обсуждение:PSRS-сортировка

1238 байт добавлено, 18:45, 18 мая 2014
Метод Шелла
Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Что касается константы <tex>C</tex>, то <tex>C \cdot N \cdot (N/8+log_{2} N) \approx N^2/8</tex>, следовательно <tex>C=1/8</tex>.
=== Метод Шелла ===
Метод Шелла основан на том, что сортировка вставками более эффективна на маленьких или на частичной отсортированных входных данных. Устройство метода Шелла более понятно если рассматривать его на фиксированном наборе данных. Например мы имеем набор из 16 элементов <tex>R_1...R_16</tex> разобьём их на пары <tex>(R_1,R_9),...,(R_8,R_16)</tex>. Отсортируем каждую из пар. Разобьем на группы по 4 элемента <tex>(R_1,R_5,R_9,R_13),...,(R_4,R_8,R_12,R_16)</tex>. Отсортируем каждую из пар.Разобьём на 2 группы <tex>(R_1,R_3,R_5,R_7,R_9,R_11,R_13,R_15),...,(R_2,R_4,R_6,R_8,R_10,R_12,R_14,R_16)</tex>. Отсортируем каждую из пар. Каждое разделение называется проходом. При четвёртоми последнем проходе сортируются все 16 элементов. В итоге получится отсортированный массив.
 
===Вставка в список ===
=== Сортировка с вычисление адреса ===
77
правок

Навигация