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

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

В этой статье будут обсуждаться различные методы сортировки массива примитивных типов или объектов в Java.

1. Сортировка массива с помощью Arrays.sort() метод

Arrays class предоставляет несколько статических методов для сортировки массивов:

Он сортирует указанный массив типов примитивов или объектов в порядке возрастания в соответствии с естественным порядком его элементов.

У него также есть версия, которая сортирует указанный массив между указанным диапазоном:

Arrays.sort() использует Dual-Pivot Quicksort, который предлагает O(n.log(n)) производительность. Обычно это быстрее, чем традиционный (одноповоротный) Быстрая сортировка реализации.

Он сортирует указанный массив объектов в соответствии с порядком, заданным указанным компаратором. Он требует, чтобы все элементы массива были взаимно сравнимы указанным компаратором, т. е. для любой пары элементов (e1, e2) в массиве, c.compare(e1, e2) не следует бросать ClassCastException .

⮚ Чтобы отсортировать по возрастанию:

⮚ Чтобы отсортировать по убыванию:

Arrays . sort ( arr , Comparator . reverseOrder ( ) ) ; // или используйте `Collections.reverseOrder()`)

Мы также можем написать собственный компаратор, как показано ниже:

Он также предоставляет версию, которая сортирует указанный массив объектов между указанным диапазоном в соответствии с порядком, заданным указанным компаратором:

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

2. Сортировка массива с помощью Arrays.parallelSort() метод

Java 8 также предоставляет Arrays.parallelSort() который использует несколько потоков для сортировки, в отличие от Arrays.sort() который использует только один поток для сортировки элементов. Прототип parallelSort() похоже на sort() .

Это бьет Arrays.sort() когда общее количество элементов превышает определенный порог. Внутри любой массив размером меньше порогового значения сортируется с помощью Arrays.sort() . Порог рассчитывается с учетом параллелизма машины и размера массива. Общий пул ForkJoin используется для выполнения любых параллельных задач.

Следующая программа на Java сравнивает производительность Arrays.parallelSort() с Arrays.sort() на огромном наборе данных из 10 миллионов целых чисел:

Источник

Алгоритмы сортировки на Java с примерами

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

Алгоритм сортировки пузырьком на Java

Сортировка пузырьком (Bubble Sort) — это один из наиболее известных алгоритмов, суть которого состоит в последовательном сравнении двух соседних элементов. В том случае, если предыдущий элемент больше последующего, они меняются местами.

Так выглядит сортировка пузырьком на Java:

public static void bubbleSort(int[] sortArr) < for (int i = 0; i < sortArr.length - 1; i++) < for(int j = 0; j < sortArr.length - i - 1; j++) < if(sortArr[j + 1] < sortArr[j]) < int swap = sortArr[j]; sortArr[j] = sortArr[j + 1]; sortArr[j + 1] = swap; >> > > public static void main(String args[]) < int[] sortArr = ; bubbleSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Объяснение

Как видим из кода, метод bubbleSort() принимает массив в качестве входных данных для сортировки — sortArr . Далее мы создаём внешний цикл for , который перебирает каждый элемент массива, тогда как внутренний цикл for начинается с первого элемента массива до предпоследнего индекса: sortArr.length — i — 1 . С помощью условия if мы проверяем, больше ли элемент слева элемента справа или нет. Если элемент слева действительно больше, он меняется местами с правым элементом.

Примечание Внешний цикл for будет перебирать все элементы массива, даже если массив уже полностью отсортирован.

Массив, который принимает метод bubbleSort() , может быть любым. В нашем примере мы передаём значения 12, 6, 4, 1, 15, 10 .

Сложность алгоритма: О(n2)

А ниже представлен алгоритм сортировки двумерного массива Java пузырьком:

