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

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

Классификация алгоритмов

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

Пожалуйста, используйте следующую ссылку для объяснения обозначения Big-O и того, что хорошо, справедливо и плохо.

Сортировка вставки На Яве

public final class InsertionSort {

    public void sort(int[] collection) {
        if (collection != null) {
            insertionSort(collection);
        } else {
            throw new IllegalArgumentException("Input parameter for array to sort is null.");
        }
    } 


    private void insertionSort(int[] collection) {
        int arrayLength = collection.length;

        for (int unsortIndex = 1; unsortIndex < arrayLength;  unsortIndex++) {
            int newElement = collection[unsortIndex];
            int iterator = 0;

            for (iterator = unsortIndex; iterator > 0 && collection[iterator - 1] > newElement; iterator--) {
                collection[iterator] = collection[iterator - 1];
            }
            collection[iterator] = newElement;
        }
    }
}

Пример кода (GitHub)

Подробную информацию о классе сортировки вставки можно просмотреть здесь . Подробную информацию о тестовом классе JUnit для сортировки вставки можно просмотреть здесь .

Вывод

Алгоритм сортировки по вставке является частью более крупной группы алгоритмов сортировки. Обучение на основе опыта – вот причина, по которой я создал этот пост о реализации алгоритма сортировки вставок в Java. Я многое узнал о том, как другие решали алгоритм сортировки вставки на других языках, включая различные реализации в Java.

Сообщение Сортировка вставки в Java появилось первым на Код 2 бита .

Оригинал: “https://dev.to/code2bits/insertion-sort-in-java-50h7”