Sorting coding in java

Как правильно делать сортировку в Java

Анализируя исходные коды многих opensource Java-проектов, я обнаружил, что большинство разработчиков осуществляют сортировку всего двумя разными способами. Один из них основан на применении метода sort() классов Collections или Arrays , а другой на использовании самосортирующихся структур данных, таких как TreeMap и TreeSet .

Использование метода sort()

 // Collections.sort(…) List list = new ArrayList(); Collections.sort(list, new Comparator() < public int compare(ObjectName o1, ObjectName o2) < return o1.toString().compareTo(o2.toString()); >>); 

 // Arrays.sort(…) ObjectName[] arr = new ObjectName[10]; Arrays.sort(arr, new Comparator() < public int compare(ObjectName o1, ObjectName o2) < return o1.toString().compareTo(o2.toString()); >>); 

Применение самосортирующихся структур данных

Если нужно отсортировать список ( List ) или множество ( Set ), используйте структуру TreeSet для сортировки.

 // TreeSet Set sortedSet = new TreeSet(new Comparator() < public int compare(ObjectName o1, ObjectName o2) < return o1.toString().compareTo(o2.toString()); >>); sortedSet.addAll(unsortedSet); 

Если вам требуется отсортировать словарь ( Map ), используйте структуру TreeMap для сортировки. TreeMap сортируется по ключу ( key ).

 // TreeMap – использующий String ключи и компаратор (Comparator) CASE_INSENSITIVE_ORDER, // упорядочивающий строки (String) методом compareToIgnoreCase Map sortedMap = new TreeMap(String.CASE_INSENSITIVE_ORDER); sortedMap.putAll(unsortedMap); 

 //TreeMap – общий случай, компаратор указывается вручную Map sortedMap = new TreeMap(new Comparator() < public int compare(ObjectName o1, ObjectName o2) < return o1.toString().compareTo(o2.toString()); >>); sortedMap.putAll(unsortedMap); 

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

Плохой подход к задаче сортировки

До сих пор можно встретить примеры, когда программисты самостоятельно описывают алгоритмы сортировки. Рассмотрим код сортировки, представленный ниже (сортировка double-массива по возрастанию (прим. перев.)). Этот код не только не эффективен, но и не читабелен. И таких примеров много.

Источник

Алгоритмы сортировки на 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)

Источник