How it works?
Lektion 3 von 9 im Kurs Counting Sort - DSA-Serie von Coddy.
Counting Sort arbeitet in zwei Phasen: Zählen, dann Wiederaufbauen.
Schritt-für-Schritt-Prozess:
- Zählen: Erstellen Sie ein
count-Array, in demcount[v]angibt, wie oft der Wertvvorkommt. - Wiederaufbauen: Gehen Sie die Werte vom kleinsten zum größten durch und schreiben Sie jeden Wert
vinsgesamtcount[v]-mal in die Ausgabe.
Beispiel für [4, 2, 2, 8, 3, 3, 1]:
- Zählen Sie jeden Wert: 1 erscheint einmal, 2 zweimal, 3 zweimal, 4 einmal, 8 einmal.
- In der richtigen Reihenfolge wiederaufbauen: [1, 2, 2, 3, 3, 4, 8].
Es wurden keine Vergleiche angestellt: Der Wert selbst hat entschieden, wohin jedes Element gehört.
Probier es selbst
Diese Lektion enthält keine Programmieraufgabe.
Teste dich selbstDiese Lektion enthält ein kurzes Quiz. Starte die Lektion, um es zu beantworten und deinen Fortschritt zu speichern.
Alle Lektionen in Counting Sort - DSA-Serie
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity