Die Zählsart ist ein stabiler Sortieralgorithmus. Die Zählsortierung verwendet ein zusätzliches Array count_arr, wobei das I-te-Element die Anzahl der Elemente mit einem Wert ist. Laut Array Count_arr sind die Elemente in arr an der richtigen Position angeordnet.
Es ist in vier Schritte unterteilt:
1. Finden Sie die größten und kleinsten Elemente im Array, die sortiert werden sollen
2. Statistik Die Anzahl der Male jedes Element
3. akkumulieren alle Zählungen (ab dem ersten Element in count_arr, jedes Element und das vorherige Element werden hinzugefügt)
4. Umgekehrt das ursprüngliche Array: Legen Sie jedes Element I in das Element count_arr (i) des Neuarrays und subtrahieren Sie für jedes Element count_arr (i) um 1.
Beispiel:
Die Codekopie lautet wie folgt:
/**
* Zählsortierung ist ein nicht vergleichbarer Sortieralgorithmus.
* Dieser Algorithmus wurde 1954 von Harold H. Seward vorgeschlagen.
* Sein Vorteil ist, dass beim Sortieren von Ganzzahlen innerhalb eines bestimmten Bereichs,
* Seine Komplexität ist ο (n+k) (wobei k der Bereich der Ganzzahlen ist),
* Schneller als jeder Vergleichssortierungsalgorithmus.
*
*/
Funktion countSort (arr, min, max) {
var i, z = 0, count = [];
für (i = min; i <= max; i ++) {
zählen [i] = 0;
}
für (i = 0; i <arr.length; i ++) {
zählen [arr [i]] ++;
}
für (i = min; i <= max; i ++) {
while (count [i]-> 0) {
arr [z ++] = i;
}
}
arr zurückgeben;
}
// prüfen
var i, arr = [];
für (i = 0; i <100; i ++) {
arr.push (math.floor (math.random () * (141));
}
CountSort (arr, 0, 140);