49504 (Элементарные методы сортировки), страница 2
Описание файла
Документ из архива "Элементарные методы сортировки", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "49504"
Текст 2 страницы из документа "49504"
Основная идея алгоритма состоит в том, чтобы отсортировать все группы файла состоящие из элементов файла отстоящих друг от друга на расстояние h. Такие файлы называются h-сортированными. Когда мы h-сортируем файл по некоторому большому h, мы передвигаем его элементы на большие растояния. Это облегчает работу сортировки для меньших значений h. Процесс заканчивается когда h уменьшается до 1.
Приведенная программа использует последовательность… 1093, 364, 121, 40, 13, 4, 1. Могут существовать и другие последовательности – одни лучше, другие хуже.
Свойство 6 Оболочечная сортировка никогда не делает более чем N1.5 сравнений для вышеуказанной последовательности h.
Подсчет распределения
Во многих случаях мы знаем, что значения ключей в файле лежат в каких либо пределах. В этих ситуациях применим алгоритм, именуемый подсчет распределения. Здесь приведена программа для этого простого алгоритма.