Реализуйте алгоритм сортировки подсчетом в Java

Что такое алгоритм сортировки подсчетом?

Сортировка подсчетом — алгоритм сортировки, эффективный для small ranges of integers . Он работает, подсчитывая количество вхождений каждого значения во входном массиве, а затем используя эту информацию, чтобы поместить каждое значение в правильное положение в выходном массиве.

Временная сложность этого алгоритма составляет O(n+k) , где n — размер входного массива, а k — диапазон целых чисел.

CrunchifyCountingSortAlgo.java

Вот полная реализация Counting Sort в Java. Просто скопируйте его в предпочтительную IDEA и запустите.

 пакет crunchify.com.java.tutorials;

импортировать java.util.Arrays;

/**
 * @автор Crunchify.com
 * Программа: Как реализовать алгоритм сортировки подсчетом в java?
 * Сортировка подсчетом — это алгоритм сортировки, который сортирует элементы массива. 
 * путем подсчета количества вхождений каждого уникального элемента в массиве.
 */

открытый класс CrunchifyCountingSortAlgo {

    public static void main(String[] args) {

        // Целочисленный массив из 10 элементов
        int[] crunchifyArray = {9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3};

        crunchifyPrint("Исходный массив: " + Arrays.toString(crunchifyArray));
        crunchifyPrint("\n");

        CrunchifyCountingSortAlgo crunchify = new CrunchifyCountingSortAlgo();
        crunchify.crunchifyCountingSortAlgorithm (crunchifyArray);

        crunchifyPrint("\n");
        crunchifyPrint("Результат алгоритма сортировки подсчетом Crunchify: " + Arrays.toString(crunchifyArray));
    }

    private static void crunchifyPrint (String s) {

        System.out.println(s);
    }


    /**
     * Автор: Апп Шах (Crunchify.com)
     *
     * Логика сортировки подсчетом:
     * Это реализация сортировки подсчетом, алгоритма сортировки, который эффективен для небольших диапазонов целых чисел.
     * Он работает, подсчитывая количество вхождений каждого значения во входном массиве,
     * а затем, используя эту информацию, поместить каждое значение в правильное положение в выходном массиве.
     * Временная сложность этого алгоритма O(n+k),
     * где n — размер входного массива, а k — диапазон целых чисел.
     */


    public static int[] crunchifyCountingSortAlgorithm(int[] crunchifyArray) {

        // getAsInt(): если значение присутствует, возвращает значение, в противном случае генерирует исключение NoSuchElementException.
        int crunchifyMax = Arrays.stream(crunchifyArray).max().getAsInt();
        int[] crunchifyCount = новый int[crunchifyMax + 1];

        // crunchifyПодсчет вхождений каждого значения во входном массиве
        for (int i = 0; i < crunchifyArray.length; i++) {
            crunchifyCount[crunchifyArray[i]]++;
            crunchifyPrint("Добавление 1 к crunchifyCount[" + crunchifyArray[i] 
                    + "], массив crunchifyCount теперь: " + Arrays.toString(crunchifyCount));
        }

        crunchifyPrint("\n");

        инт к = 0;
        for (int i = 0; i <= crunchifyMax; i++) {
            for (int j = 0; j < crunchifyCount[i]; j++) {
                crunchifyArray[k++] = i;
                crunchifyPrint("Добавление " + i + " в позицию " + (k - 1) 
                        + " в выходном массиве теперь выходной массив: " + Arrays.toString(crunchifyArray));
            }
        }

        вернуть crunchifyArray;
    }

}

Просто запустите указанную выше программу как приложение Java в IntelliJ IDEA или Eclipse IDE, и вы получите результат, как показано ниже.

Результат консоли IntelliJ IDEA

 Исходный массив: [9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]


Добавление 1 к crunchifyCount[9], массив crunchifyCount теперь: [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Добавление 1 к crunchifyCount[3], массив crunchifyCount теперь: [0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Добавление 1 к crunchifyCount[6], массив crunchifyCount теперь: [0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Добавление 1 к crunchifyCount[6], массив crunchifyCount теперь: [0, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Добавление 1 к crunchifyCount[1], массив crunchifyCount теперь: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Добавление 1 к crunchifyCount[12], массив crunchifyCount теперь: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Добавление 1 к crunchifyCount[32], массив crunchifyCount теперь: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]
Добавление 1 к crunchifyCount[29], массив crunchifyCount теперь: [0, 1, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
Добавление 1 к crunchifyCount[2], массив crunchifyCount теперь: [0, 1, 1, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
Добавление 1 к crunchifyCount[9], массив crunchifyCount теперь: [0, 1, 1, 1, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]
Добавление 1 к crunchifyCount[3], массив crunchifyCount теперь: [0, 1, 1, 2, 0, 0, 2, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1]


Добавление 1 к позиции 0 в выходном массиве, теперь выходной массив: [1, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3]
Добавление 2 к позиции 1 в выходном массиве, теперь выходной массив: [1, 2, 6, 6, 1, 12, 32, 29, 2, 9, 3]
Добавление 3 к позиции 2 в выходном массиве, теперь выходной массив: [1, 2, 3, 6, 1, 12, 32, 29, 2, 9, 3]
Добавление 3 к позиции 3 в выходном массиве, теперь выходной массив: [1, 2, 3, 3, 1, 12, 32, 29, 2, 9, 3]
Добавление 6 к позиции 4 в выходном массиве, теперь выходной массив: [1, 2, 3, 3, 6, 12, 32, 29, 2, 9, 3]
Добавление 6 к позиции 5 в выходном массиве, теперь выходной массив: [1, 2, 3, 3, 6, 6, 32, 29, 2, 9, 3]
Добавление 9 к позиции 6 в выходном массиве, теперь выходной массив: [1, 2, 3, 3, 6, 6, 9, 29, 2, 9, 3]
Добавление 9 к позиции 7 в выходном массиве, теперь выходной массив: [1, 2, 3, 3, 6, 6, 9, 9, 2, 9, 3]
Добавление 12 к позиции 8 в выходном массиве, теперь выходной массив: [1, 2, 3, 3, 6, 6, 9, 9, 12, 9, 3]
Добавление 29 к позиции 9 в выходном массиве, теперь выходной массив: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 3]
Добавление 32 к позиции 10 в выходном массиве, теперь выходной массив: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]


Результат алгоритма сортировки подсчета Crunchify: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32]

Процесс завершен с кодом выхода 0 

Дайте мне знать, если у вас возникнут какие-либо проблемы с запуском Java-программы алгоритма сортировки подсчета.