|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Popov 2:5025/38.90 12 Jun 2001 03:48:36
To : All
Subject : сортировка динамического списка
--------------------------------------------------------------------------------
05 Июн 01 12:22, Andrew Kadatch -> All:
>> IZ> Hарод, поделитесь сабжем. Hе дайте погибнуть заочнику :)))
>> IZ> В книгах не нашёл, а своим умом не могу дойти, не хватает
>> IZ> информации, да и материал этот не начитывали.
>> IZ> Сабж нужен на паскале.
>> а cколко я помню cпcки только вcтавкой cоpтиpовать можно.
AK>
AK> Hу-ну... А если построить сбалансированное дерево поиска (AVL, 2-3,
AK> red-black, и т.д)
AK> и затем обойти?
AK>
AK> А как же классическая сортировка слиянием -- одна из лучших?
AK>
AK> Рассмотрим неотсортированный список длины N как последовательность
AK> из N подсписков длины 1. Подсписок, содержащий ровно один элемент,
AK> отсортирован по определению.
AK>
AK> Допустим, что на некотором шаге имеется последовательность из K
AK> отсортированных
AK> подсписков длины M (кроме последнего, который может быть короче).
AK> Возьмем два первых отсортированных подсписка и сольем их в один список
AK> длины 2M сравнением первых элементов подсписков и удалением наибольшего,
AK> который необходимо добавить в конец порождаемого списка.
AK>
AK> Применив слияние K/2 раз, получим последовательность из K/2
AK> отсортированных подсписков длины 2М. Итак, на каждом шаге количество
...skip...
А может лучше использовать
двухпутевое однофазное естественное несбалансированное слияние.
Удачи тебе! -=Sera is over Now!=-
np: Tom Waits - Nighthawks Postcards
--- GoldED/W32 3.0.1
* Origin: See you in another world (2:5025/38.90)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
