So implementieren Sie den Algorithmus der umgekehrten Reihenfolge mit PHP

So implementieren Sie den Reverse-Sequence-Algorithmus in PHP

In der Informatik wird eine Reverse-Sequenz in einer Sequenz bezeichnet, wenn i cb3da72cd3ca08bff7e4a9624b877f31 . Die Lösung von Problemen in umgekehrter Reihenfolge ist von großer praktischer Bedeutung und findet Anwendung in Bereichen wie der Optimierung von Sortierproblemen und der Datenanalyse.

In diesem Artikel stellen wir vor, wie Sie mit der Programmiersprache PHP den Reverse-Pair-Algorithmus implementieren, um dieses häufige Problem besser zu verstehen und zu meistern.

Zuerst müssen wir darüber nachdenken, wie man Paare in umgekehrter Reihenfolge berechnet. Ein einfacher Ansatz besteht darin, zwei verschachtelte Schleifen zu verwenden und jedes Mal alle Elementpaare zu vergleichen. Wenn die Bedingung ai > aj erfüllt ist, erhöhen Sie den Zähler des umgekehrten Reihenfolgepaars. Die zeitliche Komplexität dieser Methode beträgt jedoch O(n^2) und ist nicht für große Datensätze geeignet.

Eine weitere effizientere Methode ist die Verwendung des Merge-Sort-Algorithmus. Die Grundidee dieses Algorithmus besteht darin, eine Sequenz in kleinere Teilsequenzen zu zerlegen und diese dann zu einer größeren sortierten Sequenz zusammenzuführen. Während des Zusammenführungsprozesses können wir die Anzahl der Paare problemlos in umgekehrter Reihenfolge zählen.

Das Folgende ist unser Beispielcode für die Implementierung des Reverse-Order-Pair-Algorithmus mithilfe der Programmiersprache PHP:

function mergeSortCount(&$arr) {
    $temp = array();
    $count = 0;
    $length = count($arr);
    $temp = array_fill(0, $length, 0); // 创建一个临时数组用于存储合并过程中的结果

    $count = mergeSort($arr, $temp, 0, $length - 1); // 调用真正的归并排序函数

    return $count;
}

function mergeSort(&$arr, &$temp, $left, $right) {
    $count = 0;
    if ($left < $right) {
        $mid = floor(($left + $right) / 2); // 找到中间位置
        $count += mergeSort($arr, $temp, $left, $mid); // 递归地对左子数组进行排序
        $count += mergeSort($arr, $temp, $mid + 1, $right); // 递归地对右子数组进行排序
        $count += merge($arr, $temp, $left, $mid + 1, $right); // 合并左右子数组，并计算逆序对数量
    }
    return $count;
}

function merge(&$arr, &$temp, $left, $mid, $right) {
    $count = 0;
    $i = $left; // 左子数组起始位置
    $j = $mid; // 右子数组起始位置
    $k = $left; // 合并后的数组起始位置

    while ($i <= $mid - 1 && $j <= $right) {
        if ($arr[$i] <= $arr[$j]) {
            $temp[$k++] = $arr[$i++];
        } else {
            $temp[$k++] = $arr[$j++];
            $count += $mid - $i;
        }
    }

    while ($i <= $mid - 1) {
        $temp[$k++] = $arr[$i++];
    }

    while ($j <= $right) {
        $temp[$k++] = $arr[$j++];
    }

    for ($i = $left; $i <= $right; $i++) {
        $arr[$i] = $temp[$i];
    }

    return $count;
}

// 测试示例
$arr = array(3, 1, 2, 4, 5);
$count = mergeSortCount($arr);
echo "逆序对的数量：" . $count;

Der obige Code definiert zunächst eine mergeSortCount-Funktion, die ein Array als Parameter akzeptiert und zurückgibt die Anzahl der Paare in umgekehrter Reihenfolge. In dieser Funktion erstellen wir ein temporäres Array temp, initialisieren einen Zähler count und zeichnen die Länge des Arrays length auf. mergeSortCount函数，该函数接受一个数组作为参数，并返回逆序对的数量。在这个函数中，我们创建了一个临时数组temp，并初始化一个计数器count，以及记录数组长度length。

