Concept et code d'implémentation d'un algorithme de tri par tas en Python

La condition préalable pour comprendre l'algorithme de tri par tas est de connaître l'arbre binaire complet et la structure des données du tas. L'algorithme de tri par tas visualise le tableau comme un arbre binaire complet, c'est pourquoi il est également appelé « tas ».

Principe de l'algorithme de tri du tas

1 Selon l'attribut de tas maximum, le plus grand élément du groupe de données est stocké dans le nœud racine

2. Supprimez l'élément racine et placez-le à la fin du tableau (le nième position), et placez le dernier élément de l'élément de l'arborescence, placez-le dans l'espace vide.

3. Réduisez la taille du tas de 1.

4. Regroupez à nouveau l'élément racine

5. Répétez le processus jusqu'à ce que tous les éléments de la liste soient triés

Python implémente un algorithme de tri par tas

指定数组arr= 1 12 9 5 6 10

def heapify(arr, n, i):
      largest = i
      l = 2 * i + 1
      r = 2 * i + 2
  
      if l < n and arr[i] < arr[l]:
          largest = l
  
      if r < n and arr[largest] < arr[r]:
          largest = r
  
heapifying
      if largest != i:
          arr[i], arr[largest] = arr[largest], arr[i]
          heapify(arr, n, largest)
  
def heapSort(arr):
      n = len(arr)
  
      for i in range(n//2, -1, -1):
          heapify(arr, n, i)
  
      for i in range(n-1, 0, -1):
          arr[i], arr[0] = arr[0], arr[i]
  
          heapify(arr, i, 0)
  
  arr = [1, 12, 9, 5, 6, 10]
  heapSort(arr)
  n = len(arr)
  print("Sorted array is")
  for i in range(n):
      print("%d " % arr[i], end=&#x27;&#x27;)

.

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!