Implementierungsprinzip des Zählsortieralgorithmus in PHP

Prinzip der Implementierung des Zählsortieralgorithmus in PHP

Die Zählsortierung ist ein nicht vergleichender Sortieralgorithmus. Seine Grundidee besteht darin, das Vorkommen jedes Elements zu zählen und es dann entsprechend der Größe des Elements an einer geordneten Position zu platzieren. Die Zählsortierung eignet sich für Situationen, in denen der Elementbereich klein ist und viele wiederholte Elemente vorhanden sind. Die zeitliche Komplexität beträgt O (n) und ist ein effizienter Sortieralgorithmus.

Implementierungsprinzip:

1. Durchlaufen Sie zunächst das zu sortierende Array und ermitteln Sie die Maximal- und Minimalwerte, um die Größe des Zählarrays zu bestimmen.
2. Erstellen Sie ein Zählarray, dessen Länge der Differenz zwischen dem Maximalwert und dem Minimalwert plus 1 entspricht, und initialisieren Sie es auf 0.
3. Durchlaufen Sie das zu sortierende Array erneut, zählen Sie die Anzahl der Vorkommen jedes Elements und speichern Sie die Anzahl im Zählarray.
4. Führen Sie eine Akkumulationsoperation für das Zählarray durch, dh summieren Sie das Element an der aktuellen Position und das Element an der vorherigen Position.
5. Erstellen Sie ein temporäres Array mit derselben Länge wie das zu sortierende Array, um die Sortierergebnisse zu speichern.
6. Durchlaufen Sie das zu sortierende Array von hinten nach vorne und verwenden Sie den akkumulierten Wert im Zählarray, um die Elemente an den entsprechenden Positionen im temporären Array zu platzieren.
7. Kopieren Sie die Elemente im temporären Array in das ursprüngliche Array, um die Sortierung abzuschließen.

Das Folgende ist ein PHP-Codebeispiel:

function countSort($arr) {
    $min = min($arr); // 寻找最小值
    $max = max($arr); // 寻找最大值
    $count = array_fill($min, $max - $min + 1, 0); // 创建计数数组

    foreach ($arr as $num) {
        $count[$num]++; // 统计每个元素的出现次数
    }

    for ($i = $min + 1; $i <= $max; $i++) {
        $count[$i] += $count[$i - 1]; // 计算累加值
    }

    $temp = array_fill(0, count($arr), 0); // 创建临时数组

    for ($i = count($arr) - 1; $i >= 0; $i--) {
        $temp[--$count[$arr[$i]]] = $arr[$i]; // 将元素放置到临时数组中的相应位置上
    }

    for ($i = 0; $i < count($arr); $i++) {
        $arr[$i] = $temp[$i]; // 将临时数组中的元素复制到原始数组中
    }

    return $arr;
}

// 测试示例
$arr = [8, 3, 5, 4, 7, 6, 1, 6, 4, 4];
$result = countSort($arr);
echo implode(' ', $result); // 输出：1 3 4 4 4 5 6 6 7 8

Das Obige ist das Implementierungsprinzip des Zählsortieralgorithmus in PHP, indem die Anzahl der Vorkommen jedes Elements gezählt und die Elemente dann entsprechend geordnet werden Zahl, das sortierte Array ist eine Sortierung. Dieser Algorithmus eignet sich für Situationen, in denen der Elementbereich klein ist und viele Elemente wiederholt werden und der Sortiervorgang in kürzerer Zeit abgeschlossen werden kann.

Das obige ist der detaillierte Inhalt vonImplementierungsprinzip des Zählsortieralgorithmus in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!