Méthode de tri rapide de Python

Cet article présente principalement l'algorithme de tri rapide implémenté en Python, et analyse les principes, les méthodes de mise en œuvre et les techniques de fonctionnement associées du tri rapide Python sous forme d'exemples. Les amis dans le besoin peuvent s'y référer

Le. les exemples de cet article décrivent l'algorithme de tri rapide implémenté en Python. Partagez-le avec tout le monde pour votre référence, les détails sont les suivants :

L'idée de base du tri rapide est de diviser les données à trier en deux parties indépendantes grâce à un seul tri, et toutes les données en un seul. Une partie est supérieure à toutes les données de l'autre partie, puis utilisez cette méthode pour trier rapidement les deux parties des données respectivement. L'ensemble du processus de tri peut être effectué de manière récursive, de sorte que l'ensemble des données devienne une séquence ordonnée. .

Par exemple, dans la séquence [6, 8, 1, 4, 3, 9], sélectionnez 6 comme numéro de base. Scannez de droite à gauche, à la recherche d'un nombre plus petit que le nombre de base 3, échangez les positions de 6 et 3, [3, 8, 1, 4, 6, 9], puis scannez de gauche à droite, à la recherche d'un nombre. plus grand que le nombre de base Le nombre est 8, échangez les positions de 6 et 8, [3, 6, 1, 4, 8, 9]. Répétez le processus ci-dessus jusqu'à ce que les nombres à gauche du numéro de base soient plus petits et que les nombres à droite soient plus grands. Effectuez ensuite la méthode ci-dessus de manière récursive sur les séquences respectivement à gauche et à droite du numéro de référence.

Le code d'implémentation est le suivant :

def parttion(v, left, right):
  key = v[left]
  low = left
  high = right
  while low < high:
    while (low < high) and (v[high] >= key):
      high -= 1
    v[low] = v[high]
    while (low < high) and (v[low] <= key):
      low += 1
    v[high] = v[low]
    v[low] = key
  return low
def quicksort(v, left, right):
  if left < right:
    p = parttion(v, left, right)
    quicksort(v, left, p-1)
    quicksort(v, p+1, right)
  return v
s = [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
print("before sort:",s)
s1 = quicksort(s, left = 0, right = len(s) - 1)
print("after sort:",s1)

Résultats en cours d'exécution :

before sort: [6, 8, 1, 4, 3, 9, 5, 4, 11, 2, 2, 15, 6]
after sort: [1, 2, 2, 3, 4, 4, 5, 6, 6, 8, 9, 11, 15]

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!