Français
Français
Le tri de sélection simple est un algorithme de tri intuitif et couramment utilisé qui peut traiter efficacement diverses données. L'idée principale est de sélectionner la valeur minimale parmi les éléments à tri à chaque fois et de le placer à la fin de la séquence triée. Le processus spécifique est: la première fois sélectionne le plus petit élément de l'ensemble du tableau et échange la première position, la deuxième fois sélectionne la plus petite valeur dans les éléments restants et échange la deuxième position, et ainsi de suite jusqu'à ce que tous les éléments soient triés.
Obtenez d'abord la longueur du tableau N, puis effectuez une opération de sélection du ronde N-1. Chaque cycle de sélection trouve la valeur minimale de la partie non triée et l'échange avec l'élément à la position de début du tour actuel pour atteindre l'ordre local et enfin terminer le tri global.
Ce qui suit est un exemple de code pour le tri de sélection simple de l'implémentation PHP, ce qui facilite la compréhension du processus d'exécution spécifique de l'algorithme:
function selectionSort(&$arr)
{
$len=count($arr);
for($i=0;$i<$len-1;$i++)
{
$min=$i; // Supposons que l'élément actuel est la position de valeur minimale
for($j=$i+1;$j<$len;$j++) // Trouver des valeurs plus petites à partir d'éléments suivants
{
if($arr[$j]<$arr[$min])
{
$min=$j; // Mettre à jour la position de valeur minimale
}
}
if($min!=$i) // Échanger des éléments lorsque la position change
{
$temp=$arr[$min];
$arr[$min]=$arr[$i];
$arr[$i]=$temp;
}
}
}
Le tri de sélection simple nécessite des cycles de sélection n-1, chaque tour trouve la valeur minimale entre les éléments restants, donc le nombre de comparaisons est d'environ N² / 2, et le nombre de mouvements dépend de l'ordre des données initial. La complexité du temps totale est O (n²). Néanmoins, lorsque le volume de données est petit ou essentiellement commandé, l'algorithme est toujours pratique.
Cet algorithme n'utilise qu'une seule variable temporaire pour aider à l'échange, avec des frais généraux d'espace extrêmement petits et une complexité spatiale d'O (1).
Le tri de sélection simple est un algorithme de tri instable. Les mêmes éléments peuvent modifier l'ordre relatif en raison des positions d'échange pendant le processus de tri. Par exemple, dans la séquence 5 8 5 2 9, après le premier cycle d'échanges, le plus petit élément 2 avec le premier élément 5, le même ordre de position de 5 est perturbé.
