Алгоритм сортировки используется во многих местах. Недавно я еще раз рассмотрел этот алгоритм и просто реализовал его сам. Запишу его здесь и сохраню некоторый материал для дальнейшего обзора.
Без лишних слов, давайте рассмотрим классические алгоритмы сортировки один за другим:
1. Выберите сортировку
Основная идея сортировки выбором заключается в том, что в процессе обхода массива, если i представляет текущий порядковый номер, который необходимо отсортировать, нужно найти минимальное значение среди оставшихся [i...n-1] , а затем указать найденное минимальное значение на i, значения обмениваются. Поскольку каждый процесс определения элементов имеет подпроцесс выбора максимального значения, люди называют это сортировкой выбора. Давайте возьмем пример:
Начальное: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
i = 0: [2, 17, 16, 16, 7, 31, 39, 32, 38, 11] (0-й [38] <-> 8-й [2])
i = 1: [2, 7, 16, 16, 17, 31, 39, 32, 38, 11] (1-й [38]<->4-й [17])
i = 2: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (2-й [11] <-> 9-й [16])
i = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] (замена не требуется)
i = 4: [2, 7, 11, 16, 16, 31, 39, 32, 38, 17] (4-й [17]<->9-й [16])
i = 5: [2, 7, 11, 16, 16, 17, 39, 32, 38, 31] (5-й [31] <-> 9-й [17])
i = 6: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (6-й [39]<->9-й [31])
i = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (замена не требуется)
i = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (замена не требуется)
i = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] (замена не требуется)
Как видно из примера, по мере продолжения сортировки выбором (постепенно увеличивается i) количество сравнений будет становиться все меньше и меньше. Однако независимо от того, упорядочен ли массив изначально или нет, сортировка выбором будет выполнять сравнение выбором. от i до конца массива. Таким образом, для массива заданной длины количество сравнений при сортировке выбором фиксировано: 1 + 2 + 3 + … + n = n * (n + 1)/2. , а количество обменов связано с порядком исходного массива. Если исходный порядок массива случайный, то в худшем случае элементы массива будут заменены n раз, а в лучшем случае это может быть 0 раз ( сам массив является последовательностью).
Можно сделать вывод, что временная и пространственная сложность сортировки выбором равны O(n2) и O(1) соответственно (сортировка выбором требует только дополнительного места для обмена элементами массива).
Код реализации:
Скопируйте код кода следующим образом:
/**
*Сортировка выбора
*/
ВЫБОР (новая сортируемая() {
public <T расширяет Comparable<T>> void sort(массив T[], логическое возрастание) {
int len = массив.длина;
for (int я = 0; я <len; я++) {
интервал выбран = я;
for (int j = i + 1; j < len; j++) {
int Compare = array[j].CompareTo(массив[выбрано]);
if (сравнить != 0 && сравнить <0 == подняться) {
выбрано = j;
}
}
обмен (массив, я, выбрано);
}
}
})
2. Сортировка вставками
Основная идея сортировки вставками заключается в том, что в процессе обхода массива, предполагая, что элементы до порядкового номера i, то есть [0..i-1], отсортированы, в этом путешествии необходимо найти правильную позицию. k элемента x, соответствующего i, и в процессе нахождения этой позиции k сравниваемые элементы один за другим перемещаются назад на одну позицию, чтобы «освободить место» для элемента x. Наконец, элементу присваивается значение, соответствующее k. x. Сортировка вставкой также называется в соответствии с характеристиками сортировки.
Ниже приведен пример: числа, отмеченные красным, являются вставленными числами. Зачеркнутые числа — это элементы, которые не участвуют в этой сортировке. один за другим, например: Во второй сортировке участвуют элементы [11, 31, 12], а элемент, который нужно вставить, — 12, но 12 в данный момент не находится в правильной позиции, поэтому нам нужно вставить его с помощью предыдущие элементы 31 и 11 по порядку. Сравнивайте, перемещайте сравниваемые элементы во время сравнения и прекращайте сравнение, когда найдете первый элемент 11, который меньше 12. В этот момент индекс 1, соответствующий 31, является позицией, в которую необходимо вставить 12.
Начальное: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
Первый проход: [11, 31, 12, 5, 34, 30, 26, 38, 36, 18] (без перемещенных элементов)
Вторая поездка: [11, 12, 31, 5, 34, 30, 26, 38, 36, 18] (31 ход назад)
Третья поездка: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (11, 12, 31 все двигаются назад)
Четвертый проход: [5, 11, 12, 31, 34, 30, 26, 38, 36, 18] (без движущихся элементов)
Пятая поездка: [5, 11, 12, 30, 31, 34, 26, 38, 36, 18] (31, 34 движется назад)
Шестая поездка: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (30, 31, 34 движется назад)
Седьмой проход: [5, 11, 12, 26, 30, 31, 34, 38, 36, 18] (без движущихся элементов)
Восьмая поездка: [5, 11, 12, 26, 30, 31, 34, 36, 38, 18] (38 ходов назад)
Девятая поездка: [5, 11, 12, 18, 26, 30, 31, 34, 36, 38] (26, 30, 31, 34, 36, 38 при движении назад)
Сортировка вставкой лучше сортировки выбором, поскольку она может использовать тот факт, что первая часть элементов массива была отсортирована в процессе сортировки, что эффективно уменьшает количество сравнений. Конечно, это преимущество зависит от начального порядка. В итоге, в плохом случае (данный массив оказывается в обратном порядке) количество сравнений и ходов, необходимых для сортировки вставками, будет равно 1 + 2 + 3... + n = n * (n). + 1) / 2. В этом крайнем случае сортировка вставками. Эффективность сортировки даже хуже сортировки выбором. Таким образом, сортировка вставкой является нестабильным методом сортировки, и эффективность вставки тесно связана с начальным порядком массива. В общем, временная и пространственная сложность сортировки вставками равны O(n2) и O(1) соответственно.
Код реализации:
Скопируйте код кода следующим образом:
/**
*Сортировка вставками
*/
ВСТАВКА (новая сортируемая() {
public <T расширяет Comparable<T>> void sort(массив T[], логическое возрастание) {
int len = массив.длина;
for (int i = 1; i <len; i++) {
Т toInsert = массив [я];
интервал j = я;
для (; j > 0; j) {
int Compare = array[j - 1].compareTo(toInsert);
if (сравнить == 0 || сравнить < 0 == подняться) {
перерыв;
}
массив[j] = массив[j - 1];
}
массив [j] = toInsert;
}
}
})
3. Пузырьковая сортировка
Пузырьковую сортировку можно считать самым классическим алгоритмом сортировки. Я помню, что с этим алгоритмом я познакомился впервые, когда учился в школе. Поскольку метод реализации самый простой, это двухуровневый цикл for In. во внутреннем цикле оценивается, находятся ли два соседних элемента в обратном порядке. Если да, то поменяйте местами два элемента и выполните один внешний цикл, чтобы «переместить» наименьший элемент среди остальных элементов массива вперед, так что это называется. пузырьковая сортировка.
Как обычно, приведем простой пример:
Исходное состояние: [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
Первое путешествие внутреннего слоя: [24, 19, 26, 39, 36, 7, 31, 29, 23, 38] (9-й [23]<->8-й [38)
Второй проход внутреннего слоя: [24, 19, 26, 39, 36, 7, 31, 23, 29, 38] (8-й [23]<->7-й [29])
Третий проход внутреннего слоя: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7-й [23]<->6-й [31])
Четвертый проход внутреннего слоя: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] (7 и 23 все в правильном порядке, замена не требуется)
Пятый трип внутреннего слоя: [24, 19, 26, 39, 7, 36, 23, 31, 29, 38] (5-й [7]<->4-й [36])
Шестое путешествие внутреннего слоя: [24, 19, 26, 7, 39, 36, 23, 31, 29, 38] (4-е [7]<->3-е [39])
Седьмой проход внутреннего слоя: [24, 19, 7, 26, 39, 36, 23, 31, 29, 38] (3-й [7]<->2-й [26])
Восьмой проход внутреннего слоя: [24, 7, 19, 26, 39, 36, 23, 31, 29, 38] (2-й [7]<->1-й [19])
Девятое путешествие внутреннего слоя: [7, 24, 19, 26, 39, 36, 23, 31, 29, 38] (1-е [7]<->0-е [24])
……….
Фактически пузырьковая сортировка аналогична сортировке выбором. Количество сравнений такое же, n * (n + 1)/2. Однако пузырьковая сортировка будет выполнять дополнительные обмены в процессе выбора минимального значения (нужна только пузырьковая сортировка). Если будет обнаружено, что порядок соседних элементов неправильный, он будет заменен. Соответственно, сортировка выбором будет решать, следует ли обмениваться по ситуации, только после завершения внутреннего цикла сравнения), так что, на мой взгляд, сортировка выбором принадлежит. для пузырьковой сортировки.
Код реализации:
Скопируйте код кода следующим образом:
/**
* Пузырьковая сортировка очень похожа на сортировку вставками.
*/
ПУЗЫРЬ(новая сортируемая() {
public <T расширяет Comparable<T>> void sort(массив T[], логическое возрастание) {
длина int = array.length;
ИНТ LastExchangedIdx = 0;
for (int я = 0; я <длина; я++) {
// отмечаем флаг, чтобы определить, произошел ли обмен с ложью
логическое значение isExchanged = ложь;
// последнее сравнение и обмен произошли до достижения индекса i
int currOrderedIdx = LastExchangedIdx > я? LastExchangedIdx: я;
for (int j = длина 1; j > currOrderedIdx; j) {
int Compare = array[j - 1].compareTo(array[j]);
if (сравнить != 0 && сравнить > 0 == подняться) {
обмен (массив, j 1, j);
isExchanged = правда;
последнийExchangedIdx = j;
}
}
// если обмен не произошел, значит массив уже в порядке
если (isExchanged == ложь) {
перерыв;
}
}
}
})
4. Сортировка холмов
Сортировка по холму возникла потому, что сортировка вставками столкнулась с проблемой перемещения слишком большого количества элементов при работе с большими массивами. Идея сортировки по Хиллу заключается в том, чтобы «разделить и властвовать» большой массив на несколько маленьких массивов, разделенных пробелами, например массив [1, 2, 3, 4, 5, 6, 7, 8 Если пробел]. = 2 для деления, его можно разделить на два массива [1, 3, 5, 7] и [2, 4, 6, 8] (соответственно, например, разрыв = 3 , то разделенные массивы будут такими: [1, 4, 7], [2, 5, 8], [3, 6]) Затем выполните сортировку вставками в разделенных массивах, а затем уменьшите их после сортировки каждого подмассива. Повторяйте предыдущие шаги до тех пор, пока пробел не станет равен 1. , то есть сортировка вставками выполняется по всему массиву. В это время массив в основном сортируется, поэтому элементы, которые необходимо переместить, будут очень маленькими, что решает проблему большего количества ходов при сортировке вставками при обработке больших объемов. масштабировать массивы.
Конкретные примеры см. в разделе «Сортировка вставками».
Сортировка Хилла — это улучшенная версия сортировки вставками. Она очень полезна для повышения эффективности при большом объеме данных. Когда объем данных небольшой, рекомендуется использовать сортировку вставкой напрямую.
Код реализации:
Скопируйте код кода следующим образом:
/**
* Сортировка ракушек
*/
SHELL(новая сортируемая() {
public <T расширяет Comparable<T>> void sort(массив T[], логическое возрастание) {
длина int = array.length;
интервал пробела = 1;
// используем ближайшую к длине / 3 позицию в качестве первого пробела
в то время как (пробел < длина / 3) {
разрыв = разрыв * 3 + 1;
}
в то время как (пробел >= 1) {
for (int i = пробел; я <длина; я++) {
Т следующий = массив [я];
интервал j = я;
while (j >= пробел) {
int Compare = array[j - пробел].compareTo(следующий);
// уже находим его позицию
if (сравнить == 0 || сравнить < 0 == подняться) {
перерыв;
}
массив[j] = массив[j - пробел];
j -= разрыв;
}
если (j != i) {
массив [j] = следующий;
}
}
разрыв /= 3;
}
}
})
5. Сортировка слиянием
Сортировка слиянием реализуется с помощью рекурсии, которая представляет собой метод «разделяй и властвуй». Целевой массив делится на две части, начиная с середины, а затем два массива сортируются отдельно. После завершения сортировки два отсортированных массива «объединяются». " в Together, самая важная вещь в сортировке слиянием - это процесс "слияния". Процесс слияния требует дополнительного пространства, соответствующего длине двух массивов, которые необходимо объединить. Например, массивы, которые необходимо указать являются: [3, 6, 8, 11] и [1, 3, 12, 15] (Хотя эти элементы логически разделены на два массива, на самом деле они все еще находятся в исходном массиве, но они разделены на два массива посредством некоторых индексов. Исходный массив Для [3, 6, 8, 11, 1, 3, 12, 15, мы устанавливаем три указателя lo, middle и high на 0, 3 и 7 соответственно. Можно добиться логического разделения на подмассивы) Тогда длина требуемого дополнительного массива составит 4+4=8. Кратко процесс объединения можно охарактеризовать следующим образом:
1) Скопируйте элементы двух подмассивов в новый массив copyArray. Взяв в качестве примера приведенный выше пример, copyArray = [3, 6, 8, 11, 1, 3, 12, 15];
2) Установите два указателя на соответствующий первый элемент в атомарном массиве соответственно. Предположим, что два указателя называются leftIdx и rightIdx, тогда leftIdx = 0 (соответствует первому элементу [3] в copyArray), rightIdx = 4 ( соответствующий пятому элементу [1] в copyArray);
3) Сравните значения элементов массива, на которые указывают leftIdx и rightIdx, выберите меньший и присвойте его значение соответствующей позиции i в исходном массиве. После завершения присваивания выполните операцию автоинкремента над элементом. два индекса, участвующих в присваивании. Если значение leftIdx или rigthIdx достигло конца соответствующего массива, остается только скопировать оставшиеся элементы массива на оставшиеся позиции по порядку.
Вот конкретный пример слияния:
Первая поездка:
Вспомогательный массив [21, 28, 39 | 35, 38] (массив разделен на два левых и правых подмассива, разделенных |)
[21, , , , ] (При первом сравнении 21 с 35 выигрывает левый подмассив, leftIdx = 0, i = 0)
Вторая поездка:
Вспомогательный массив [21, 28, 39 | 35, 38]
[21, 28, , , ] (Второй раз 28 сравнивается с 35, побеждает левый подмассив, leftIdx = 1, i = 1)
Третья поездка: [21, 28, 39 | 35, 38]
[21, 28, 35, , ] (В третий раз 39 сравнивается с 35, побеждает правый подмассив, rightIdx = 0, i = 2)
Четвертая поездка: [21, 28, 39 | 35, 38]
[21, 28, 35, 38,] (Четвертый раз сравниваются 39 и 38, побеждает правый подмассив, rightIdx = 1, i = 3)
Пятая поездка: [21, 28, 39 | 35, 38]
[21, 28, 35, 38, 39] (Правый подмассив копируется пятый раз, сравнивать leftIdx = 2, i = 4 не нужно)
Вышеупомянутый процесс слияния. Мы можем разделить весь массив, который необходимо отсортировать, ограниченное количество раз (каждый раз разделяя на две части), пока он не будет разделен на небольшой массив с длиной 1. Когда длина равна 1, массив больше не нужно сортировать. После этого эти массивы объединяются в обратном порядке (за счет рекурсии) до тех пор, пока не будет объединен последний подмассив длины n/2. После завершения слияния сортировка массива также завершается.
Сортировка слиянием требует больше всего дополнительного пространства из всех видов сортировки, и для каждого слияния требуется такое же количество элементов, как сумма длин двух массивов, участвующих в слиянии (чтобы обеспечить вспомогательный массив). Тогда можно сделать вывод, что пространственная сложность сортировки слиянием равна 1 + 2 + 4 + ... + n = n * ( n + 2)/4 (игнорируя оценку четности n). Временную сложность трудно оценить. Вот я и забыл сколько ().
Код реализации:
Скопируйте код кода следующим образом:
/**
* Сортировка слиянием
*/
ОБЪЕДИНИТЬ (новая сортируемая таблица () {
public <T расширяет Comparable<T>> void sort(массив T[], логическое возрастание) {
this.sort(массив, 0, массив.длина 1, возрастание);
}
частный <T расширяет Comparable<T>> void sort(T[] array, int lo, int hi, логическое возрастание) {
// ОПТИМИЗИРОВАТЬ ОДИН
// если длина подстроки меньше 20,
// используем сортировку вставкой, чтобы уменьшить количество рекурсивных вызовов
если (привет, ло <20) {
for (int i = lo + 1; я <= привет; я++) {
Т toInsert = массив [я];
интервал j = я;
для (; j > lo; j) {
int Compare = array[j - 1].compareTo(toInsert);
if (сравнить == 0 || сравнить < 0 == подняться) {
перерыв;
}
массив[j] = массив[j - 1];
}
массив [j] = toInsert;
}
возвращаться;
}
int Mid = lo + (привет, лоу) / 2;
сортировка (массив, вот, середина, восхождение);
sort(массив, середина + 1, привет, восхождение);
слияние (массив, вот, середина, привет, восхождение);
}
частный <T расширяет Comparable<T>> void merge(T[] array, int lo, int middle, int hi, boolean возрастание) {
// ОПТИМИЗИРОВАТЬ ДВА
// если он уже в правильном порядке, пропустите это слияние
// так как в этом нет необходимости
int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]);
if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == подъем) {
возвращаться;
}
@SuppressWarnings («не отмечено»)
T[] arrayCopy = (T[]) new Comparable[hi - lo + 1];
System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length);
интервал lowIdx = 0;
int highIdx = середина lo + 1;
for (int я = lo; я <= привет; я++) {
если (lowIdx > середина lo) {
// левый подмассив исчерпан
массив[i] = arrayCopy[highIdx++];
} else if (highIdx > привет лоу) {
// правый подмассив исчерпан
массив[i] = arrayCopy[lowIdx++];
} else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == возрастание) {
массив[i] = arrayCopy[lowIdx++];
} еще {
массив[i] = arrayCopy[highIdx++];
}
}
}
})
6. Быстрая сортировка
Быстрая сортировка также представляет собой алгоритм сортировки по принципу «разделяй и властвуй», реализованный с использованием метода слияния. Его прелесть в том, что он может определить окончательную правильную позицию сортировки для элемента массива в каждом разделе (ядро алгоритма сортировки) (один раз). Если позиционирование точное, этот элемент не будет учитываться в следующем цикле).