Сортировка и поиск: Рецептурный справочник

Предисловие

В этой книжечке содержится информация о нескольких алгоритмах сортировки и поиска. Эту информацию можно найти во множестве книг – в большинстве из них предполагается знание математического анализа и теории вероятностей. Хотя формальное исследование алгоритмов и доказательство результатов, описывающих их асимптотические свойства, очень важны, часто важны и возможны чисто интуитивные объяснения.

Здесь все алгоритмы объяснены в наиболее простом виде. Предполагается, что вы владеете Си или Паскалем по крайней мере на начальном уровне. В частности, вы должны знать, что такое массивы и указатели. Материал представлен здесь в порядке от простого к чуть более сложному. Несмотря на то, что этот текст предназначен для начинающих, в нем есть разделы, которые могут оказаться интересными и более продвинутым читателям. В особенности это относится к разделам о хеш-таблицах и скип-списках.

Замечание переводчика

При чтении RU.ALGORITHMS в русском ФИДО я часто натыкаюсь на малограмотные и/или неверные утверждения. Этот текст показался мне интересным для начинающих – он, по крайней мере, убережет их от совсем уж непростительных заблуждений.

Оглавление

1. ВВЕДЕНИЕ
2. СОРТИРОВКА
   1. Сортировка вставками
   2. Сортировка Шелла
   3. Быстрая сортировка
   4. Сравнение методов
3. СЛОВАРИ
   1. Хеш-таблицы
   2. Поиск в бинарных деревьях
   3. Красно-черные деревья
   4. Разделенные списки
   5. Сравнение методов
4. ТЕКСТЫ ПРОГРАММ
   1. Коды для сортировки вставками
   2. Коды для сортировки Шелла
   3. Коды для быстрого поиска (функции Quicksort)
   4. Коды для стандартной реализации быстрого поиска
   5. Коды для хеш-таблиц
   6. Коды для бинарных деревьев
   7. Коды для красно-черных деревьев
   8. Коды для разделенных списков
5. ЛИТЕРАТУРА
6. СЛОВАРЬ