Алгоритмы сортировки в Java

Введение Сортировка данных означает их упорядочение в определенном порядке, часто в виде структуры данных, подобной массиву. Вы можете использовать различные критерии упорядочения, распространенными из которых являются сортировка чисел от наименьшего к наибольшему или наоборот, либо лексикографическая сортировка строк [https://en.wikipedia.org/wiki/Lexicographic_order]. Вы даже можете определить свои собственные критерии, и мы рассмотрим практические способы сделать это к концу этой статьи. Если вам интересно, как работает сортировка, мы рассмотрим различные алгоритмы, fr

Вступление

Сортировка данных означает их упорядочение в определенном порядке, часто в виде структуры данных, подобной массиву. Вы можете использовать различные критерии упорядочения, распространенными из которых являются сортировка чисел от наименьшего к наибольшему или наоборот, или лексикографическая сортировка строк. Вы даже можете определить свои собственные критерии, и мы рассмотрим практические способы сделать это к концу этой статьи.

Если вам интересно, как работает сортировка, мы рассмотрим различные алгоритмы, от неэффективных, но интуитивно понятных решений, до эффективных алгоритмов, которые фактически реализованы на Java и других языках.

Существуют различные алгоритмы сортировки, и не все они одинаково эффективны. Мы проанализируем их временную сложность , чтобы сравнить их и посмотреть, какие из них работают лучше всего.

Список алгоритмов, которые вы здесь изучите, ни в коем случае не является исчерпывающим, но мы собрали некоторые из наиболее распространенных и наиболее эффективных, чтобы помочь вам начать работу:

Примечание . В этой статье не рассматривается параллельная сортировка, поскольку она предназначена для начинающих.

Пузырьковая сортировка

Объяснение

Пузырьковая сортировка работает, меняя местами соседние элементы, если они находятся не в желаемом порядке. Этот процесс повторяется с начала массива, пока все элементы не будут в порядке.

Мы знаем, что все элементы в порядке, когда нам удается выполнить всю итерацию без замены мест вообще - тогда все элементы, которые мы сравнивали, были в желаемом порядке со своими соседними элементами, и, соответственно, со всем массивом.

Вот шаги для сортировки массива чисел от наименьшего к наибольшему:

  • 4 2 1 5 3: Первые два элемента расположены в неправильном порядке, поэтому мы меняем их местами.

  • 2 4 1 5 3: вторые два элемента тоже находятся в неправильном порядке, поэтому мы меняем местами.

  • 2 1 4 5 3: Эти два расположены в правильном порядке, 4 <5, поэтому мы оставим их в покое.

  • 2 1 4 5 3 : Другой обмен.

  • 2 1 4 3 5: Вот результирующий массив после одной итерации.

Поскольку во время первого прохода произошел по крайней мере один обмен (на самом деле их было три), нам нужно снова пройти через весь массив и повторить тот же процесс.

Повторяя этот процесс, пока не перестанут делать свопы, мы получим отсортированный массив.

Причина, по которой этот алгоритм называется пузырьковой сортировкой, заключается в том, что числа как бы «всплывают» на «поверхность». Если вы еще раз просмотрите наш пример, следуя определенному числу (4 - отличный пример), вы увидите, что оно медленно перемещается вправо во время процесса.

Все числа постепенно перемещаются на свои места слева направо, как пузыри, медленно поднимающиеся из водоема.

Если вы хотите прочитать подробную статью о пузырьковой сортировке , мы вам поможем!

Выполнение

Мы собираемся реализовать пузырьковую сортировку так же, как мы изложили это на словах. Наша функция входит в цикл while, в котором она выполняет замену всего массива по мере необходимости.

Мы предполагаем, что массив отсортирован, но если мы ошиблись при сортировке (если произошла подкачка), мы проходим еще одну итерацию. Затем цикл while продолжается до тех пор, пока нам не удастся пройти через весь массив без подкачки:

 public static void bubbleSort(int[] a) { 
 boolean sorted = false; 
 int temp; 
 while(!sorted) { 
 sorted = true; 
 for (int i = 0; i < array.length - 1; i++) { 
 if (a[i] > a[i+1]) { 
 temp = a[i]; 
 a[i] = a[i+1]; 
 a[i+1] = temp; 
 sorted = false; 
 } 
 } 
 } 
 }

При использовании этого алгоритма мы должны быть осторожны при формулировании условий обмена.

Например, если бы я использовал a[i] >= a[i+1] это могло бы закончиться бесконечным циклом, потому что для равных элементов это отношение всегда было бы true и, следовательно, всегда меняло их местами.

Сложность времени

Чтобы выяснить временную сложность пузырьковой сортировки, нам нужно рассмотреть наихудший из возможных сценариев. Какое максимальное количество раз нам нужно пройти через весь массив, прежде чем мы его отсортируем? Рассмотрим следующий пример:

 5 4 3 2 1

В первой итерации 5 будет «всплывать на поверхность», но остальные элементы останутся в порядке убывания. Нам нужно будет сделать одну итерацию для каждого элемента, кроме 1, а затем еще одну итерацию, чтобы проверить, что все в порядке, так что всего 5 итераций.

Расширьте это до любого массива из n элементов, и это означает, что вам нужно сделать n итераций. Глядя на код, это будет означать, что наш в while цикл может работать максимум n раз.

Каждый из этих n раз мы перебираем весь массив (цикл for в коде), что означает, что в худшем случае временная сложность будет O (n ^ 2) .

Примечание . Временная сложность всегда была бы O (n ^ 2), если бы не sorted логическая проверка, которая завершает алгоритм, если во внутреннем цикле нет свопов, что означает, что массив отсортирован.

Сортировка вставкой

Объяснение

Идея сортировки вставкой состоит в разделении массива на отсортированные и несортированные подмассивы.

Отсортированная часть имеет длину 1 в начале и соответствует первому (самому левому) элементу в массиве. Мы перебираем массив и на каждой итерации расширяем отсортированную часть массива на один элемент.

При расширении мы помещаем новый элемент на свое место в отсортированном подмассиве. Мы делаем это, сдвигая все элементы вправо, пока не встретим первый элемент, который нам не нужно сдвигать.

Например, если в следующем массиве выделенная жирным шрифтом часть отсортирована в порядке возрастания, произойдет следующее:

  • 3 5 7 8 4 2 1 9 6: Берем 4 и запоминаем, что это то, что нам нужно вставить. Поскольку 8> 4, мы сдвигаемся.

  • 3 5 7 x 8 2 1 9 6: где значение x не имеет решающего значения, поскольку оно будет немедленно перезаписано (либо на 4, если это подходящее место, либо на 7, если мы переместим). Поскольку 7> 4, мы сдвигаемся.

  • 3 5 х 7 8 2 1 9 6

  • 3 х 5 7 8 2 1 9 6

  • 3 4 5 7 8 2 1 9 6

После этого процесса отсортированная часть была расширена на один элемент, теперь у нас есть пять, а не четыре элемента. Каждая итерация делает это, и к концу у нас будет отсортирован весь массив.

Если вы хотите прочитать подробную статью о сортировке вставкой , мы вам поможем!

Выполнение

 public static void insertionSort(int[] array) { 
 for (int i = 1; i < array.length; i++) { 
 int current = array[i]; 
 int j = i - 1; 
 while(j >= 0 && current < array[j]) { 
 array[j+1] = array[j]; 
 j--; 
 } 
 // at this point we've exited, so j is either -1 
 // or it's at the first element where current >= a[j] 
 array[j+1] = current; 
 } 
 }

Сложность времени

Опять же, мы должны рассмотреть наихудший сценарий для нашего алгоритма, и это снова будет пример, когда весь массив убывает.

Это связано с тем, что на каждой итерации нам придется перемещать весь отсортированный список на единицу, что составляет O (n) . Мы должны сделать это для каждого элемента в каждом массиве, что означает, что он будет ограничен O (n ^ 2) .

Выбор Сортировка

Объяснение

Selection Sort также делит массив на отсортированный и несортированный подмассив. Хотя на этот раз отсортированный подмассив формируется путем вставки минимального элемента несортированного подмассива в конец отсортированного массива путем замены местами:

  • 3 5 1 2 4

  • 1 5 3 2 4

  • 1 2 3 5 4

  • 1 2 3 5 4

  • 1 2 3 4 5

  • 1 2 3 4 5

Выполнение

На каждой итерации мы предполагаем, что первый несортированный элемент является минимальным, и перебираем остальные, чтобы увидеть, есть ли элемент меньшего размера.

Как только мы находим текущий минимум неотсортированной части массива, мы меняем его местами с первым элементом и считаем его частью отсортированного массива:

 public static void selectionSort(int[] array) { 
 for (int i = 0; i < array.length; i++) { 
 int min = array[i]; 
 int minId = i; 
 for (int j = i+1; j < array.length; j++) { 
 if (array[j] < min) { 
 min = array[j]; 
 minId = j; 
 } 
 } 
 // swapping 
 int temp = array[i]; 
 array[i] = min; 
 array[minId] = temp; 
 } 
 }

Сложность времени

Нахождение минимума - это O (n) для длины массива, потому что мы должны проверить все элементы. Мы должны найти минимум для каждого элемента массива, сделав весь процесс ограниченным O (n ^ 2) .

Сортировка слиянием

Объяснение

Сортировка слиянием использует рекурсию для решения проблемы сортировки более эффективно, чем ранее представленные алгоритмы, и, в частности, использует подход «разделяй и властвуй».

Используя обе эти концепции, мы разделим весь массив на два подмассива, а затем:

  1. Сортировать левую половину массива (рекурсивно)
  2. Сортировать правую половину массива (рекурсивно)
  3. Объедините решения

Иллюстрация сортировкислиянием{.ezlazyload}

Это дерево предназначено для представления того, как работают рекурсивные вызовы. Массивы, отмеченные стрелкой вниз, - это те, для которых мы вызываем функцию, в то время как мы объединяем массивы со стрелкой вверх, возвращаясь вверх. Итак, вы следуете за стрелкой вниз до нижней части дерева, а затем снова поднимаетесь и объединяетесь.

В нашем примере у нас есть массив 3 5 3 2 1 , поэтому мы делим его на 3 5 4 и 2 1 . Чтобы отсортировать их, мы далее разделяем их на составляющие. Как только мы достигли дна, мы начинаем объединять и сортировать их по мере продвижения.

Если вы хотите прочитать подробную статью о сортировке слиянием , мы вам поможем!

Выполнение

Основная функция работает примерно так, как описано в объяснении. Мы просто передаем индексы left и right которые являются индексами самого левого и самого правого элемента подмассива, который мы хотим отсортировать. Первоначально они должны быть 0 и array.length-1 , в зависимости от реализации.

Основа нашей рекурсии гарантирует, что мы выйдем, когда мы закончим или когда right и left встретятся друг с другом. Мы находим середину mid и рекурсивно сортируем подмассивы слева и справа от нее, в конечном итоге объединяя наши решения.

Если вы помните нашу древовидную графику, вы можете задаться вопросом, почему бы нам не создать два новых меньших массива и вместо этого передать их. Это связано с тем, что на очень длинных массивах это привело бы к огромному потреблению памяти для чего-то, что по сути не нужно.

Сортировка слиянием уже не работает на месте из-за этапа слияния, и это только ухудшит ее эффективность использования памяти. В остальном логика нашего дерева рекурсии остается прежней, хотя нам просто нужно следовать индексам, которые мы используем:

 public static void mergeSort(int[] array, int left, int right) { 
 if (right <= left) return; 
 int mid = (left+right)/2; 
 mergeSort(array, left, mid); 
 mergeSort(array, mid+1, right); 
 merge(array, left, mid, right); 
 }

Чтобы объединить отсортированные подмассивы в один, нам нужно рассчитать длину каждого и создать временные массивы для их копирования, чтобы мы могли свободно изменять наш основной массив.

После копирования проходим получившийся массив и присваиваем ему текущий минимум. Поскольку наши подмассивы отсортированы, мы просто выбрали меньший из двух элементов, которые еще не были выбраны, и переместили итератор для этого подмассива вперед:

 void merge(int[] array, int left, int mid, int right) { 
 // calculating lengths 
 int lengthLeft = mid - left + 1; 
 int lengthRight = right - mid; 
 
 // creating temporary subarrays 
 int leftArray[] = new int [lengthLeft]; 
 int rightArray[] = new int [lengthRight]; 
 
 // copying our sorted subarrays into temporaries 
 for (int i = 0; i < lengthLeft; i++) 
 leftArray[i] = array[left+i]; 
 for (int i = 0; i < lengthRight; i++) 
 rightArray[i] = array[mid+i+1]; 
 
 // iterators containing current index of temp subarrays 
 int leftIndex = 0; 
 int rightIndex = 0; 
 
 // copying from leftArray and rightArray back into array 
 for (int i = left; i < right + 1; i++) { 
 // if there are still uncopied elements in R and L, copy minimum of the two 
 if (leftIndex < lengthLeft && rightIndex < lengthRight) { 
 if (leftArray[leftIndex] < rightArray[rightIndex]) { 
 array[i] = leftArray[leftIndex]; 
 leftIndex++; 
 } 
 else { 
 array[i] = rightArray[rightIndex]; 
 rightIndex++; 
 } 
 } 
 // if all the elements have been copied from rightArray, copy the rest of leftArray 
 else if (leftIndex < lengthLeft) { 
 array[i] = leftArray[leftIndex]; 
 leftIndex++; 
 } 
 // if all the elements have been copied from leftArray, copy the rest of rightArray 
 else if (rightIndex < lengthRight) { 
 array[i] = rightArray[rightIndex]; 
 rightIndex++; 
 } 
 } 
 }

Сложность времени

Если мы хотим определить сложность рекурсивных алгоритмов, нам понадобится немного математики.

Основная теорема используется для определения временной сложности рекурсивных алгоритмов. Для нерекурсивных алгоритмов мы обычно можем записать точную временную сложность в виде некоторого уравнения, а затем использовать нотацию Big-O, чтобы отсортировать их по классам алгоритмов аналогичного поведения.

Проблема с рекурсивными алгоритмами в том, что это же уравнение будет выглядеть примерно так:

$$
T (n) = aT (\ frac {n} {b}) + cn ^ k
$

Само уравнение рекурсивное! В этом уравнении a сообщает нам, сколько раз мы вызываем рекурсию, а b сообщает нам, на сколько частей разделена наша проблема. В этом случае это может показаться несущественным различием, потому что они равны для сортировки слиянием, но для некоторых проблем их может не быть.

Остальная часть уравнения - это сложность объединения всех этих решений в одно в конце. Основная теорема решает это уравнение за нас:

$$
Т (п) = \ Bigg \ {
\ begin {matrix}
O (n ^ {log_ba}), & a> b ^ k \\ O (n ^ klog n), & a = b ^ k \\ O (n ^ k), & a <b ^ k
\ end {matrix}
$

Если T(n) - это время выполнения алгоритма при сортировке массива длины n , сортировка слиянием будет выполняться дважды для массивов, которые составляют половину длины исходного массива.

Итак, если у нас есть a=2 , b=2 . Шаг слияния занимает O (n) памяти, поэтому k=1 . Это означает, что уравнение сортировки слиянием будет выглядеть следующим образом:

$$
T (n) = 2T (\ frac {n} {2}) + cn
$

Если мы применим основную теорему, мы увидим, что наш случай - это тот, где a=b^k потому что у нас 2=2^1 . Это означает, что наша сложность O (nlog n) . Это чрезвычайно хорошая временная сложность для алгоритма сортировки, поскольку было доказано, что массив не может быть отсортирован быстрее, чем O (nlog n) .

Хотя версия, которую мы продемонстрировали, потребляет много памяти, существуют более сложные версии сортировки слиянием, которые занимают только O (1) места.

Кроме того, алгоритм чрезвычайно легко распараллелить, поскольку рекурсивные вызовы из одного узла могут выполняться полностью независимо от отдельных ветвей. Хотя мы не будем вдаваться в подробности, как и почему, поскольку это выходит за рамки данной статьи, стоит помнить о плюсах использования этого конкретного алгоритма.

Heapsort

Объяснение

Чтобы правильно понять, почему работает Heapsort, вы должны сначала понять структуру, на которой он основан - кучи . Мы будем говорить конкретно о двоичной куче, но вы можете обобщить большую часть этого и на другие структуры кучи.

Куча - это дерево, которое удовлетворяет свойству кучи, то есть для каждого узла все его дочерние элементы находятся в заданном отношении к нему. Кроме того, куча должна быть почти полной. Почти полное двоичное дерево глубины d имеет поддерево глубины d-1 с тем же полным корнем, в котором каждый узел с левым потомком имеет полное левое поддерево. Другими словами, при добавлении узла мы всегда выбираем крайнюю левую позицию на самом высоком незавершенном уровне.

Если куча - это максимальная куча , тогда все дочерние элементы меньше родительского, а если это минимальная куча, все они больше.

Другими словами, по мере движения вниз по дереву вы получаете все меньшие и меньшие числа (min-heap) или все большие и большие числа (max-heap). Вот пример максимальной кучи:

Макс.Куча{.ezlazyload}

Мы можем представить эту максимальную кучу в памяти в виде массива следующим образом:

 8 5 6 3 1 2 4

Вы можете представить себе это как чтение от уровня графика слева направо. Этим мы достигли того, что если мы возьмем kth элемент в массиве, его дочерние позиции будут 2*k+1 и 2*k+2 (при условии, что индексирование начинается с 0). Вы можете убедиться в этом сами.

И наоборот, для kth элемента позиция родителя всегда (k-1)/2 .

Зная это, вы можете легко "максимально увеличить кучу" для любого заданного массива. Для каждого элемента проверьте, не меньше ли его дочерний элемент. Если это так, поменяйте местами один из них с родительским и рекурсивно повторите этот шаг с родительским элементом (потому что новый большой элемент все еще может быть больше, чем его другой дочерний элемент).

У листьев нет дочерних элементов, поэтому они банально представляют собой максимальные кучи:

  • 6 1 8 3 5 2 4 : Оба потомка меньше, чем родитель, поэтому все остается неизменным.

  • 6 1 8 3 5 2 4: Поскольку 5> 1, мы меняем их местами. Мы рекурсивно нагромождаем сейчас 5.

  • 6 5 8 3 1 2 4: Оба ребенка меньше, поэтому ничего не происходит.

  • 6 5 8 3 1 2 4: Поскольку 8> 6, мы меняем их местами.

  • 8 5 6 3 1 2 4: У нас есть куча, изображенная выше!

Как только мы научимся нагромождать массив, все остальное будет довольно просто. Мы меняем местами корень кучи с концом массива и сокращаем массив на единицу.

Мы снова нагромождаем сокращенный массив и повторяем процесс:

  • 8 5 6 3 1 2 4

  • 4 5 6 3 1 2 8 : поменяно местами

  • 6 5 4 3 1 2 8 : с кучей

  • 2 5 4 3 1 6 8 : поменяно местами

  • 5 2 4 2 1 6 8 : с кучей

  • 1 2 4 2 5 6 8 : поменяно местами

И так далее, я уверен, вы можете увидеть, как возникает закономерность.

Выполнение

 static void heapify(int[] array, int length, int i) { 
 int leftChild = 2*i+1; 
 int rightChild = 2*i+2; 
 int largest = i; 
 
 // if the left child is larger than parent 
 if (leftChild < length && array[leftChild] > array[largest]) { 
 largest = leftChild; 
 } 
 
 // if the right child is larger than parent 
 if (rightChild < length && array[rightChild] > array[largest]) { 
 largest = rightChild; 
 } 
 
 // if a swap needs to occur 
 if (largest != i) { 
 int temp = array[i]; 
 array[i] = array[largest]; 
 array[largest] = temp; 
 heapify(array, length, largest); 
 } 
 } 
 
 public static void heapSort(int[] array) { 
 if (array.length == 0) return; 
 
 // Building the heap 
 int length = array.length; 
 // we're going from the first non-leaf to the root 
 for (int i = length / 2-1; i >= 0; i--) 
 heapify(array, length, i); 
 
 for (int i = length-1; i >= 0; i--) { 
 int temp = array[0]; 
 array[0] = array[i]; 
 array[i] = temp; 
 
 heapify(array, i, 0); 
 } 
 }

Сложность времени

Когда мы смотрим на heapify() , кажется, что все делается за O (1) , но есть этот надоедливый рекурсивный вызов.

Сколько раз это будет вызвано в худшем случае? Что ж, в худшем случае он будет распространяться до самого верха кучи. Он сделает это, перейдя к родительскому элементу каждого узла, таким образом, вокруг позиции i/2 . это означает, что он сделает в худшем случае log n прыжков, прежде чем достигнет вершины, поэтому сложность составляет O (log n) .

Поскольку heapSort() явно O (n) из-за циклов for, повторяющихся по всему массиву, это сделает общую сложность Heapsort равной O (nlog n) .

Heapsort - это сортировка на месте, то есть для нее требуется O (1) дополнительного места, в отличие от сортировки слиянием, но у нее также есть некоторые недостатки, такие как сложность распараллеливания.

Быстрая сортировка

Объяснение

Quicksort - это еще один алгоритм «разделяй и властвуй». Он выбирает один элемент массива в качестве точки поворота и сортирует все остальные элементы вокруг него, например меньшие элементы слева и большие справа.

Это гарантирует, что ось будет на своем месте после процесса. Затем алгоритм рекурсивно делает то же самое для левой и правой частей массива.

Выполнение

 static int partition(int[] array, int begin, int end) { 
 int pivot = end; 
 
 int counter = begin; 
 for (int i = begin; i < end; i++) { 
 if (array[i] < array[pivot]) { 
 int temp = array[counter]; 
 array[counter] = array[i]; 
 array[i] = temp; 
 counter++; 
 } 
 } 
 int temp = array[pivot]; 
 array[pivot] = array[counter]; 
 array[counter] = temp; 
 
 return counter; 
 } 
 
 public static void quickSort(int[] array, int begin, int end) { 
 if (end <= begin) return; 
 int pivot = partition(array, begin, end); 
 quickSort(array, begin, pivot-1); 
 quickSort(array, pivot+1, end); 
 }

Сложность времени

Временная сложность Quicksort может быть выражена следующим уравнением:

$$
Т (п) = Т (к) + Т (нк-1) + О (п)
$

Наихудший сценарий - когда для поворота всегда выбирается самый большой или самый маленький элемент. Тогда уравнение будет выглядеть так:

$$
Т (п) = Т (0) + Т (п-1) + О (п) = Т (п-1) + О (п)
$

Оказывается, это O (n ^ 2) .

Это может показаться плохим, поскольку мы уже изучили несколько алгоритмов, которые работают за время O (nlog n) как наихудший случай, но Quicksort на самом деле очень широко используется.

Это потому, что он имеет действительно хорошее среднее время выполнения, также ограниченное O (nlog n) , и очень эффективно для большой части возможных входных данных.

Одна из причин, по которой предпочтение отдается сортировке слиянием, заключается в том, что она не занимает лишнего места, вся сортировка выполняется на месте и отсутствуют дорогостоящие вызовы выделения и освобождения.

Сравнение производительности

При этом часто бывает полезно запустить все эти алгоритмы на вашем компьютере несколько раз, чтобы получить представление о том, как они работают.

Они будут работать по-разному с разными коллекциями, которые, конечно, сортируются, но даже с учетом этого вы сможете заметить некоторые тенденции.

Давайте запустим все реализации, одну за другой, каждая на копии перетасованного массива из 10 000 целых чисел:

время (нс) Пузырьковая сортировка Сортировка вставкой Выбор Сортировка Сортировка слиянием HeapSort QuickSort
Первый забег 266 089 476 21 973 989 66 603 076 5 511 069 5 283 411 4 156 005
Второй прогон 323 692 591 29 138 068 80 963 267 8 075 023 6 420 768 7 060 203
Третий пробег 303 853 052 21 380 896 91 810 620 7 765 258 8 009 711 7 622 817
Четвертый забег 410 171 593 30 995 411 96 545 412 6 560 722 5 837 317 2 358 377
Пятый заезд 315 602 328 26 119 110 95 742 699 5 471 260 14 629 836 3 331 834
Шестой пробег 286 841 514 26 789 954 90 266 152 9 898 465 4 671 969 4 401 080
Седьмой забег 384 841 823 18 979 289 72 569 462 5 135 060 10 348 805 4 982 666
Восьмерка 393 849 249 34 476 528 107 951 645 8 436 103 10 142 295 13 678 772
Девятый забег 306 140 830 57 831 705 138 244 799 5 154 343 5 654 133 4,663,260
Десятый забег 306 686 339 34 594 400 89 442 602 5 601 573 4 675 390 3 148 027

Очевидно, мы видим, что пузырьковая сортировка - худшая, когда дело касается производительности. Избегайте использования его в производственной среде, если вы не можете гарантировать, что он будет обрабатывать только небольшие коллекции и не остановит приложение.

HeapSort и QuickSort являются лучшими с точки зрения производительности. Хотя они выдают похожие результаты, QuickSort, как правило, немного лучше и согласованнее, что подтверждается.

Сортировка в Java

Сопоставимый интерфейс

Если у вас есть собственные типы, реализация отдельного алгоритма сортировки для каждого из них может оказаться обременительной. Вот почему Java предоставляет интерфейс, позволяющий использовать Collections.sort() в ваших собственных классах.

Для этого ваш класс должен реализовать Comparable<T> , где T - ваш тип, и переопределить метод с именем .compareTo() .

Этот метод возвращает отрицательное целое число, если this меньше элемента аргумента, 0, если они равны, и положительное целое число, если this больше.

В нашем примере мы создали класс « Student , и каждый студент идентифицируется по id и году начала учебы.

Мы хотим отсортировать их в первую очередь по поколениям, но также во вторую очередь по идентификаторам:

 public static class Student implements Comparable<Student> { 
 int studentId; 
 int studentGeneration; 
 
 public Student(int studentId, int studentGeneration) { 
 this.studentId = studentId; 
 this.studentGeneration = studentGeneration; 
 } 
 
 @Override 
 public String toString() { 
 return studentId + "/" + studentGeneration % 100; 
 } 
 
 @Override 
 public int compareTo(Student student) { 
 int result = this.studentGeneration - student.studentGeneration; 
 if (result != 0) 
 return result; 
 else 
 return this.studentId - student.studentId; 
 } 
 }

А вот как его использовать в приложении:

 public static void main(String[] args) { 
 Student[] a = new SortingAlgorithms.Student[5]; 
 a[0] = new Student(75, 2016); 
 a[1] = new Student(52, 2019); 
 a[2] = new Student(57, 2016); 
 a[3] = new Student(220, 2014); 
 a[4] = new Student(16, 2018); 
 
 Arrays.sort(a); 
 
 System.out.println(Arrays.toString(a)); 
 }

Выход:

 [220/14, 57/16, 75/16, 16/18, 52/19]

Интерфейс компаратора

Мы могли бы захотеть отсортировать наши объекты неортодоксальным способом для определенной цели, но мы не хотим реализовывать это как поведение нашего класса по умолчанию, или мы могли бы сортировать коллекцию встроенного типа в не- способ по умолчанию.

Для этого мы можем использовать интерфейс Comparator Например, возьмем наш Student и отсортируем только по ID:

 public static class SortByID implements Comparator<Student> { 
 public int compare(Student a, Student b) { 
 return a.studentId - b.studentId; 
 } 
 }

Если мы заменим вызов sort в main следующим:

 Arrays.sort(a, new SortByID());

Выход:

 [16/18, 52/19, 57/16, 75/16, 220/14]

Как все это работает

Collection.sort() работает, вызывая базовый Arrays.sort() , в то время как сама сортировка использует сортировку вставкой для массивов короче 47 и Quicksort для остальных.

Согласно документации JDK10, он основан на конкретной реализации Quicksort с двумя опорами, что позволяет избежать большинства типичных причин снижения производительности до квадратичной.

Заключение

Сортировка - очень распространенная операция с наборами данных, будь то их дальнейший анализ, ускорение поиска за счет использования более эффективных алгоритмов, основанных на сортируемых данных, фильтрации данных и т. Д.

Сортировка поддерживается многими языками, и интерфейсы часто скрывают от программиста, что на самом деле происходит. Хотя эта абстракция приветствуется и необходима для эффективной работы, иногда она может быть смертельной для эффективности, и полезно знать, как реализовать различные алгоритмы, и знать их плюсы и минусы, а также то, как легко получить доступ к встроенным реализациям.

comments powered by Disqus

Содержание