http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=5.18.60.187&* 2026-05-04T05:49:41Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=Smoothsort&diff=44976 2015-03-13T20:20:19Z

<p>5.18.60.187: </p> <hr /> <div>'''''Smoothsort''''' (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную &lt;tex dpi = 120&gt; O(n log n) &lt;/tex&gt;. Преимущество плавной сортировки в том, что её сложность приближается к &lt;tex dpi = 120&gt; O(n) &lt;/tex&gt;, если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных.<br /> =Основная идея=<br /> Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:<br /> <br /> &lt;tex dpi = 120&gt; L(0) = 1, L(1) = 1, L(i) = L(i - 1) + L(i - 2) + 1 &lt;/tex&gt;</div>

5.18.60.187 http://neerc.ifmo.ru/wiki/index.php?title=Smoothsort&diff=44975 2015-03-13T20:19:34Z

<p>5.18.60.187: Новая страница: «'''''Smoothsort''''' (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сор...»</p> <hr /> <div>'''''Smoothsort''''' (Плавная сортировка) -- алгоритм сортировки, разновидность пирамидальной сортировки, разработанная Э. Дейкстрой в 1981 году. Как и пирамидальная сортировка, имеет сложность в худшем случае равную &lt;tex dpi = 120&gt; O(n log n) &lt;/tex&gt;. Преимущество плавной сортировки в том, что её сложность приближается к &lt;tex dpi = 120&gt; O(n) &lt;/tex&gt;, если входные данные частично отсортированы, в то время как у пирамидальной сортировки сложность всегда одна, независимо от состояния входных данных.<br /> ==Основная идея==<br /> Как и в пирамидальной сортировке, в массив накапливается куча из данных, которые затем сортируются путём непрерывного удаления максимума из кучи. В отличие от пирамидальной сортировки, здесь используется не двоичная куча, а специальная, полученная с помощью чисел Леонардо:<br /> <br /> &lt;tex dpi = 120&gt; L(0) = 1, L(1) = 1, L(i) = L(i - 1) + L(i - 2) + 1 &lt;/tex&gt;</div>

5.18.60.187