———— На следующий день —————
————————————
Давайте сначала рассмотримСортировка вставками:
Сортировка вставками, как следует из названия, заключается во вставке каждого элемента массива в соответствующую позицию предыдущей упорядоченной области в соответствии с соотношением размеров в процессе сортировки.
Например, элемент 3 в следующем массиве, в соответствии с отношением размера, должен быть вставлен перед тремя элементами в предыдущей упорядоченной области, а первые три элемента соответственно перемещены назад:
И так далее, сортировка вставками будет выполнять в общей сложности (длина массива-1) раундов, и результаты каждого раунда будут следующими:
Средняя временная сложность сортировки вставкамиО (п ^ 2). Этот алгоритм сортировки не сложен, но явно не является эффективным алгоритмом сортировки.
Итак, как мы можем оптимизировать алгоритм сортировки вставками? Начнем с двух особенностей сортировки вставками:
1. В случае, когда большинство элементов уже упорядочены, сортировка вставками менее трудоемка
Этот вывод очевиден, если большинство элементов массива упорядочены, то элементы в массиве, естественно, не нуждаются в частом сравнении и обмене местами.
2. В случае небольшого количества элементов нагрузка на сортировку вставками меньше
Этот вывод более очевиден: нагрузка на сортировку вставками пропорциональна квадрату n. Если n относительно мало, то нагрузка на сортировку, естественно, намного меньше.
Как предварительно обработать исходный массив? Умные ученые придумали способ группировки и сортировки, чтобы внести в массив определенные «грубые коррективы».
Так называемая группировка означает, что элементы сгруппированы попарно, а интервал между двумя элементами в одной группе составляет половину общей длины массива, то есть интервал равен 4.
Как показано на рисунке, элемент 5 сгруппирован с элементом 9, элемент 8 сгруппирован с элементом 2, элемент 6 сгруппирован с элементом 1, элемент 3 сгруппирован с элементом 7, всего 4 группы.
Затем мы позволяем каждой группе элементов сортироваться независимо, и метод сортировки может быть напрямую вставлен сортировкой. Поскольку количество элементов в каждой группе невелико, всего два, сортировка вставками работает очень мало. Отсортированный массив для каждой группы выглядит следующим образом:
Таким образом, всего после нескольких простых обменов общий порядок массива был значительно улучшен, что значительно снижает нагрузку на последующую прямую сортировку вставками. Эту практику можно понимать как «грубую настройку» исходного массива.
Но это еще не конец, мы можем еще больше сузить диапазон группировки и повторить вышеописанную работу. Уменьшите span до половины исходного, то есть span равен 2, и перегруппируйте элементы:
Как показано на рисунке, есть две группы элементов 5, 1, 9 и 6 и одна группа элементов 2, 3, 8 и 7.
Далее мы продолжаем позволять каждой группе элементов сортироваться независимо, и метод сортировки может быть напрямую вставленной сортировкой. Отсортированный массив для каждой группы выглядит следующим образом:
На этом этапе порядок массива еще более улучшается, открывая путь для последующей сортировки.
Наконец, мы дополнительно уменьшаем диапазон группировки и устанавливаем его равным 1, что эквивалентно прямой сортировке вставками. После ряда грубых корректировок рабочая нагрузка прямой сортировки вставками значительно сократилась, и результаты сортировки выглядят следующим образом:
Давайте реорганизуем весь процесс групповой сортировки:
Идея постепенной группировки для грубой настройки, подобной этой, а затем выполнения прямой сортировки вставками заключается в следующем.Сортировка холмов, по словам изобретателей алгоритма, ученых-компьютерщиковDonald Shellназванный в честь.
Шаг группировки (4, 2, 1), использованный в приведенном выше примере, называется сортировкой по холму.Инкрементный, есть много вариантов приращения, пошаговый метод деления пополам, который мы использовали в примере, является наивным методом, предложенным Дональдом Шеллом, когда он изобрел сортировку Хилла, который называетсяПриращение холма.
public static void sort(int [] array){ //希尔排序的增量 int d=array.length; while(d>1) { //使用希尔增量的方式，即每次折半 d=d/2; for(int x=0;x<d;x++) { for(int i=x+d;i<array.length;i=i+d) { int temp=array[i]; int j; for(j=i-d;j>=0&&array[j]>temp;j=j-d) { array[j+d]=array[j]; } array[j+d]=temp; } } }}public static void main(String [] args){ int[] array = {5,3,9,12,6,1,7,2,4,11,8,10}; sort(array); System.out.println(Arrays.toString(array));}Глядя на приведенный выше массив, если мы скопируем предыдущую идею группировки, будь то с шагом 4 или 2, внутри каждой группы не будет обмена элементами. Только когда мы уменьшим приращение до 1, массив будет скорректирован методом сортировки вставками.
Для такого массива сортировка Хилла не только не снижает трудоемкость прямой сортировки вставками, но и напрасно увеличивает стоимость операций группировки.
Как выбрать более эффективный пошаговый способ для сортировки Хилла?
Чтобы гарантировать отсутствие мертвой зоны в групповой грубой регулировке, приращения каждого раунда должны быть «взаимно просты» друг с другом, то есть не должно быть общего делителя, отличного от 1.
В результате один за другим было предложено множество инкрементальных методов, наиболее репрезентативным из которых являетсяИнкремент ХиббардаиСеджвик Инкремент.
HibbardПошаговая последовательность действий следующая:
1, 3, 7, 15...
Формула общего члена 2^k-1
Используя эту инкрементную сортировку Хилла, наихудшая временная сложность равнаО (п ^ (3/2))
SedgewickПошаговая последовательность действий следующая:
1, 5, 19, 41, 109......
Формула общего термина 9*4^k - 9*2^k + 1 или 4^k - 3*2^k + 1
Используя эту инкрементную сортировку Хилла, наихудшая временная сложность равнаО (п ^ (4/3))
Что касается временной сложности этих двух инкрементных методов, некоторые из них требуют очень сложных математических доказательств, а некоторые представляют собой грубые догадки людей, так что пока вам не нужно о них беспокоиться.
В приведенном выше массиве есть два элемента 5: зеленый 5 находится спереди, а оранжевый 5 — сзади.
Если мы сгруппируем по приращениям Хилла, после первого раунда грубой настройки (приращение равно 4) зеленый элемент 5 будет заменен на элемент 4 после оранжевого 5:
После второго раунда грубой настройки (с шагом 2):
Окончательный результат сортировки:
Тот же элемент 5, изменил порядок после сортировки, видно, что сортировка по Хиллу — этонестабильная сортировка.
----КОНЕЦ----
Друзья, которым понравилась эта статья, приглашаем обратить внимание на номер пабликапрограммист маленький серый, смотрите больше захватывающего контента
Добро пожаловать, нажмите и удерживайте QR-код, чтобы следоватьМаленький Грей учит английский, вы узнаете больше, чем просто английский!