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

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

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

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

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

Сортировка скорлупы На Яве

public final class ShellSort {

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

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

        for (int gap = arrayLength / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arrayLength; i++) {
                int newElement = collection[i];

                int j = i;
                while (j >= gap && collection[j - gap] > newElement) {
                    collection[j] = collection[j - gap];
                    j -= gap;
                }
                collection[j] = newElement;
            }
        }
    } 
}

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

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

Вывод

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

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

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