Сейчас читаю , я изучил множество часто используемых алгоритмов сортировки, поэтому я написал заметку для чтения, чтобы записать идеи и реализацию этих алгоритмов сортировки.
Пузырьковая сортировка
Пузырьковая сортировка — это очень простой первичный алгоритм сортировки.Он каждый раз сравнивает два соседних элемента, и если порядок неправильный, они меняются местами.Поскольку наименьший элемент медленно всплывает вверх посредством непрерывного обмена, такая сортировка называется пузырьковой сортировкой.
Для пузырьковой сортировки требуется n элементовO(n^2)количество сравнений, поэтому сортировать большие массивы неэффективно.
рабочий процесс
- Сравнивает два соседних элемента, и если второй элемент меньше первого, меняет его местами (и наоборот по убыванию).
- Сделайте то же самое для каждой пары соседних элементов, начиная с первой пары до последней пары, Когда это будет сделано, последний элемент будет самым большим.
- Повторите вышеуказанные шаги для всех элементов, кроме последнего элемента.
- Продолжайте повторять вышеуказанные шаги с каждым разом все меньше и меньше элементов, пока весь массив не будет отсортирован (т. е. нет необходимости сравнивать пары элементов).
Код
// less与exch函数见完整代码
public static void sort(Comparable[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (less(a[j + 1], a[j])) {
exch(a, j, j + 1);
}
}
}
}
полный код
/**
* Bubble Sort
*
* @author SylvanasSun
*
*/
public class Bubble {
// This class should not be instantiated.
private Bubble() {
}
/**
* Rearranges the array in ascending order, using the natural order.
*
* @param a
* a the array to be sorted
*/
public static void sort(Comparable[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (less(a[j + 1], a[j])) {
exch(a, j, j + 1);
}
}
}
}
/**
* Rearranges the array in ascending order, using a comparator.
*
* @param a
* a the arry to be sorted
* @param comparator
* comparator the comparator specifying the order
*/
public static void sort(Object[] a, Comparator comparator) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (less(comparator, a[j + 1], a[j])) {
exch(a, j, j + 1);
}
}
}
}
// a < b ?
private static boolean less(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
// a < b ?
private static boolean less(Comparator comparator, Object a, Object b) {
return comparator.compare(a, b) < 0;
}
// exchange a[i] and a[j]
private static void exch(Object[] a, int i, int j) {
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// print array elements to console
public static void print(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
System.out.print(a[i] + " ");
}
}
// test
public static void main(String[] args) {
String[] s = new Scanner(System.in).nextLine().split("\\s+");
Bubble.sort(s);
Bubble.print(s);
}
}
Выберите сортировку
Сортировка выбором также является очень простым и интуитивно понятным алгоритмом первичной сортировки. Идея постоянно выбирается среди наименьших оставшихся элементов.
Он имеет следующие две характеристики.
- Время выполнения не зависит от входной моделиПри сортировке выбором однократное сканирование массива для поиска наименьшего элемента не дает много информации для следующего сканирования, даже если входные данные представляют собой уже упорядоченный массив или массив со всеми одинаковыми первичными ключами и массив со случайно расположенными и неупорядоченными элементами. время сортировки используется то же самое.
- Движение данных минимальноЕсли элемент находится в правильном положении, он не будет перемещен.Каждый раз, когда сортировка выбором меняет местами пару элементов, по крайней мере один из них будет перемещен в его конечную позицию, поэтому сортировка таблицы из n элементов в сумме делает не более n-1 свопов.
рабочий процесс
- Сначала найдите наименьший элемент в массиве
- Во-вторых, поменяйте его местами с первым элементом массива (если первый элемент является наименьшим элементом, он заменяется сам собой)
- Снова находим наименьший элемент среди оставшихся элементов, меняем его местами со вторым элементом массива и так далее, пока весь массив не будет отсортирован.
Код
public static void sort(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
int min = i; // the smallest element index
for (int j = i + 1; j < a.length; j++) {
if (less(a[j], a[min]))
min = j;
exch(a, i, min);
}
}
}
Сортировка вставками
Сортировка вставками аналогична сортировке выбором, все элементы слева от текущего индекса упорядочены, но их конечное положение не определено, она строит упорядоченную последовательность, для несортированных элементов, в упорядоченной последовательности от последнего сканирования вперед, найти соответствующее положение и вставьте.
Время, необходимое для сортировки вставками, зависит от начального порядка элементов во входной модели.Сортировка вставками намного эффективнее, когда входная модель представляет собой частично отсортированный массив.
Итак, сортировка вставками предназначена дляЧастично упорядоченный массивОчень эффективен и подходит для небольших массивов.
рабочий процесс
- Начиная с первого элемента, который можно считать упорядоченным
- Возьмите следующий элемент и просканируйте его сзади наперед в упорядоченной последовательности.
- Если элемент (отсортированный) больше нового элемента, переместите элемент в следующую позицию (сдвиг вправо)
- Повторяйте шаг 3, пока не найдете позицию, в которой отсортированный элемент меньше или равен новому элементу.
- После вставки нового элемента в эту позицию
- Повторите шаги 2–5.
Код
public static void sort(Comparable[] a) {
for (int i = 0; i < a.length; i++) {
// a[i] insert to a[i-1]、a[i-2]、a[i-3]...
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
оптимизация
Есть еще много мест, где можно оптимизировать сортировку вставками, вот два примера.
- Метод бинарного поиска используется для уменьшения количества операций сравнения.
public static void sort(Comparable[] a) { int length = a.length; for (int i = 1; i < length; i++) { // binary search to determine index j at which to insert a[i] Comparable v = a[i]; int lo = 0, hi = i; while (lo < hi) { int mid = lo + (hi - lo) / 2; if (less(v, a[mid])) hi = mid; else lo = mid + 1; } // insertion sort with "half exchanges" // (insert a[i] at index j and shift a[j], ..., a[i-1] to right) for (int j = i; j > lo; --j) a[j] = a[j - 1]; a[lo] = v; } }
- Сдвигайте большие элементы вправо во внутреннем цикле вместо того, чтобы всегда менять местами два элемента (количество обращений к массиву можно уменьшить вдвое)
public static void sort(Comparable[] a) { int length = a.length; // put smallest element in position to serve as sentinel int exchanges = 0; for (int i = length - 1; i > 0; i--) { if (less(a[i], a[i - 1])) { exch(a, i, i - 1); exchanges++; } } if (exchanges == 0) return; // insertion sort with half-exchanges for (int i = 2; i < length; i++) { Comparable v = a[i]; int j = i; while (less(v, a[j - 1])) { a[j] = a[j - 1]; j--; } a[j] = v; } }
Сортировка холмов
Hill Worth, также известный какАлгоритм сортировки по убыванию, которая является более эффективной и улучшенной версией, основанной на сортировке вставками.
Поскольку сортировка вставками неэффективна для больших неупорядоченных массивов, поскольку она только меняет местами соседние элементы, элементы могут перемещаться только побитно с одного конца массива на другой.
А сортировка по Хиллу просто улучшает сортировку вставками для ускорения.поменять местами несмежные элементыЛокальный массив для сортировки, сортировки вставками и конечнойместный заказСортировка массива.
Идея сортировки Хилла заключается в том,Сделать любой элемент массива на интервале h упорядоченным, можно сказать, что h упорядоченный массив — это массив, состоящий из h взаимно независимых упорядоченных массивов, сплетенных вместе.
Код
public static void sort(Comparable[] a) {
int h = 1;
while (h < a.length / 3) {
// h sequence 1,4,13,40,121,364,1093,...
h = h * 3 + 1;
}
while (h >= 1) {
for (int i = h; i < a.length; i++) {
// a[i] insert to a[i-h],a[i-2*h],a[i-3*h]...
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a, j, j - h);
}
}
h = h / 3;
}
}
Сортировка слиянием
Сортировка слиянием — типичное применение алгоритма «разделяй и властвуй».Объединить два отсортированных массива в более крупный отсортированный массив.
У него есть главный недостаток, заключающийся в том, что он требует дополнительного пространства (вспомогательного массива), а требуемое дополнительное пространство пропорционально N.
Процесс слияния
- Подать заявку на пространство, чтобы его размер был суммой двух упорядоченных последовательностей, и это пространство использовалось для хранения объединенной последовательности.
- Объявите два указателя, начальные позиции являются начальными позициями двух упорядоченных последовательностей.
- Сравните элементы, на которые указывают два указателя, выберите относительно небольшой элемент в пространстве слияния и переместите указатель в следующую позицию.
- Повторяйте шаг 3, пока указатель не достигнет конца последовательности.
- Помещает все оставшиеся элементы другой последовательности непосредственно в конец объединенной последовательности.
сортировка слиянием сверху вниз
Сверху вниз — это рекурсивное решение задачи сверху вниз.
Например: чтобы отсортировать массив a[lo..hi], его нужно разделить на две части: a[lo..mid] и a[mid+1..hi],Сортировать их индивидуально по рекурсивным вызовам,НаконецОбъединить отсортированные подмассивы в окончательный отсортированный результат.
// stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
// copy a[] to aux[]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// merge back to a[]
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = aux[j++];
} else if (j > hi) {
a[k] = aux[i++];
} else if (less(aux[j], aux[i])) {
a[k] = aux[j++];
} else {
a[k] = aux[i++];
}
}
}
// mergesort a[lo..hi] using auxiliary array aux[lo..hi]
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
сортировка слиянием снизу вверх
«Снизу-вверх» — это пошаговый подход к решению проблемы.
Идея состоит в том, чтобы сначала объединить эти крошечные массивы, а затем объединить полученные подмассивы попарно, пока весь массив не будет объединен вместе.
Вы можете выполнить слияние два на два (каждый элемент представляется как массив размера 1), затем слияние четыре-четыре (объединить два массива размера 2 в массив с четырьмя элементами), а затем восемь-восемь слияние .....(и т. д.) В каждом раунде слияний второй подмассив последнего слияния может быть меньше первого подмассива, в противном случае два массива должны быть одинакового размера во всех слияниях.
//merge函数与自顶向下中的一致
public static void sort(Comparable[] a) {
int N = a.length;
Comparable[] aux = new Comparable[N];
for (int len = 1; len < N; len *= 2) {
for (int lo = 0; lo < N - len; lo += len + len) {
int mid = lo + len - 1;
int hi = Math.min(lo + len + len - 1, N - 1);
merge(a, aux, lo, mid, hi);
}
}
}
оптимизация
-
Если массив небольшой, частые рекурсивные вызовы будут неэффективны, поэтому вы можете использовать сортировку вставками (или сортировку выбором и т. д.) для обработки небольших подмассивов.
private static void merge(Comparable[] src, Comparable[] dst, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k <= hi; k++) { if (i > mid) { dst[k] = src[j++]; } else if (j > hi) { dst[k] = src[i++]; } else if (less(src[j], src[i])) { dst[k] = src[j++]; } else { dst[k] = src[i++]; } } } private static void sort(Comparable[] src, Comparable[] dst, int lo, int hi) { // if (hi <= lo) return; if (hi <= lo + CUTOFF) { insertionSort(dst, lo, hi); return; } int mid = lo + (hi - lo) / 2; sort(dst, src, lo, mid); sort(dst, src, mid + 1, hi); // using System.arraycopy() is a bit faster than the above loop if (!less(src[mid + 1], src[mid])) { System.arraycopy(src, lo, dst, lo, hi - lo + 1); return; } merge(src, dst, lo, mid, hi); } // using insertion sort handle small array private static void insertionSort(Comparable[] a, int lo, int hi) { for (int i = lo; i <= hi; i++) { for (int j = i; j > lo && less(a[j], a[j - 1]); j--) { exch(a, j, j - 1); } } } public static void sort(Comparable[] a) { Comparable[] aux = a.clone(); sort(aux, a, 0, a.length - 1); }
быстрая сортировка
быстрая сортировка划分交换排序, который также является алгоритмом сортировки по принципу «разделяй и властвуй».
Быстрая сортировка имеет потенциальный недостаток, т.Когда сплит не сбалансированЭта процедура может быть крайне неэффективной, поэтому необходимоПроизвольная сортировка массива перед быстрой сортировкойчтобы избежать этой ситуации.
Он разбивает массив на два подмассива и сортирует две части независимо.От сортировки слиянием он отличается тем, что:
- Сортировка слиянием делит массив на два подмассива и сортирует их по отдельности, и, наконец, объединяет отсортированные подмассивы, чтобы отсортировать весь массив.
- Быстрая сортировка сортирует массив, когдаКогда оба подмассива упорядочены, весь массив упорядочен.
- При сортировке слиянием рекурсивные вызовы обрабатывают весь массив.До; в то время как в быстрой сортировке рекурсивный вызов обрабатывает весь массивпосле.
- При сортировке слиянием массив сортируется поРазделить пополам, в то время как в быстрой сортировке,Расположение разделения зависит от содержимого массива.
рабочий процесс
- Выберите один из массива
基准, который может быть a[lo] , который является элементом, идентифицированным как запланированный.
- Сканируйте вправо, начиная с левого конца массива (левый указатель), пока не найдете массив, больший или равный
基准Элементы.
- Сканировать влево, начиная с правого конца массива (правый указатель), пока он не найдет значение, не находящееся или равно
基准Элементы.
- Эти два элемента не планируются, и их позиции меняются местами (чтобы гарантировать, что левый элемент левого указателя i не больше, чем
基准, правый элемент правого указателя j не меньше基准).
- , Когда два указателя встречаются,
基准Поменять местами крайний правый элемент (a[j]) левого подмассива и вернуть j.
Код
// partition the subarray a[lo..hi] so that a[lo..j-1] <= a[j] <= a[j+1..hi]
// and return the index j.
private static int partition(Comparable[] a, int lo, int hi) {
int i = lo; // left point
int j = hi + 1; // right point
Comparable v = a[lo]; // partition element
while (true) {
// scan left point
while (less(a[++i], v)) {
if (i == hi)
break;
}
// scan right point
while (less(v, a[--j])) {
if (j == lo)
break;
}
// check if point cross
if (i >= j)
break;
exch(a, i, j);
}
// put partition element v to a[j]
exch(a, lo, j);
// now a[lo..j-1] <= a[j] <= a[j+1..hi]
return j;
}
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
int j = partition(a, lo, hi);
sort(a, lo, j - 1);
sort(a, j + 1, hi);
}
public static void sort(Comparable[] a) {
shuffle(a);
sort(a, 0, a.length - 1);
}
// random sort an array
private static void shuffle(Object[] a) {
if (a == null)
throw new IllegalArgumentException("array is null.");
Random random = new Random();
int N = a.length;
for (int i = 0; i < N; i++) {
int j = i + random.nextInt(N - i);
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
Быстрая сортировка с разделением на три части
При наличии большого количества повторяющихся элементов рекурсивный характер быстрой сортировки приведет к частому появлению подмассивов со всеми повторяющимися элементами, что имеет большой потенциал для улучшения, повышая производительность текущей быстрой сортировки с линейно-логарифмического уровня на линейный уровень.
Простая идеяРазделите массив на три части, соответствующие элементам массива меньше, равно и больше элемента разделения соответственно.
В реализации поддерживать левый указательltсделатьa[lo..lt-1]элементов меньше, чем基准, правый указательgtсделатьa[gt+1..hi]элементы в больше, чем基准, указательiсделатьa[lt..i-1]Элементы равны基准,a[i..gt]Элементы еще не определены.
-
a[i]меньше, чем基准,будетa[lt]иa[i]Поменять местами,lt++&i++.
-
a[i]больше, чем基准,будетa[gt]иa[i]обмен, gt–.
-
a[i]равный基准,i++.
Вышеуказанные операции гарантируют, что элементы массива останутся неизменными и сократятся.gt-i(поэтому цикл завершится.) Если он не равен разделяемому элементу, все остальные элементы будут заменены местами.
// quicksort the subarray a[lo .. hi] using 3-way partitioning
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo)
return;
int lt = lo, i = lo + 1, gt = hi;
Comparable v = a[lo]; // partition element
// a[lo..lt-1] < a[lt..gt] < a[gt+1..hi]
while (i <= gt) {
int cmp = a[i].compareTo(v);
if (cmp < 0) {
exch(a, i++, lt++);
} else if (cmp > 0) {
exch(a, i, gt--);
} else {
i++;
}
}
sort(a, lo, lt - 1);
sort(a, gt + 1, hi);
}
сортировка кучей
Heapsort — это алгоритм сортировки, реализованный в очереди с приоритетом на основе кучи.
приоритетная очередь
Приоритетная очередь — это поддержкаудалить самый большой (самый маленький) элементивставить элементСтруктура данных упорядочивается внутри, и любую приоритетную очередь можно превратить в метод сортировки.
куча
Куча — это структура данных, которую часто можно рассматривать как деревомножествоОбъект.Корневой узел как максимальное число называетсямаксимальная куча, наоборот, корневой узел как наименьшее число называетсямин куча.
куча - этоПриблизительное полное бинарное деревоСтруктура , и в то же время удовлетворяют свойствам кучи:Гарантируется, что каждый элемент больше (меньше) равен элементу его дочерних узлов..
В куче по позиции индекса корневого узла алгоритм вычисления положения родительского узла и дочернего узла также отличается.
- Когда начальная позиция массива равна 0, родительский узел узла в позиции k
(k - 1)/2, его два дочерних узла2k+1,2k+2.
- Когда начальная позиция массива равна 1 (то есть индекс 0 не используется), родительский узел узла в позиции k
k/2, его два дочерних узла2k,2k+1.
чтобы убедиться, чтокуча упорядочена, необходимо поддерживать две операции дляРазбейте состояние кучи, затем пройдитесь по куче и восстановите состояние кучи по мере необходимости., этот процесс называетсяпорядок в куче.
-
Порядок кучи снизу вверх (плавающий вверх): если упорядоченное состояние кучи нарушено из-за того, что узел становится больше своего родителя, то куча должна быть восстановлена путем замены ее и его родителя местами, перемещая узел до тех пор, пока он не столкнется с более крупным родительским узлом (если это так). мин куча, логика сравнения обратная).
// 在本文中,均不使用数组的0索引 private void swim(int k) { while (k > 1 && less(k/2, k)) { exch(a,k, k/2); k = k/2; } }
-
Упорядочивание кучи сверху вниз (погружение): если упорядоченное состояние кучи нарушено из-за того, что узел становится меньше, чем один или оба из его двух дочерних элементов, это необходимо исправить, заменив его на больший из двух его дочерних элементов. Куча, перемещайте этот узел вниз, пока его дочерние элементы не станут меньше. чем это или достичь дна кучи.(если это мин куча, то логичная идея сравнения)
// n为数组长度 private void sink(int k) { while (2*k <= n) { int j = 2*k; if (j < n && less(j, j+1)) j++; if (!less(a[k],a[j])) break; exch(a,k, j); k = j; } }
рабочий процесс
Кучевую сортировку можно разделить на два этапа.
- Этап построения кучи, который реорганизует исходный массив в кучу.. Используйте функцию sink() справа налево, чтобы построить подкучу. Каждая позиция массива уже является корневым узлом подкучи. Нужно сканировать только половину элементов в массиве, потому что мы можем пропустить подкучу размера 1. Наконец, функция приемника () вызывается в позиции 1, чтобы завершить сканирование.
- Стадия сортировки стока, взять все элементы из кучи в порядке убывания и получить отсортированный результат.Удалите самый большой элемент в куче и поместите его на освободившуюся позицию в массиве после того, как куча сожмется.
Код
public static void sort(Comparable[] a) {
int N = a.length;
// construction max heap
for (int k = N / 2; k >= 1; k--) {
sink(a, k, N);
}
// sink sort
while (N > 1) {
// the biggest element (root) swap smallest element then heap shrink
exch(a, 1, N--);
// new root element sink
sink(a, 1, N);
}
}
private static void sink(Comparable[] pq, int k, int n) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && less(pq, j, j + 1))
j++;
if (!less(pq, k, j))
break;
exch(pq, k, j);
k = j;
}
}
private static boolean less(Comparable[] pq, int i, int j) {
return pq[i - 1].compareTo(pq[j - 1]) < 0;
}
private static void exch(Object[] pq, int i, int j) {
Object swap = pq[i - 1];
pq[i - 1] = pq[j - 1];
pq[j - 1] = swap;
}
Суммировать
| название | Это стабильно | Сортировать ли на месте | временная сложность | космическая сложность | Примечание |
|---|---|---|---|---|---|
| Пузырьковая сортировка | да | да | O(N^2) | O(1) | (неупорядоченная область, упорядоченная область). Найдите самый большой элемент из неупорядоченной области путем замены местами и поместите его впереди упорядоченной области. |
| сортировка выбором | нет | да | O(N^2) | O(1) | (упорядоченная область, неупорядоченная область). Найдите наименьший элемент в неупорядоченной области, чтобы следовать за упорядоченной областью. Для массивов: больше сравнивайте, меньше обменивайте. |
| Сортировка вставками | да | да | между N и N^2 | O(1) | (упорядоченная область, неупорядоченная область). Вставьте первый элемент неупорядоченной области в соответствующую позицию в упорядоченной области. Для массивов: меньше сравнивайте, больше меняйте. |
| Сортировка холмов | нет | да | O(N log^2 N) | O(1) | Каждый раунд выполняет сортировку вставками с заданным интервалом, и интервал будет уменьшаться в свою очередь, а последний раз должен быть равен 1. |
| быстрая сортировка | нет | да | O(N log N) | O(logN) | (десятичный, базовый элемент, большое число). Произвольно выберите элемент в интервале в качестве эталона, поместите элементы меньше эталона перед эталоном и поместите элементы больше эталона после эталона, а затем отсортируйте десятичную область и область больших чисел соответственно. |
| Трехсторонняя QuickSort | нет | да | между N и NlogN | O(logN) | Он более эффективен для входных данных с большим количеством повторяющихся элементов. |
| Сортировка слиянием | да | нет | O(N log N) | O(N) | Разделите данные на два сегмента и выберите наименьшие элементы из двух сегментов один за другим и переместите их в конец нового сегмента данных. |
| сортировка кучей | нет | да | O(N log N) | O(1) | (максимальная куча, упорядоченная область). Корень выгружается из вершины кучи и помещается в упорядоченную область перед восстановлением кучи. |
В большинстве практических случаев лучше всего подходит быстрая сортировка. Если важна стабильность и нет проблем с объемом, сортировка слиянием, вероятно, является лучшей.
В JDK Arrays.sort() использует разные алгоритмы сортировки в соответствии с разными типами параметров.Если это примитивный тип данных, он использует быструю сортировку с разделением по трем направлениям, а для ссылочного типа — сортировку слиянием.
end
- Author : SylvanasSun
- Email : sylvanassun_xtz@163.com