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

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

В одной из предыдущих статей мы разобрались, где применяются алгоритмы сортировки, а теперь поговорим об их реализации на 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 = {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");
    }
}

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

Объяснение алгоритмов сортировки с примерами на Python

tproger.ru

Встроенные функции сортировки Java

Рассмотрим метод 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)), а значит при удвоении количества данных в коллекции время поиска не удваивается, а увеличивается на постоянную величину.