for 1 = [1. п)
t = X [ 1 ]
for (j = 1. J > 0 && х[j-1] > t. j - -)
X [ J J = X [ J -1 ]
X[j] = t
Эта программа сдвигает элементы вправо до тех пор, пока они превосходят значение t, а потом ставит t в правильную позицию. Эта функция из пяти строк чуть сложнее своих предшественников, но на моем компьютере она работает примерно на 15% быстрее, чем вторая версия той же сортировки.
Для случайного расположения элементов во входном массиве, как и в худшем случае (обратный порядок сортировки), время выполнения сортировки вставкой пропорционально п\ Таблица 11.1 содержит данные о времени выполнения трех программ, когда па вход подается п случайных целых чисел.
Программа Объем (строк на языке С) Время, не
Сортировка вставкой (1) 3 11,9л2
Сортировка вставкой (2) 5 3,8/72
Сортировка вставкой (3) 5 3,2/г
Третьей программе требуется несколько миллисекунд для сортировки п = 1000 целых чисел, треть секунды на п = 10 ООО целых, и почти час па сортировку миллиона чисел. Скоро мы встретимся с программой, сортирующей миллион чисел меньше, чем за секунду. Если входной массив уже почти отсортирован, сортировка вставкой работает гораздо быстрее, поскольку все элементы сдвигаются лишь на небольшое расстояние. Алгоритм в разделе 11.3 данной главы основан именно на этом свойстве.
Опубликовал vovan666
April 17 2013 00:02:31 ·
0 Комментариев ·
4576 Прочтений ·
• Не нашли ответ на свой вопрос? Тогда задайте вопрос в комментариях или на форуме! •
Комментарии
Нет комментариев.
Добавить комментарий
Рейтинги
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
Гость
Вы не зарегистрированны? Нажмите здесь для регистрации.