Comment implémenter un algorithme de tri par sélection avec PHP

Comment implémenter un algorithme de tri par sélection avec PHP

Le tri par sélection est un algorithme de tri simple et intuitif. Son idée de base est de sélectionner le plus petit (ou le plus grand) élément parmi les éléments de données à trier à chaque passe et de le stocker dans le résultat. La position de départ de la séquence jusqu'à ce que tous les éléments de données à trier soient disposés. Ci-dessous, nous allons implémenter l'algorithme de tri par sélection via le code PHP et l'expliquer en détail.

Tout d'abord, jetons un coup d'œil aux étapes de mise en œuvre de l'algorithme de tri par sélection :

1. Parcourez l'ensemble du tableau à trier, en prenant le premier élément comme valeur minimale (par défaut).
2. En fonction de la valeur minimale, parcourez les éléments restants, recherchez les éléments plus petits que la valeur minimale actuelle et mettez à jour la valeur minimale.
3. Échangez la valeur minimale avec la position parcourue actuelle.
4. Répétez les étapes 2 et 3 jusqu'à ce que le tri du tableau soit terminé.

Ce qui suit est un exemple de code utilisant PHP pour implémenter l'algorithme de tri par sélection :

function selectionSort($arr) {
    $len = count($arr);
    
    for($i = 0; $i < $len - 1; $i++) {
        $minIndex = $i;
        
        for($j = $i + 1; $j < $len; $j++) {
            if($arr[$j] < $arr[$minIndex]) {
                $minIndex = $j;
            }
        }
        
        // Swap the minimum value with the current position
        $temp = $arr[$minIndex];
        $arr[$minIndex] = $arr[$i];
        $arr[$i] = $temp;
    }
    
    return $arr;
}

// Test the selectionSort function
$testArray = [64, 25, 12, 22, 11];
echo "Before sorting: ";
print_r($testArray);
echo "After sorting: ";
print_r(selectionSort($testArray));

Exécutez le code ci-dessus, le résultat de sortie sera :

Before sorting: Array ( [0] => 64 [1] => 25 [2] => 12 [3] => 22 [4] => 11 )
After sorting: Array ( [0] => 11 [1] => 12 [2] => 22 [3] => 25 [4] => 64 )

C'est le résultat du tri du tableau via l'algorithme de tri par sélection. Expliquons ensuite le processus de mise en œuvre spécifique du code.

Dans le code, nous définissons une fonction nommée selectionSort, qui accepte un tableau à trier en paramètre et renvoie le tableau trié. selectionSort的函数，它接受一个待排序的数组作为参数，并返回排序后的数组。

首先，我们使用count函数获取到数组的长度，并将其赋值给变量$len。然后，我们使用两个嵌套的for循环来遍历整个数组。

在外部的for循环中，我们定义了一个变量$minIndex用来保存当前最小值的索引，默认为当前的循环变量$i。在内部的for循环中，我们通过比较当前元素和最小值的大小来更新最小值的索引。

当内部的for循环结束后，我们将当前最小值与当前的位置进行交换。通过使用一个临时变量$temp

Tout d'abord, nous utilisons la fonction count pour obtenir la longueur du tableau et l'attribuons à la variable $len. Nous utilisons ensuite deux boucles for imbriquées pour parcourir l'ensemble du tableau.

Dans la boucle externe for, nous définissons une variable $minIndex pour enregistrer l'index de la valeur minimale actuelle, qui est par défaut la variable de boucle actuelle $i . Dans la boucle interne for, nous mettons à jour l'index de la valeur minimale en comparant la taille de l'élément actuel et la valeur minimale.

Lorsque la boucle interne for se termine, nous échangeons la valeur minimale actuelle avec la position actuelle. Échangez les valeurs de deux éléments en utilisant une variable temporaire $temp.

Enfin, nous renvoyons le tableau trié. 🎜🎜La complexité temporelle de l'algorithme de tri par sélection est O(n^2), où n est la longueur du tableau à trier. En effet, chaque parcours doit trouver la valeur minimale parmi les éléments restants et effectuer une opération d'échange. Quel que soit l’état initial du tableau, n-1 parcours doivent être effectués. 🎜🎜J'espère que grâce aux exemples de code et aux explications de cet article, vous pourrez mieux comprendre le processus de mise en œuvre de l'algorithme de tri par sélection et pouvoir l'utiliser de manière flexible dans le développement réel. 🎜

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!