public static int[][] matrixBubbleSort(int[][] sortMatrix) < int swap; for (int i = 0; i < sortMatrix.length; i++) < for (int j = 0; j < sortMatrix[i].length; j++) < for (int k = 0; k < sortMatrix.length; k++) < for (int l = 0; l < sortMatrix[k].length; l++) < if (sortMatrix[i][j] > > > > return sortMatrix; > public static void main(String args[]) < int[][] sortMatrix = new int[][]< , , >; matrixBubbleSort(sortMatrix); //Вывод отсортированного двумерного массива: for (int i = 0; i < sortMatrix.length; i++) < for (int j = 0; j < sortMatrix[i].length; j++) < System.out.print(sortMatrix[i][j] + " "); >System.out.println(); > >

Алгоритм быстрой сортировки на Java

Быстрая сортировка, также известная как Quick Sort или сортировка Хоара, является одним их самых эффективных алгоритмов. Она включает в себя три этапа:

1. Из массива выбирается опорный элемент, чаще всего посередине массива.
2. Другие элементы массива распределяются таким образом, чтобы меньшие размещались до него, а большие — после.
3. Далее первые шаги рекурсивно применяются к подмассивам, которые разделились опорным элементом на две части — слева и справа от него.

Пример быстрой сортировки на языке Java:

public static void quickSort(int[] sortArr, int low, int high) < //завершить,если массив пуст или уже нечего делить if (sortArr.length == 0 || low >= high) return; //выбираем опорный элемент int middle = low + (high - low) / 2; int border = sortArr[middle]; //разделияем на подмассивы и меняем местами int i = low, j = high; while (i border) j--; if (i > //рекурсия для сортировки левой и правой части if (low < j) quickSort(sortArr, low, j); if (high >i) quickSort(sortArr, i, high); > public static void main(String args[]) < int[] sortArr = ; quickSort(sortArr, 0, sortArr.length - 1); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Сложность алгоритма: O(n log n)

Алгоритм сортировки слиянием на Java

Данный алгоритм разбивает список на две части, каждую из них он разбивает ещё на две и так далее, пока не останутся единичные элементы. Массив из одного элемента считается упорядоченным. Соседние элементы сравниваются и соединяются вместе. Так происходит до тех пор, пока все элементы не будут отсортированы.

Примечание По возможности используйте готовые алгоритмы для коллекций и методы из java.util.Arrays .

Реализовать алгоритм сортировки слиянием на Java можно так:

import java.util.Arrays; public class Main < public static int[] mergeSort(int[] sortArr) < int[] buffer1 = Arrays.copyOf(sortArr, sortArr.length); int[] buffer2 = new int[sortArr.length]; int[] result = mergeSortInner(buffer1, buffer2, 0, sortArr.length); return result; >public static int[] mergeSortInner(int[] buffer1, int[] buffer2, int startIndex, int endIndex) < if (startIndex >= endIndex - 1) < return buffer1; >//уже отсортирован int middle = startIndex + (endIndex - startIndex) / 2; int[] sorted1 = mergeSortInner(buffer1, buffer2, startIndex, middle); int[] sorted2 = mergeSortInner(buffer1, buffer2, middle, endIndex); //слияние int index1 = startIndex; int index2 = middle; int destIndex = startIndex; int[] result = sorted1 == buffer1 ? buffer2 : buffer1; while (index1 < middle && index2 < endIndex) < result[destIndex++] = sorted1[index1] < sorted2[index2] ? sorted1[index1++] : sorted2[index2++]; >while (index1 < middle) < result[destIndex++] = sorted1[index1++]; >while (index2 < endIndex) < result[destIndex++] = sorted2[index2++]; >return result; > public static void main(String args[]) < int[] sortArr = ; int[] result = mergeSort(sortArr); System.out.println(Arrays.toString(result)); > >

Объяснение

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

Сложность алгоритма: O(n log n)

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

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

Так выглядит сортировка вставками на Java:

public static void insertionSort(int[] sortArr) < int j; //сортировку начинаем со второго элемента, т.к. считается, что первый элемент уже отсортирован for (int i = 1; i < sortArr.length; i++) < //сохраняем ссылку на индекс предыдущего элемента int swap = sortArr[i]; for (j = i; j >0 && swap < sortArr[j - 1]; j--) < //элементы отсортированного сегмента перемещаем вперёд, если они больше элемента для вставки sortArr[j] = sortArr[j - 1]; >sortArr[j] = swap; > > public static void main(String args[]) < int[] sortArr = ; insertionSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Объяснение

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

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

Сложность алгоритма: О(n2) для сравнений и перестановок.

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

1. Разбиваем массив на отсортированную и неотсортированную части.
2. Находим в неотсортированной части минимальный элемент.
3. Меняем его местами с тем элементом, который находится на нулевой позиции —
   в конец отсортированного массива.
4. Далее находим следующий по величине элемент и меняем его с элементом на первой позиции, etc., пока не закончатся неотсортированные значения.

Реализация сортировки выбором на языке программирования Java:

public static void selectionSort(int[] sortArr) < for (int i = 0; i < sortArr.length; i++) < int pos = i; int min = sortArr[i]; //цикл выбора наименьшего элемента for (int j = i + 1; j < sortArr.length; j++) < if (sortArr[j] < min) < //pos - индекс наименьшего элемента pos = j; min = sortArr[j]; >> sortArr[pos] = sortArr[i]; //меняем местами наименьший с sortArr[i] sortArr[i] = min; > > public static void main(String args[]) < int[] sortArr = ; selectionSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Сложность алгоритма: О(n2)

Алгоритм пирамидальной сортировки на Java

Чтобы реализовать алгоритм пирамидальной сортировки (Heapsort) на Java, нужно сперва понять принцип. Алгоритм сегментирует массив на отсортированный и неотсортированный. Неотсортированный сегмент преобразовывается в кучу (heap), что позволяет эффективно эффективно определить самый большой элемент.

Пирамидальная сортировка на Java с использованием класса java.util.Arrays :

//вернуть левого потомка `A[i]` private static int LEFT(int i) < return (2 * i + 1); >//вернуть правого потомка `A[i]` private static int RIGHT(int i) < return (2 * i + 2); >//вспомогательная функция для замены двух индексов в массиве private static void swap(int[] sortArr, int i, int j) < int swap = sortArr[i]; sortArr[i] = sortArr[j]; sortArr[j] = swap; >//рекурсивный алгоритм heapify-down. Узел с индексом `i` и 2 его прямых потомка нарушают свойство кучи private static void heapify(int[] sortArr, int i, int size) < // получить левый и правый потомки узла с индексом `i` int left = LEFT(i); int right = RIGHT(i); int largest = i; //сравниваем `A[i]` с его левым и правым дочерними элементами и находим наибольшее значение if (left < size && sortArr[left] >sortArr[i]) largest = left; if (right < size && sortArr[right] >sortArr[largest]) largest = right; //поменяться местами с потомком, имеющим большее значение и вызовите heapify-down для дочернего элемента if (largest != i) < swap(sortArr, i, largest); heapify(sortArr, largest, size); >> //функция для удаления элемента с наивысшим приоритетом (присутствует в корне) public static int pop(int[] sortArr, int size) < //если в куче нет элементов if (size int top = sortArr[0]; //заменяем корень кучи последним элементом массива sortArr[0] = sortArr[size-1]; //вызовите heapify-down на корневом узле heapify(sortArr, 0, size - 1); return top; > //функция для выполнения пирамидальной сортировки массива `A` размера `n` public static void heapSort(int[] sortArr) < //строим приоритетную очередь и инициализируем ее заданным массивом int n = sortArr.length; //build-heap: вызывать heapify, начиная с последнего внутреннего //узел до корневого узла int i = (n - 2) / 2; while (i >= 0) < heapify(sortArr, i--, n); >//несколько раз извлекаем из кучи, пока она не станет пустой while (n > 0) < sortArr[n - 1] = pop(sortArr, n); n--; >> public static void main(String args[]) < int[] sortArr = ; heapSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Сложность алгоритма: O(n log n)

Источник