Shell's Sort - очень «волшебный» алгоритм сортировки. Говорят, что это «магическое», потому что никто не может четко объяснить, чего на самом деле может достичь его производительность. Сортировка холма, потому что DL. Shell был назван в честь этого в 1959 году. Поскольку Car Hoare предложила быстрое сортировку в 1962 году, она обычно используется быстрое сортировку, потому что она проще. Тем не менее, многие математики все еще неустанно ищут лучшую сложность сортировки холмов. Как обычные программисты, мы можем изучить идеи Хилла.
Кстати, до того, как появилась Hill Sorting, в компьютерном мире было общее представление о том, что «алгоритмы сортировки не могут прорваться через O (N2)». Появление сортировки холма сломало это проклятие, и вскоре такие алгоритмы, как быстрая сортировка, были выпущены один за другим. В этом смысле холм сортировка ведет нас к новой эре.
Обзор алгоритма/идеи
Предложение сортировки холма в основном основано на следующих двух точках:
1. Алгоритм сортировки вставки может приблизительно достигать сложности O (n) и чрезвычайно эффективно, когда массив в основном упорядочен.
2. Однако сортировка вставки может перемещать данные только на один бит за раз, и производительность будет быстро ухудшаться, когда массив большой и в основном беспорядочный.
Основываясь на этом, мы можем использовать сгруппированный метод сортировки вставки, который является конкретным методом: (в качестве примера взять массив из 16 элементов)
1. Выберите дельту приращения, которая больше 1, и выберите Subarray из массива с помощью этого приращения для прямой сортировки вставки. Например, если приращение 5, выбран 5, элементы с подписками 0, 5, 10, 15 отсортированы.
2. Держите дельту приращения и переместите первый элемент в свою очередь для введения и сортировки, пока раунд не будет завершен. Для примера выше, массивы [1, 6, 11], [2, 7, 12], [3, 8, 13], [4, 9, 14] сортируются по очереди.
3. Уменьшите приращение и непрерывно повторяйте вышеуказанный процесс, пока приращение не уменьшится до 1. Очевидно, что последний раз - это прямая сортировка вставки.
4. Сортировка завершена.
Как видно из вышеперечисленного, приращение постоянно уменьшается, поэтому сортировка холма снова называется «снижение сортировки приращения».
Реализация кода
сортировка пакетов; открытый класс ShellSortTest {public static int count = 0; public static void main (string [] args) {int [] data = new int [] {5, 3, 6, 2, 1, 9, 4, 8, 7}; print (data); ShellSort (данные); print (data); } public static void shellsort (int [] data) {// Рассчитайте максимальное значение h int h = 1; while (h <= data.length / 3) {h = h * 3 + 1; } while (h> 0) {for (int i = h; i <data.length; i += h) {if (data [i] <data [i - h]) {int tmp = data [i]; int j = i - h; while (j> = 0 && data [j]> tmp) {data [j + h] = data [j]; j -= h; } data [j + h] = tmp; print (data); }} // Вычислять следующее значение h h = (h - 1) / 3; }} public static void print (int [] data) {for (int i = 0; i <data.length; i ++) {System.out.print (data [i]+"/t"); } System.out.println (); }} Результаты работы:
5 3 6 2 1 9 4 8 7 7 1 3 6 2 5 9 4 8 7 1 2 3 6 5 9 4 8 7 1 2 3 5 6 9 4 8 7 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 8 9
Производительность алгоритма/сложность
Последовательные последовательности, сортируемые Hill, могут быть взяты в любое время, и единственное требование состоит в том, что последнее должно быть 1 (потому что необходимо убедиться, что он упорядочен 1). Однако различный выбор последовательности окажет огромное влияние на производительность алгоритма. Приведенный выше код демонстрирует два приращения.
Помните: лучше не иметь общих факторов, отличных от 1 на каждые два элемента в последовательности последовательности! (Очевидно, сортировка по 2 в последовательности не очень значима).
Ниже приведены некоторые общие последовательности.
Первым приращением является первоначально предложенный Дональдом Шелл, то есть, сгиба уменьшается до 1. Согласно исследованию, используя приращения холмов, сложности времени все еще остается O (N2).
Второй приращение Hibbard: {1, 3, ..., 2^k-1}. Временная сложность этой последовательности последовательно составляет приблизительно O (n^1,5).
Третий приращение Sedgewick Incred: (1, 5, 19, 41, 109, ...), которая генерирует последовательность либо 9*4^i - 9*2^i + 1 или 4^i - 3*2^i + 1.
Стабильность алгоритма
Мы все знаем, что сортировка вставки является стабильным алгоритмом. Тем не менее, сортировка оболочки - это процесс множества вставки. В одной вставке мы можем убедиться, что порядок одних и тех же элементов не был перемещен, но во многих вставках вполне возможно, что одни и те же элементы перемещаются в разных раундах вставки, и стабильность окончательно разрушается. Следовательно, сортировка оболочки не является стабильным алгоритмом.
Алгоритм применимых сценариев
Несмотря на то, что сортировка оболочки быстрая, в конце концов, она сортирует вставку, а порядок ее величины не так хорош, как восходящая звезда - быстрая сортировка O (NN) быстрая. Сортировка оболочки не является хорошим алгоритмом перед лицом большого количества данных. Тем не менее, вполне возможно использовать малые и средние данные.