• Постановка задачи. Выходная последовательность — это упорядоченная перестановка входной последовательности. Если на входе — дисковый файл, на выходе, как правило, другой файл; если на входе — массив, па выходе, как правило, тот же самый массив.
• Приложения. Приведенный ниже список всего лишь намекает па разнообразие приложений сортировки.
• Требования к выходной информации. Некоторые пользователи требуют упорядочения выходной информации; см. раздел 1.1 и ваш телефонный справочник. Функции поиска, аналогичные двоичному, требуют предварительной сортировки.
• Группировка одинаковых элементов. Программисты используют сортировку, чтобы сгруппировать вместе одинаковые элементы: программа поиска анаграмм из разделов 2.4 и 2.8 собирает вместе слова из одного класса анаграмм. Массивы остатков из разделов 15.2 и 15.3 собирают вместе похожие фразы. См. также задачи 2.6, 8.10 и 15.8.
• Другие приложения. Программа поиска анаграмм из разделов 2.4 и 2.8 использовала сортировку для получения канонического порядка следования букв слова, что позволяло получить сигнатуру класса анаграмм. В задаче 2.7 сортировка используется для реорганизации данных на лейте.
• Функции общего назначения. Приведенные ниже алгоритмы сортируют произвольную последовательность из п элементов.
• Сортировка вставкой (insertion sort). Программа в разделе 11.1 работала за время 0(п2) как в худшем случае, так и для случайных входных данных. Время выполнения нескольких ее версий приведено в таблице в этом разделе. В разделе 11.3 сортировка вставкой использовалась для упорядочения почти отсортированного массива за время 0{п). Это единственная стабильная сортировка в этой книге: элементы с равными ключами оказываются на выходе в том же порядке, в котором они были на входе.
• Быстрая сортировка (quicksort). Простая быстрая сортировка в разделе 11.2 работает за время 0(п log л) на массиве из п различных элементов. Она реализуется рекурсивно и использует логарифмически растущий объем памяти на стеке. В худшем случае она работает за время 0(п2) и требует О(п) памяти. Время 0(п2) достигается на массиве одинаковых элементов; улучшенная версия быстрой сортировки из раздела 11.3 работает за время O(nlogn) на любом массиве. Таблица в разделе 11.3 содержит эмпирические данные о времени работы нескольких реализаций быстрой сортировки. Стандартная библиотечная функция языка С qsort обычно реализуется на основе этого алгоритма. Она применяется в разделах 2.8, 15.2 и 15.3, а также в решении
Опубликовал vovan666
April 17 2013 00:05:11 ·
1 Комментариев ·
2979 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Oleg27 October 23 2023 11:56:18
Советую Вам выделить немного свободного времени, и изучить вот на этом ресурсе обзоры букмекерских контор 1хбет рабочее зеркало . Только так Вы сможете найти ту, у которой условия будут наилучшими. Времени на это много не уйдёт.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.
Главная
Каталог файлов
