Comment écrire un algorithme de tri par sélection en Python ?

Comment écrire un algorithme de tri par sélection en Python ?

Le tri par sélection est un algorithme de tri simple et intuitif. L'idée de base est de trouver le plus petit élément et de le placer à la fin de la partie triée, puis de continuer à trouver le plus petit élément de la partie non triée et de répéter ce processus jusqu'à la fin de la partie triée. le tableau est trié Terminer.

Nous allons maintenant présenter en détail comment écrire l'algorithme de tri par sélection en Python.

Tout d'abord, nous définissons une fonction select_sort pour implémenter le tri par sélection. Cette fonction reçoit un tableau en paramètre et trie le tableau d'origine. Deux boucles imbriquées sont utilisées à l'intérieur de la fonction, la boucle externe est utilisée pour parcourir le tableau et la boucle interne est utilisée pour trouver l'index du plus petit élément dans la partie non triée.

Le code est le suivant :

def select_sort(arr):
    n = len(arr)
    for i in range(n-1):
        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]

Ensuite, nous pouvons tester l'effet de l'algorithme de tri par sélection. Par exemple, trier un tableau d'entiers :

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

Le résultat courant est le suivant :

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

On peut voir que l'algorithme de tri par sélection trie avec succès le tableau d'entrée par ordre croissant.

La complexité temporelle de l'algorithme de tri par sélection est O(n^2). Quelles que soient les données d'entrée, sa complexité temporelle est la même. Par conséquent, dans les applications pratiques, l’algorithme de tri par sélection a une faible efficacité et n’est pas adapté aux tâches de tri de traitement de données à grande échelle.

Pour résumer, cet article présente comment écrire l'algorithme de tri par sélection en Python et donne des exemples de code spécifiques. J'espère que les lecteurs pourront maîtriser les principes de base et les méthodes de mise en œuvre de l'algorithme de tri par sélection en lisant cet article et seront capables de l'appliquer de manière flexible à des problèmes pratiques.

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!