Lernen Sie die Prinzipien und die Zeitkomplexitätsanalyse des Zählsortieralgorithmus in PHP kennen.

Lernen Sie die Prinzipien und die Zeitkomplexitätsanalyse des Zählsortieralgorithmus in PHP kennen.

Die Zählsortierung ist ein nicht vergleichender Sortieralgorithmus, der für Situationen geeignet ist, in denen der Datenbereich klein und bekannt ist. Seine Grundidee besteht darin, die Anzahl der Vorkommen jedes Elements zu zählen und es dann in das Ausgabearray einzutragen, um eine Sortierung zu erreichen. In diesem Artikel werden die Prinzipien, Schritte und Zeitkomplexitätsanalyse der Zählsortierung vorgestellt und spezifische PHP-Codebeispiele bereitgestellt.

1. Prinzip:
   Das Prinzip der Zählsortierung ist relativ einfach. Angenommen, das zu sortierende Array ist ein Array und der Elementbereich ist [0, k]. Wir müssen zunächst ein Zählarray count mit der Größe k+1 erstellen, um die Anzahl der Vorkommen jedes Elements zu zählen. Beim Durchlaufen des ursprünglichen Arrays werden die Elemente gezählt und im Zählarray gespeichert. Anschließend akkumulieren wir nacheinander die Elemente im Zählarray, um die Position des Elements im Ausgabearray zu bestimmen. Abschließend wird das ursprüngliche Array-Array durchlaufen und jedes Element an der entsprechenden Position (gemäß dem Index in count) platziert, um die Sortierung abzuschließen.
2. Schritte:
3. Erstellen Sie ein Zählarray count der Größe k+1 und initialisieren Sie es auf 0.
4. Durchlaufen Sie das ursprüngliche Array-Array, zählen Sie die Anzahl der Vorkommen jedes Elements und speichern Sie es im Zählarray.
5. Akkumulieren Sie das Zählarray, um die Position jedes Elements im Ausgabearray zu bestimmen.
6. Erstellen Sie eine Ausgabe-Array-Ausgabe mit derselben Größe wie das ursprüngliche Array.
7. Durchlaufen Sie das ursprüngliche Array-Array erneut und platzieren Sie jedes Element entsprechend dem Index im Zählarray im Ausgabearray.
8. Die Ausgabe des Ausgabearrays ist das Ergebnis nach der Sortierung.
9. Zeitliche Komplexitätsanalyse:
10. Die zeitliche Komplexität der Erstellung des Zählarrays beträgt O(k).
11. Die zeitliche Komplexität des Durchlaufens des ursprünglichen Arrays und des Zählens der Vorkommen jedes Elements beträgt O(n).
12. Die zeitliche Komplexität der Akkumulation des Zählarrays beträgt O(k).
13. Die zeitliche Komplexität der Erstellung des Ausgabearrays beträgt O(n).
14. Die Zeitkomplexität für das erneute Durchlaufen des ursprünglichen Arrays und das Platzieren von Elementen im Ausgabearray beträgt O(n).
15. Die Gesamtzeitkomplexität beträgt O(k) + O(n) + O(k) + O(n) + O(n), was zu O(n + k) vereinfacht wird.

Das Folgende ist ein Codebeispiel für die Verwendung der PHP-Sprache zur Implementierung des Zählsortieralgorithmus:

function countingSort($array)
{
    $maxValue = max($array);
    $count = array_fill(0, $maxValue + 1, 0);
    $n = count($array);

    foreach ($array as $value) {
        $count[$value]++;
    }

    for ($i = 1; $i <= $maxValue; $i++) {
        $count[$i] += $count[$i - 1];
    }

    $output = array_fill(0, $n, 0);

    for ($i = $n - 1; $i >= 0; $i--) {
        $output[$count[$array[$i]] - 1] = $array[$i];
        $count[$array[$i]]--;
    }

    return $output;
}

$array = [4, 2, 0, 1, 3, 2, 1]; // 待排序数组
$sortedArray = countingSort($array);
print_r($sortedArray);

Das Obige ist der Inhalt des Erlernens der Prinzipien und der Zeitkomplexitätsanalyse des Zählsortieralgorithmus in PHP. Ich hoffe, dies hilft Ihnen, die Zählsortierung zu verstehen.

Das obige ist der detaillierte Inhalt vonLernen Sie die Prinzipien und die Zeitkomplexitätsanalyse des Zählsortieralgorithmus in PHP kennen.. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!