Comment implémenter un algorithme de tri rapide en Python ?

Comment implémenter un algorithme de tri rapide en Python ?

Le tri rapide est un algorithme de tri courant et efficace qui peut trier une liste de n éléments avec une complexité temporelle de O(n log n) en moyenne. Cet article explique comment utiliser Python pour écrire un exemple de code de l'algorithme de tri rapide.

L'idée de base du tri rapide est de sélectionner un élément comme référence (généralement le premier élément de la liste), de diviser la liste en deux sous-séquences, de sorte que tous les éléments de la sous-séquence de gauche soient inférieurs à la référence, et tous les éléments de la bonne sous-séquence sont supérieurs à la référence. Ensuite, les sous-séquences gauche et droite sont rapidement triées de manière récursive jusqu'à ce que la longueur de la sous-séquence soit 1 ou 0 et que le tri soit terminé.

Ce qui suit est un exemple de code d'implémentation de l'algorithme de tri rapide en Python :

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]  # 选择第一个元素作为基准
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quicksort(less) + [pivot] + quicksort(greater)

Le code ci-dessus définit une fonction appelée tri rapide, qui accepte un arr de liste en entrée et renvoie la liste triée. Premièrement, si la longueur de la liste d'entrée est inférieure ou égale à 1, la liste est renvoyée directement, car une liste d'une longueur de 0 ou 1 est déjà ordonnée.

Ensuite, sélectionnez le premier élément de la liste comme pivot de base, et ajoutez les autres éléments de la liste aux deux listes nouvellement créées, inférieures et supérieures, afin que les éléments en moins soient inférieurs ou égaux au pivot, et les éléments en plus grand sont supérieurs au pivot.

Enfin, la fonction de tri rapide est appelée de manière récursive pour trier rapidement de moins en plus, et les triés moins, pivot et supérieur sont assemblés pour obtenir le résultat de tri final.

Ce qui suit est un exemple de test de tri rapide :

arr = [4, 2, 8, 5, 1, 6, 7, 3]
sorted_arr = quicksort(arr)
print(sorted_arr)  # 输出：[1, 2, 3, 4, 5, 6, 7, 8]

Dans l'exemple ci-dessus, la liste d'entrée arr contient 8 entiers et le résultat du tri obtenu après le tri rapide est [1, 2, 3, 4, 5, 6 , 7, 8].

Résumé :
À travers les exemples de code ci-dessus, nous pouvons voir qu'il est relativement simple d'implémenter l'algorithme de tri rapide en Python. En sélectionnant l'élément de référence, la liste est divisée en deux sous-séquences, puis les sous-séquences sont triées de manière récursive, et enfin une liste ordonnée est obtenue. Le tri rapide est un algorithme de tri efficace largement utilisé dans des applications 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!