Предисловие
В этой книжечке содержится информация о нескольких алгоритмах сортировки и поиска. Эту информацию можно найти
во множестве книг – в большинстве из них предполагается знание математического анализа и теории вероятностей.
Хотя формальное исследование алгоритмов и доказательство результатов, описывающих их асимптотические свойства,
очень важны, часто важны и возможны чисто интуитивные объяснения.
Здесь все алгоритмы объяснены в наиболее простом виде. Предполагается, что вы владеете Си или Паскалем по
крайней мере на начальном уровне. В частности, вы должны знать, что такое массивы и указатели. Материал представлен
здесь в порядке от простого к чуть более сложному. Несмотря на то, что этот текст предназначен для начинающих,
в нем есть разделы, которые могут оказаться интересными и более продвинутым читателям. В особенности это относится
к разделам о хеш-таблицах и скип-списках.
Санта-Круз, Калифорния - Томас Ниман
Март 1995
Замечание переводчика
При чтении RU.ALGORITHMS в русском ФИДО я часто натыкаюсь на малограмотные и/или неверные утверждения. Этот
текст показался мне интересным для начинающих – он, по крайней мере, убережет их от совсем уж непростительных
заблуждений.
Москва - Павел Дубнер
Февраль 1998
Оглавление
- ВВЕДЕНИЕ
- СОРТИРОВКА
- Сортировка вставками
- Сортировка Шелла
- Быстрая сортировка
- Сравнение методов
- СЛОВАРИ
- Хеш-таблицы
- Поиск в бинарных деревьях
- Красно-черные деревья
- Разделенные списки
- Сравнение методов
- ТЕКСТЫ ПРОГРАММ
- Коды для сортировки вставками
- Коды для сортировки Шелла
- Коды для быстрого поиска (функции Quicksort)
- Коды для стандартной реализации быстрого поиска
- Коды для хеш-таблиц
- Коды для бинарных деревьев
- Коды для красно-черных деревьев
- Коды для разделенных списков
- ЛИТЕРАТУРА
- СЛОВАРЬ
|