Shell сортировки алгоритм сортировки, который требует меньше Асимптотически O (N) сравнений и обменов в худшем случае. Хотя это легко развить интуитивное понимание того, как этот алгоритм работает, это очень трудно анализировать его исполнение, но по оценкам, от O (nlog2 N) О (n1.5) в зависимости от деталей реализации.
Сортировка Шелла является обобщением вставок, с двумя замечаниями в виду:
- Insertion sort is efficient if the input is «almost sorted».
- Insertion sort is inefficient, on average, because it moves values just one position at a time.
Shell рода улучшает вставок путем сравнения элементов, разделенных пробелами из нескольких позиций. Это позволяет элементов принимать "большие шаги" в отношении ожидаемой позиции. Несколько переходит данные взяты с меньшими и меньшими размерами разрыва. Последний шаг Сортировка Шелла является простым рода вставки, а затем, гарантирован массива данных, которые будут почти отсортирован.
Рассмотрим небольшое значение, которое изначально хранятся в неправильном конец массива. Использование O (N) Сортировка такого рода как пузырь или вставок, это займет примерно N сравнений и обменов для перемещения этого значения весь путь в другой конец массива. Shell рода первые шаги значений с помощью гигантских размеров шагом, поэтому небольшое значение будет двигаться долгий путь к своей окончательной позиции, причем лишь несколько сравнений и обменов.
Сортировка Шелла названа в честь ее изобретателя, Дональд "Шелл", которая опубликовала в 1959 году.
Следующий метод показывает, как реализовать оболочку рода с Java:
|