Подсчет сортировки в Java

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

Начальная фаза алгоритма состоит в том, чтобы начать подсчет количества вхождений значений в массиве и увеличить значение, связанное с ключом подсчета. Второй этап состоит в том, чтобы записать новый отсортированный массив, используя количество вхождений каждого из ключей подсчета.

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

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

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

Подсчет Сортировки В Java

public final class CountingSort {

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

    private void countingSort(int[] collection, int maxValue) {
        int[] countArray = countOccurrences(collection, maxValue);
        reconstructArray(collection, countArray, maxValue);
    }

    private int findMaxValue(int[] collection) {
        int highest = collection[0];
        for (int index = 1; index < collection.length; index ++) {
            if (collection[index] > highest) {
                highest = collection [index];
            }
        }
        return highest;
    }

    private int[] countOccurrences(int[] collection, int maxValue) {
        int[] tempArray = new int[maxValue + 1];
        for (int i = 0; i < collection.length; i++) {
            int key = collection[i];
            tempArray[key]++;
        }    
        return tempArray;
    }

    private void reconstructArray(int[] collection, int[] countArray, int maxValue) {
        int j = 0;
        for (int i = 0; i <= maxValue; i++) {
            while (countArray[i] > 0) {
                collection[j++] = i;
                countArray[i]--;
            }
        }
    }
}

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

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

Вывод

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

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

Оригинал: “https://dev.to/code2bits/counting-sort-in-java-1jkg”