Для удобства редактирования весь FAQ представлен в виде чистого текста, с минимумом ссылок, и без изображений.
В процессе работы над FAQом я смотрел многие источники по этим вопросам, в которых(даже написанных самыми уважаемыми авторами) зачастую давались разные, иногда противоречивые сведения. Особенно это касается характеристик сортировок.
В FAQ были включены те, которые я счел правильными. Однако 'субъективных' оценок алгоритмов не бывает, поэтому по всем вопросам, вызывающим аргументированные сомнения, пишите мне на адрес:
В этом разделе :
8 Ликбез для понимания важной информации
Что означает символ O(n) ? Оценки Omega() и Theta(). Почему _не пишется_ основание логарифма: O(logn) ?
8 Какие на сегодняшний день самые эффективные методы сортировки ?
8 Описание и исходник SelectSort (сортировка выбором).
8 Сортировка пузырьком BubbleSort и ее улучшения с исходниками.
Операция сравнения/перестановки выполняется для каждых двух стоящих рядом элементов. После первого прохода по массиву "e;вверху"e; оказывается самый "e;легкий"e; элемент.
8 Описание и исходник InsertSort (сортировка простыми вставками).
8 Описание и исходник ShellSort (сортировка Шелла).
Этот алгоритм - модификация сортировки простыми вставками
8 Сортировка двоичным деревом, древесная сортировка.
Двоичным(бинарным) деревом назовем упорядоченную структуру данных, в которой каждому элементу - предшественнику или корню (под)дерева - поставлены в соответствие по крайней мере два других элемента (преемника).
8 Описание и исходник QuickSort (быстрая сортировка)
Выберем случайным образом какой-то элемент х и просмотрим массив, двигаясь слева направо, пока не найдем аi больший x, а затем справа налево, пока не найдем аi меньший х.
8 Описание и исходник HeapSort (пирамидальная сортировка).
8 Описание MergeSort (сортировка слиянием).
8 Что такое Байтовая, Цифровая, Радиксная или Распределяющая сортировка ?
Пусть имеем максимум по k байт в каждом ключе ( хотя за элемент сортировки вполне можно принять и что-либо другое, например слово - двойной байт, или буквы, если сортируются строки). k должно быть известно заранее, до сортировки.
8 Требования и свойства сортировок. Что когда лучше?
Какая самая быстрая сортировка? Что лучше: распределяющая сортировка или сортировка сравнениями?
8 Есть большой файл. Как его отсортировать ? Многофазное слияние.
В другом вопросе описывается простейшая сортировка слиянием. Ее вполне можно применить к любому файлу и она будет работать.
| |
*
Обратная связь