Implementierung des PHP-Zählsortieralgorithmus (Codebeispiel)

Counting Sort ist ein Algorithmus zum Sortieren einer Reihe von Objekten basierend auf kleinen Ganzzahlschlüsseln. Es bestimmt die Position jedes Schlüsselwerts in der Ausgabesequenz, indem es die Anzahl der Objekte mit unterschiedlichen Schlüsselwerten zählt und diese Zahlen arithmetisch verarbeitet.

Die Zählsortierung ist nur dann geeignet, wenn die Änderung des Schlüssels nicht größer ist als die Gesamtzahl der Elemente. Es wird häufig als Unterprogramm eines anderen Sortieralgorithmus (Radix-Sortierung) verwendet, der größere Schlüssel effizient verarbeiten kann.

Kurz gesagt, Counting Sort ist ein stabiler linearer Zeitsortierungsalgorithmus. Bei der Zählsortierung wird ein zusätzliches Array C verwendet, wobei das i-te Element die Anzahl der Elemente ist, deren Wert gleich i im zu sortierenden Array A ist. Ordnen Sie dann die Elemente in A entsprechend der Anordnung C an der richtigen Position an.

Die üblichen Implementierungsschritte des Zählsortieralgorithmus sind:

1. Finden Sie die größten und kleinsten Elemente im Array, die sortiert werden sollen 2. Zählen Sie die Anzahl der Vorkommen jedes Elements mit dem Wert i im Array und speichern Sie es im i-ten Element von Array C.

3. Sammeln Sie alle Zählungen (beginnend mit dem ersten Element in C). jedes Element zum vorherigen Element hinzufügen);

4. Füllen Sie das Zielarray in umgekehrter Reihenfolge: Platzieren Sie jedes Element i im C[i]-ten Element des neuen Arrays und fügen Sie jeweils C[i] hinzu Zeit, in der ein Element platziert wird.

<?php
function counting_sort($my_array, $min, $max)
{
    $count = array();
    for($i = $min; $i <= $max; $i++)
    {
        $count[$i] = 0;
    }

    foreach($my_array as $number)
    {
        $count[$number]++;
    }
    $z = 0;
    for($i = $min; $i <= $max; $i++) {
        while( $count[$i]-- > 0 ) {
            $my_array[$z++] = $i;
        }
    }
    return $my_array;
}
$test_array = array(3, 0, 2, 5, -1, 4, 1);
echo "原始数组 :\n";
echo implode(&#39;, &#39;,$test_array );
echo "\n排序后数组\n:";
echo implode(&#39;, &#39;,counting_sort($test_array, -1, 5)). PHP_EOL;

原始数组 : 3, 0, 2, 5, -1, 4, 1 
排序后数组 :-1, 0, 1, 2, 3, 4, 5

》Dieser Artikel ist eine Einführung in die Implementierungsmethode des PHP-Zählsortieralgorithmus. Ich hoffe, er wird Freunden in Not hilfreich sein.

Das obige ist der detaillierte Inhalt vonImplementierung des PHP-Zählsortieralgorithmus (Codebeispiel). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!