Explication détaillée de l'implémentation du tri par sélection en Python

Explication détaillée de l'algorithme de tri par sélection en Python

Le tri par sélection est un algorithme de tri simple mais inefficace. Son idée de base est de trouver le plus petit (ou le plus grand) élément de la séquence à trier à chaque fois. fin de la séquence triée. En répétant ce processus jusqu'à ce que tous les éléments soient triés.

Les étapes du tri par sélection sont les suivantes :

1. Parcourez la séquence et trouvez le plus petit (ou le plus grand) élément.
2. Échangez l'élément le plus petit (ou le plus grand) avec l'élément à la position de traversée actuelle.
3. Répétez les étapes 1 et 2 jusqu'à ce que toute la séquence ait été parcourue.

Expliquons l'algorithme de tri par sélection en détail et donnons des exemples de code spécifiques.

Tout d'abord, nous définissons une fonction pour implémenter le tri par sélection :

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # 找到未排序序列中的最小元素的索引
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        # 将最小元素与当前遍历位置的元素交换
        arr[i], arr[min_index] = arr[min_index], arr[i]

Maintenant, testons l'effet du tri par sélection :

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("排序后的数组:")
for i in range(len(arr)):
    print(arr[i])

Exécutez le code ci-dessus, le résultat est le suivant :

排序后的数组:
11
12
22
25
64

Vous pouvez voir que le tri par sélection réussira. Le tableau est trié par ordre croissant.

La complexité temporelle du tri par sélection est O(n^2), où n est la longueur de la séquence à trier. En effet, chaque fois que vous devez parcourir tous les éléments de la séquence non triée pour trouver l'élément le plus petit (ou le plus grand), vous devez effectuer n comparaisons. Un total de n-1 tours de parcours doivent être effectués, la complexité temporelle est donc O(n^2).

Le tri par sélection est un algorithme de tri instable, c'est-à-dire que l'ordre relatif des mêmes éléments peut changer. En effet, le tri par sélection est implémenté en échangeant continuellement les positions des éléments. Par exemple, pour la séquence [3, 1, 3], le résultat possible après tri à l'aide de l'algorithme de tri par sélection est [1, 3, 3], et la position relative de l'élément 3 initialement identique a changé.

Bien que le tri par sélection soit moins efficace, sa mise en œuvre est simple et intuitive. Dans certains cas spécifiques, par exemple lorsque la séquence à trier est petite ou que les exigences de stabilité ne sont pas élevées, le tri par sélection peut être utilisé comme méthode de tri simple.

Pour résumer, le tri par sélection est un algorithme qui termine le tri en recherchant continuellement l'élément le plus petit (ou le plus grand) dans une séquence non triée et en l'échangeant avec l'élément à la position de parcours actuelle. Bien que la mise en œuvre soit simple, la complexité temporelle est élevée et instable. Dans les applications pratiques, les scénarios d’utilisation du tri par sélection sont relativement limités.

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!