Cортировка слиянием с использованием O(1) дополнительной памяти — различия между версиями
(→Ссылки) |
|||
| Строка 1: | Строка 1: | ||
| − | =Ссылки= | + | Научившись сливать с использованием O(1) дополнительной памяти оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером <tex> 2^i </tex>(за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем. |
| + | |||
| + | == Слияние == | ||
| + | === Шаг 1 === | ||
| + | Разобьем наш массив на группы | ||
| + | === Шаг 2 === | ||
| + | |||
| + | =Ссылки и литература= | ||
*[http://e-maxx.ru/bookz/files/knuth_3.djvu| Д.Е.Кнут - Искусство программирования (том 3) упр 18 к разделу 5.2.4] | *[http://e-maxx.ru/bookz/files/knuth_3.djvu| Д.Е.Кнут - Искусство программирования (том 3) упр 18 к разделу 5.2.4] | ||
*[http://pastebin.com/hN2SnEfP Реализация алгоритма на JAVA] | *[http://pastebin.com/hN2SnEfP Реализация алгоритма на JAVA] | ||
Версия 05:55, 7 июня 2011
Научившись сливать с использованием O(1) дополнительной памяти оставшееся решение задачи становится очевидным. Будем сливать не рекурсивно, чтобы сэкономить память в стеке. Пусть на i-том шаге у нас отсортированы подряд идущие, не пересекающиеся куски массива размером (за исключением последнего, его размер может быть меньше). Тогда сольем сначала первый и второй кусок, потом третий и четвертый и так до последнего. Если последнему куску нету пари, то просто ничего не делаем.
Содержание
Слияние
Шаг 1
Разобьем наш массив на группы
