Apprendre et implémenter l'algorithme de tri par sélection en Python

Comprendre le principe et la mise en œuvre du tri par sélection en Python

Selection Sort est un algorithme de tri simple et intuitif dont l'idée de base est de parcourir le tableau à chaque fois et de sélectionner le plus petit (ou le plus grand) dans la partie non triée. , échangez sa position avec le premier élément de la partie non triée, puis continuez à sélectionner l'élément le plus petit (ou le plus grand) de la partie non triée, et ainsi de suite, jusqu'à ce que l'ensemble du tableau soit trié. La complexité temporelle du tri par sélection est O(n^2) et il s'agit d'un algorithme de tri instable.

Ce qui suit utilise des exemples de code spécifiques pour illustrer le processus de mise en œuvre du tri par sélection.

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

Ce qui précède est le code d'implémentation de l'algorithme de tri par sélection. Nous expliquerons ensuite le principe et le processus de ce code étape par étape.

Tout d'abord, nous définissons une fonction selection_sort, qui reçoit un tableau arr à trier en paramètre.

Dans le corps de la fonction, nous obtenons d'abord la longueur n du tableau. Il s'agit d'itérer n-1 fois, car chaque itération mettra un plus petit élément dans la bonne position, donc le dernier élément n'a pas besoin d'être trié.

Ensuite, nous utilisons deux boucles for imbriquées pour effectuer le processus de tri de sélection. La boucle externe va de 0 à n-1, représentant la position de départ i de la pièce à trier.

La boucle intérieure va de i+1 à n, représentant l'élément j dans la partie à trier. Nous comparons j avec l'élément à la position de départ i. Si j est plus petit que l'élément à la position de départ i, min_idx est mis à jour en j, indiquant que j est l'index du plus petit élément trouvé jusqu'à présent.

Lorsque la boucle interne se terminera, nous échangerons la position du plus petit élément trouvé avec l'élément à la position de départ i, afin que l'itération en cours place le plus petit élément dans la bonne position.

Avec n-1 itérations, nous pouvons nous assurer que l'ensemble du tableau est trié par ordre croissant.

Ensuite, nous pouvons utiliser le code suivant pour tester 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], end=" ")

Le résultat de sortie est : 11 12 22 25 64, ce qui signifie que le tableau a été trié par ordre croissant.

En utilisation réelle, le tri par sélection est moins efficace, nous préférons donc utiliser d'autres algorithmes de tri plus efficaces, comme le tri rapide ou le tri par fusion. Cependant, le tri par sélection est un algorithme de tri simple et facile à comprendre, qui aide les débutants à comprendre les principes et les idées de base des algorithmes de tri.

Pour résumer, le tri par sélection consiste à sélectionner à chaque fois l'élément le plus petit (ou le plus grand) de la partie non triée, à le placer à la fin de la partie triée et, à travers plusieurs itérations, enfin à atteindre l'objectif de commander l'ensemble du tableau. La maîtrise du principe et de la mise en œuvre du tri par sélection est d'une grande importance pour une compréhension approfondie des algorithmes de tri et l'amélioration des capacités de programmation.

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!