Quel est le principe et l'implémentation de l'algorithme de tri par insertion en PHP ?

Le principe et l'implémentation de l'algorithme de tri par insertion en PHP

Le tri par insertion est un algorithme de tri courant. Son idée principale est d'insérer un élément dans une séquence déjà ordonnée en fonction de sa taille. En PHP, nous pouvons implémenter l'algorithme de tri par insertion via un simple échange numérique. Cet article présentera en détail le principe et la mise en œuvre du tri par insertion et fournira des exemples de code spécifiques.

Principe :

1. Sélectionnez un élément de la séquence non triée et insérez-le dans la position appropriée de la séquence triée.
2. Déterminez où l'élément doit être inséré en comparant l'élément à insérer avec les éléments de la séquence triée.
3. Répétez les étapes 1 et 2 jusqu'à ce que la séquence non triée soit vide.

Méthode d'implémentation :
Ce qui suit est un exemple de code pour implémenter l'algorithme de tri par insertion en PHP :

function insertionSort($array)
{
    $length = count($array);

    for ($i = 1; $i < $length; $i++) {
        $key = $array[$i];
        $j = $i - 1;

        // 将当前元素与已排序序列中的元素比较，找到合适的插入位置
        while ($j >= 0 && $array[$j] > $key) {
            $array[$j + 1] = $array[$j];
            $j--;
        }

        $array[$j + 1] = $key;
    }

    return $array;
}

// 示例用法
$data = [4, 2, 7, 1, 9, 5];
$sortedData = insertionSort($data);
print_r($sortedData);

Dans le code ci-dessus, la fonction insertionSort accepte un tableau comme paramètre et renvoie un tri tableau. Pendant le processus de tri, nous utilisons une variable $key pour enregistrer l'élément actuel à insérer. Dans chaque comparaison, l'élément plus grand que l'élément dans la séquence triée est déplacé d'une position vers la droite jusqu'à ce qu'un élément soit plus grand que l'élément dans la séquence triée. la position d'insertion appropriée est trouvée. insertionSort函数接受一个数组作为参数，并返回一个排序后的数组。在排序过程中，我们使用一个$key变量保存当前待插入的元素，在每次比较中，将已排序序列中大于该元素的元素向右移动一位，直到找到合适的插入位置。

示例用法中，我们定义了一个待排序的数组$data，并将其传递给insertionSort函数。最后，通过print_r($sortedData)

Résumé :

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!