Рассматриваем популярные алгоритмы сортировки и принципы их работы с примерами на языке программирования Java.
57К открытий72К показов
В одной из предыдущих статей мы разобрались, где применяются алгоритмы сортировки, а теперь поговорим об их реализации на 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 = {12, 6, 4, 1, 15, 10};
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] <= sortMatrix[k][l]) {
swap = sortMatrix[i][j];
sortMatrix[i][j] = sortMatrix[k][l];
sortMatrix[k][l] = swap;
}
}
}
}
}
return sortMatrix;
}
public static void main(String args[]) {
int[][] sortMatrix = new int[][]{
{8, 3, 5},
{1, 4, 6},
{9, 7, 2}
};
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 или сортировка Хоара, является одним их самых эффективных алгоритмов. Она включает в себя три этапа:
Из массива выбирается опорный элемент, чаще всего посередине массива.
Другие элементы массива распределяются таким образом, чтобы меньшие размещались до него, а большие — после.
Далее первые шаги рекурсивно применяются к подмассивам, которые разделились опорным элементом на две части — слева и справа от него.
Пример быстрой сортировки на языке 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 <= j) {
while (sortArr[i] < border) i++;
while (sortArr[j] > border) j--;
if (i <= j) {
int swap = sortArr[i];
sortArr[i] = sortArr[j];
sortArr[j] = swap;
i++;
j--;
}
}
//рекурсия для сортировки левой и правой части
if (low < j) quickSort(sortArr, low, j);
if (high > i) quickSort(sortArr, i, high);
}
public static void main(String args[]) {
int[] sortArr = {12, 6, 4, 1, 15, 10};
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 = {12, 6, 4, 1, 15, 10};
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 = {12, 6, 4, 1, 15, 10};
insertionSort(sortArr);
for(int i = 0; i < sortArr.length; i++){
System.out.print(sortArr[i] + "\n");
}
}
Объяснение
Предполагается, что первый элемент списка отсортирован. Переходим к следующему элементу, обозначим его i. Если х больше первого, оставляем его на своём месте. Если он меньше, копируем его на вторую позицию, а i устанавливаем в качестве первого элемента.
Переходя к другим элементам несортированного сегмента, перемещаем более крупные элементы в отсортированном сегменте вверх по списку, пока не встретим элемент меньше i или не дойдём до конца списка. В первом случае i помещается на правильную позицию.
Сложность алгоритма:О(n2) для сравнений и перестановок.
Алгоритм сортировки выбором на Java
Идея алгоритма:
Разбиваем массив на отсортированную и неотсортированную части.
Находим в неотсортированной части минимальный элемент.
Меняем его местами с тем элементом, который находится на нулевой позиции — в конец отсортированного массива.
Далее находим следующий по величине элемент и меняем его с элементом на первой позиции, 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 = {12, 6, 4, 1, 15, 10};
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 <= 0) {
return -1;
}
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 = {12, 6, 4, 1, 15, 10};
heapSort(sortArr);
for(int i = 0; i < sortArr.length; i++){
System.out.print(sortArr[i] + "\n");
}
}
Рассмотрим метод sort() классов Collections и Arrays, а также структуры данных вроде TreeMap и TreeSet.
Как использовать метод sort() в Java?
Метод Collections.sort() для сортировки коллекций:
List<ObjectName> list = new ArrayList<ObjectName>();
Collections.sort(list, new Comparator<ObjectName>() {
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<ObjectName>() {
public int compare(ObjectName o1, ObjectName o2) {
return o1.toString().compareTo(o2.toString());
}
});
Метод sort() удобно использовать в том случае, если массив или коллекция заблаговременно заполнены значениями.
Структуры данных
TreeMap и TreeSet
Для сортировки списков List и множеств Set следует использовать структуру TreeSet:
Set<ObjectName> sortedSet = new TreeSet<ObjectName>(new Comparator<ObjectName>() {
public int compare(ObjectName o1, ObjectName o2) {
return o1.toString().compareTo(o2.toString());
}
});
sortedSet.addAll(unsortedSet);
Если же речь идёт о коллекции пар ключ/значение Map, для сортировки подойдёт структура TreeMap, которая сортируется по ключу:
Map<String, Integer> sortedMap = new TreeMap<String, Integer>(String.CASE_INSENSITIVE_ORDER);
sortedMap.putAll(unsortedMap);
Map<ObjectName, String> sortedMap = new TreeMap<ObjectName, String>(new Comparator<ObjectName>() {
public int compare(ObjectName o1, ObjectName o2) {
return o1.toString().compareTo(o2.toString());
}
});
sortedMap.putAll(unsortedMap);
Самосортируемые структуры данных имеют эффективность O(log(n)), а значит при удвоении количества данных в коллекции время поиска не удваивается, а увеличивается на постоянную величину.
Профессия фронтенд-разработчика сейчас в числе самых востребованных в IT. Разбираем базовые вопросы для тех, кто планирует стать фронтенд-разработчиком.
Возможно, специальность графического дизайнера звучит просто — рисуешь себе макеты и всё. Однако нужно выполнять и другие сопутствующие задачи. Рассказываем, какие.
Узнали у middle и senior разработчиков, что нужно учить каждому Android-разработчику, какие фреймворки, библиотеки и инструменты устарели, а какие актуальны.
