Comment implémenter le tri par sélection en utilisant Python

Le tri par sélection est un algorithme de tri simple. Son idée de base est de trouver la valeur minimale parmi les éléments non triés, puis de la placer à la fin des éléments triés. Répétez ce processus jusqu'à ce que tous les éléments soient triés. Dans cet article, nous présenterons comment implémenter le tri par sélection à l'aide de Python.

Tout d’abord, nous devons clairement sélectionner les étapes de tri.

1. Tout d'abord, recherchez le plus petit élément de la séquence non triée, puis stockez-le au début de la séquence.
2. Ensuite, continuez à rechercher le plus petit élément parmi les éléments non triés restants, puis stockez-le à la fin de la séquence triée.
3. Répétez l'étape 2 jusqu'à ce que tous les éléments aient été triés.

Sur la base des étapes ci-dessus, nous pouvons commencer à utiliser Python pour implémenter l'algorithme de tri par sélection.

Étapes de mise en œuvre :

1. Définissez une fonction selection_sort() qui reçoit une liste en paramètre.
2. Dans la fonction, utilisez une boucle for pour parcourir la liste et obtenir la longueur de la liste len(arr).
3. Ensuite, utilisez une autre boucle for pour trouver le plus petit élément du tableau non trié.
4. Après avoir trouvé le plus petit élément, échangez-le avec le i-ième élément de la liste actuelle.
5. Répétez les étapes 3 et 4 jusqu'à ce que tous les éléments soient triés.

Ce qui suit est l'implémentation spécifique du code :

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i+1, n):
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Dans le code ci-dessus, nous définissons une fonction selection_sort() qui accepte une liste comme paramètre. Une boucle for est utilisée à l'intérieur de la fonction pour parcourir la liste et obtenir la longueur de la liste. Ensuite, utilisez une autre boucle for pour trouver le plus petit élément du tableau non trié. Une fois le plus petit élément trouvé, échangez-le avec le i-ème élément de la liste actuelle. Enfin, répétez les étapes 3 et 4 jusqu'à ce que tous les éléments soient triés.

Maintenant, nous pouvons utiliser la fonction selection_sort() pour le tester :

arr = [64, 25, 12, 22, 11]

print("原始数组：")
print(arr)

s_arr = selection_sort(arr)

print("排序后的数组：")
print(s_arr)

Le résultat de sortie est :

原始数组：
[64, 25, 12, 22, 11]
排序后的数组：
[11, 12, 22, 25, 64]

Résumé

Le tri par sélection est un algorithme de tri simple mais très efficace, sa complexité temporelle est O(n²). Dans le processus de programmation réel, nous pouvons utiliser Python pour implémenter l'algorithme de tri par sélection.

Grâce au code de démonstration ci-dessus, nous pouvons voir que l'implémentation par Python de l'algorithme de tri est très simple. Si vous n'êtes pas entré en contact avec des algorithmes de tri lors de votre apprentissage de Python, cet article peut vous aider.

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!