接下来，我们调用mergeSort函数进行实际的归并排序。mergeSort函数接受一个左闭区间$left和一个右闭区间$right作为参数，在每次递归调用中，它将分割数组并递归地对子数组进行排序，然后调用merge函数来合并子数组并计算逆序对的数量。

在merge函数中，我们使用三个指针$i、$j和$k，对左、右子数组和合并后的数组进行遍历。如果左子数组的当前元素小于或等于右子数组的当前元素，则将左子数组的当前元素放入临时数组中，并将$i和$k指针向后移动一位。如果右子数组的当前元素小于左子数组的当前元素，则将右子数组的当前元素放入临时数组中，并将$j和$k指针向后移动一位。在这个过程中，如果出现右子数组的当前元素小于左子数组的当前元素，则计数器$count加上左子数组当前位置到中间位置的元素个数（因为左子数组已经有序）。

最后，我们将临时数组$temp中的元素复制回原始数组$arr，然后返回计数器$count。

在最后的测试示例中，我们定义了一个包含5个整数的数组，并调用mergeSortCount

Als nächstes rufen wir die Funktion mergeSort auf, um die eigentliche Zusammenführungssortierung durchzuführen. Die Funktion mergeSort akzeptiert ein links geschlossenes Intervall $left und ein rechts geschlossenes Intervall $right als Parameter. Bei jedem rekursiven Aufruf wird das Array aufgeteilt und sortieren Sie die Subarrays rekursiv. Rufen Sie dann die Funktion merge auf, um die Subarrays zusammenzuführen und die Anzahl der umgekehrten Paare zu zählen.

In der Funktion merge verwenden wir drei Zeiger $i, $j und $k für The Linke und rechte Subarrays sowie das zusammengeführte Array werden durchlaufen. Wenn das aktuelle Element des linken Subarrays kleiner oder gleich dem aktuellen Element des rechten Subarrays ist, fügen Sie das aktuelle Element des linken Subarrays in ein temporäres Array ein und fügen Sie $i und $ hinzu k code>Der Zeiger bewegt sich um eine Position zurück. Wenn das aktuelle Element des rechten Subarrays kleiner ist als das aktuelle Element des linken Subarrays, fügen Sie das aktuelle Element des rechten Subarrays in ein temporäres Array ein und fügen Sie <code>$j und $k hinzu. Code> Der Zeiger bewegt sich um eine Position zurück. Wenn in diesem Prozess das aktuelle Element des rechten Subarrays kleiner als das aktuelle Element des linken Subarrays ist, wird der Zähler <code>$count zur Anzahl der Elemente von der aktuellen Position des linken Subarrays bis addiert die mittlere Position (weil das linke Subarray Das Array ist bereits sortiert). 🎜🎜Schließlich kopieren wir die Elemente im temporären Array $temp zurück in das ursprüngliche Array $arr und geben dann den Zähler $count zurück . 🎜🎜Im letzten Testbeispiel haben wir ein Array mit 5 Ganzzahlen definiert und die Funktion mergeSortCount aufgerufen, um die Anzahl der Paare in umgekehrter Reihenfolge zu zählen. In diesem Beispiel beträgt die Anzahl der Paare in umgekehrter Reihenfolge 2. 🎜🎜Anhand der obigen Codebeispiele können wir sehen, dass es nicht schwierig ist, den Reverse-Pair-Algorithmus mit der Programmiersprache PHP zu implementieren. Die Kernidee des Zusammenführungssortierungsalgorithmus besteht darin, die Sequenz in kleinere Teilsequenzen zu zerlegen, die Sortierung durch Zusammenführungsoperationen zu implementieren und gleichzeitig die Anzahl der Paare in umgekehrter Reihenfolge zu berechnen. Dies ist ein effizienter und häufig verwendeter Sortieralgorithmus, der auf verschiedene praktische Probleme angewendet werden kann. 🎜

Das obige ist der detaillierte Inhalt vonSo implementieren Sie den Algorithmus der umgekehrten Reihenfolge mit PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!