Zaimplementuj algorytm sortowania zliczania w Javie
Opublikowany: 2023-01-30
Co to jest algorytm sortowania zliczającego?
Sortowanie zliczające , algorytm sortowania, który jest wydajny dla small ranges of integers . Działa poprzez zliczanie liczby wystąpień każdej wartości w tablicy wejściowej, a następnie wykorzystanie tych informacji do umieszczenia każdej wartości we właściwej pozycji w tablicy wyjściowej.
Złożoność czasowa tego algorytmu wynosi O(n+k) , gdzie n to rozmiar tablicy wejściowej, a k to zakres liczb całkowitych.
CrunchifyCountingSortAlgo.java
Oto pełna implementacja sortowania zliczającego w Javie. Po prostu skopiuj go do preferowanego IDEA i uruchom.
pakiet crunchify.com.java.tutorials;
importuj java.util.Arrays;
/**
* @autor Crunchify.com
* Program: Jak zaimplementować algorytm sortowania zliczającego w Javie?
* Sortowanie zliczające to algorytm sortowania, który sortuje elementy tablicy
* przez zliczenie liczby wystąpień każdego unikalnego elementu w tablicy.
*/
klasa publiczna CrunchifyCountingSortAlgo {
public static void main(String[] args) {
// Tablica liczb całkowitych 10 elementów
int[] crunchifyArray = {9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3};
crunchifyPrint("Oryginalna tablica: " + Arrays.toString(crunchifyArray));
crunchifyPrint("\n");
CrunchifyCountingSortAlgo crunchify = new CrunchifyCountingSortAlgo();
crunchify.crunchifyCountingSortAlgorithm(crunchifyArray);
crunchifyPrint("\n");
crunchifyPrint("Wynik algorytmu sortowania zliczania Crunchify: " + Arrays.toString(crunchifyArray));
}
prywatny statyczny void crunchifyPrint(String s) {
System.out.println(s);
}
/**
* Autor: App Shah (Crunchify.com)
*
* Licząca logika sortowania:
* Jest to implementacja sortowania zliczającego, algorytmu sortowania, który jest wydajny dla małych zakresów liczb całkowitych.
* Działa poprzez zliczanie liczby wystąpień każdej wartości w tablicy wejściowej,
* a następnie używając tych informacji do umieszczenia każdej wartości we właściwej pozycji w tablicy wyjściowej.
* Złożoność czasowa tego algorytmu wynosi O(n+k),
* gdzie n to rozmiar tablicy wejściowej, a k to zakres liczb całkowitych.
*/
public static int[] crunchifyCountingSortAlgorithm(int[] crunchifyArray) {
// getAsInt(): Jeśli wartość jest obecna, zwraca wartość, w przeciwnym razie zgłasza wyjątek NoSuchElementException.
int crunchifyMax = Arrays.stream(crunchifyArray).max().getAsInt();
int[]crunchifyCount = nowy int[crunchifyMax + 1];
// crunchifyZlicz wystąpienia każdej wartości w tablicy wejściowej
for (int i = 0; i < crunchifyArray.length; i++) {
crunchifyCount[crunchifyArray[i]]++;
crunchifyPrint("Dodawanie 1 do crunchifyCount[" + crunchifyArray[i]
+ "], tablica crunchifyCount to teraz: " + Arrays.toString(crunchifyCount));
}
crunchifyPrint("\n");
int k = 0;
for (int i = 0; i <= crunchifyMax; i++) {
for (int j = 0; j < crunchifyCount[i]; j++) {
crunchifyArray[k++] = i;
crunchifyPrint("Dodanie " + i + " do pozycji " + (k - 1)
+ " w tablicy wyjściowej, tablica wyjściowa to teraz: " + Arrays.toString(crunchifyArray));
}
}
powrót crunchifyArray;
}
}Po prostu uruchom powyższy program jako aplikację Java w IntelliJ IDEA lub Eclipse IDE, a otrzymasz wynik jak poniżej.
Wynik konsoli IntelliJ IDEA
Oryginalna tablica: [9, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3] Dodając 1 do crunchifyCount[9], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do crunchifyCount[3], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do crunchifyCount[6], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do crunchifyCount[6], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do crunchifyCount[1], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do crunchifyCount[12], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do crunchifyCount[32], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do crunchifyCount[29], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do crunchifyCount[2], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do crunchifyCount[9], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do crunchifyCount[3], tablica crunchifyCount wygląda teraz następująco: [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] Dodając 1 do pozycji 0 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 3, 6, 6, 1, 12, 32, 29, 2, 9, 3] Dodając 2 do pozycji 1 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 2, 6, 6, 1, 12, 32, 29, 2, 9, 3] Dodając 3 do pozycji 2 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 2, 3, 6, 1, 12, 32, 29, 2, 9, 3] Dodając 3 do pozycji 3 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 2, 3, 3, 1, 12, 32, 29, 2, 9, 3] Dodając 6 do pozycji 4 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 2, 3, 3, 6, 12, 32, 29, 2, 9, 3] Dodając 6 do pozycji 5 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 2, 3, 3, 6, 6, 32, 29, 2, 9, 3] Dodając 9 do pozycji 6 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 2, 3, 3, 6, 6, 9, 29, 2, 9, 3] Dodając 9 do pozycji 7 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 2, 3, 3, 6, 6, 9, 9, 2, 9, 3] Dodając 12 do pozycji 8 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 2, 3, 3, 6, 6, 9, 9, 12, 9, 3] Dodając 29 do pozycji 9 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 3] Dodając 32 do pozycji 10 w tablicy wyjściowej, tablica wyjściowa to teraz: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32] Wynik algorytmu sortowania zliczania Crunchify: [1, 2, 3, 3, 6, 6, 9, 9, 12, 29, 32] Proces zakończony kodem wyjścia 0
Daj mi znać, jeśli napotkasz jakiekolwiek problemy z działaniem powyżej programu Counting Sort Algorithm Java.