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

Автор оригинала: Darinka Zobenica.

Вступление

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

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

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

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

• Сортировка Пузырьков
• Сортировка Вставки
• Сортировка выбора
• Сортировка слиянием
• Куча
• Быстрая сортировка
• Сортировка на 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][i+1] , это могло бы закончиться бесконечным циклом , потому что для равных элементов это соотношение всегда было бы истинным и, следовательно, всегда меняло их местами.

Временная Сложность

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

5 4 3 2 1

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

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

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

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

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

Объяснение

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

Отсортированная часть имеет длину 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 x 7 8 2 1 9 6

• 3 x 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) .

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

Объяснение

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

• 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. Объедините решения

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

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

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

Реализация

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

Основа нашей рекурсии гарантирует, что мы выйдем, когда закончим, или когда вправо и влево встретимся друг с другом. Мы находим среднюю точку 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 для сортировки их по классам алгоритмов с аналогичным поведением.

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

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

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

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

$$ $$ T(n) = \Bigg\{ \начало{матрицы} O(n^{log_b a}), & a>b^k \\ O(n^klog n), &^k \\ O(n^k), & a < b^k \конец{матрицы} $$

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

Git Essentials

Ознакомьтесь с этим практическим руководством по изучению Git, содержащим лучшие практики и принятые в отрасли стандарты. Прекратите гуглить команды Git и на самом деле изучите это!

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

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

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

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

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

Куча

Объяснение

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

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

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

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

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

8 5 6 3 1 2 4

Вы можете представить это как чтение с графика уровень за уровнем, слева направо. Таким образом, мы добились того, что если мы возьмем k-й элемент в массиве, его дочерние позиции будут 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 . это означает, что он сделает на

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

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

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

Объяснение

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

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

Реализация

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);
}

Временная Сложность

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

$$ (k) + T(n-k-1) + O(n) $$

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

$$ (0) + T(n-1) +(n-1) + O(n) $$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

public static class Student implements Comparable {
    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 . Например, давайте возьмем наш Студент класс и отсортируем только по идентификатору:

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

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

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

Выход:

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

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

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

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

Вывод

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

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