Comment implémenter l'algorithme d'ordre inverse en utilisant PHP

Comment implémenter l'algorithme de séquence inverse en PHP

En informatique, une paire de séquence inverse est dans une séquence pour deux éléments ai et aj, si i < droite. La résolution du problème de l’ordre inverse revêt une grande importance pratique et a des applications dans des domaines tels que l’optimisation des problèmes de tri et l’analyse des données.

Dans cet article, nous présenterons comment utiliser le langage de programmation PHP pour implémenter l'algorithme d'ordre inverse afin de mieux comprendre et maîtriser ce problème courant.

Tout d’abord, nous devons réfléchir à la façon de calculer les paires d’ordre inverse. Une approche simple consiste à utiliser deux boucles imbriquées, en comparant à chaque fois toutes les paires d’éléments. Si la condition ai > aj est remplie, alors incrémentez le compteur de la paire inversée. Cependant, la complexité temporelle de cette méthode est O(n^2) et ne convient pas aux grands ensembles de données.

Une autre méthode plus efficace consiste à utiliser l'algorithme de tri par fusion. L'idée de base de cet algorithme est de décomposer une séquence en sous-séquences plus petites, puis de les fusionner en une séquence triée plus grande. Pendant le processus de fusion, nous pouvons facilement compter le nombre de paires dans l’ordre inverse.

Voici notre exemple de code pour implémenter l'algorithme de paire d'ordre inverse à l'aide du langage de programmation 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;

Le code ci-dessus définit d'abord une fonction mergeSortCount, qui accepte un tableau comme paramètre et renvoie le nombre de paires d'ordre inverse. Dans cette fonction, nous créons un tableau temporaire temp, initialisons un compteur count et enregistrons la longueur du tableau length. mergeSortCount函数，该函数接受一个数组作为参数，并返回逆序对的数量。在这个函数中，我们创建了一个临时数组temp，并初始化一个计数器count，以及记录数组长度length。

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

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

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

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

Ensuite, nous appelons la fonction mergeSort pour effectuer le tri par fusion proprement dit. La fonction mergeSort accepte un intervalle fermé à gauche $left et un intervalle fermé à droite $right comme paramètres. Dans chaque appel récursif, elle divisera le tableau. et triez récursivement les sous-tableaux, puis appelez la fonction merge pour fusionner les sous-tableaux et compter le nombre de paires inversées.

Dans la fonction merge, nous utilisons trois pointeurs $i, $j et $k, pour Le les sous-tableaux gauche et droit et le tableau fusionné sont parcourus. Si l'élément actuel du sous-tableau gauche est inférieur ou égal à l'élément actuel du sous-tableau droit, placez l'élément actuel du sous-tableau gauche dans un tableau temporaire et ajoutez $i et $ k code>Le pointeur recule d'une position. Si l'élément actuel du sous-tableau droit est plus petit que l'élément actuel du sous-tableau gauche, placez l'élément actuel du sous-tableau droit dans un tableau temporaire et ajoutez <code>$j et $k code> Le pointeur recule d’une position. Dans ce processus, si l'élément actuel du sous-tableau droit est plus petit que l'élément actuel du sous-tableau gauche, le compteur <code>$count est ajouté au nombre d'éléments depuis la position actuelle du sous-tableau gauche jusqu'à la position médiane (car le sous-tableau gauche Le tableau est déjà trié). 🎜🎜Enfin, nous copions les éléments du tableau temporaire $temp dans le tableau d'origine $arr, puis renvoyons le compteur $count . 🎜🎜Dans le dernier exemple de test, nous avons défini un tableau contenant 5 entiers et appelé la fonction mergeSortCount pour compter le nombre de paires d'ordre inverse. Dans cet exemple, le nombre de paires inversées est de 2. 🎜🎜Grâce aux exemples de code ci-dessus, nous pouvons voir qu'il n'est pas difficile d'implémenter l'algorithme de paire inversée à l'aide du langage de programmation PHP. L'idée principale de l'algorithme de tri par fusion est de décomposer la séquence en sous-séquences plus petites, de mettre en œuvre le tri via des opérations de fusion et de calculer le nombre de paires d'ordre inverse en même temps. Il s’agit d’un algorithme de tri efficace et couramment utilisé qui peut être appliqué à divers problèmes pratiques. 🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!