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

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

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

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

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

Сортировка по вставке На языке Java

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 появилось впервые на Code 2 Bits .

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