Comment trier par tas

1. Construire le tas initial :

Lors de l'initialisation du tas, tous les nœuds non-feuilles sont filtrés.

L'indice du dernier élément non terminal est [n/2] arrondi vers le bas, le filtrage ne doit donc commencer qu'à partir du [n/2]ème élément arrondi vers le bas et s'ajuster de l'arrière vers l'avant.

Par exemple, étant donné un tableau, construisez d'abord un arbre binaire complet basé sur les éléments du tableau.

Ensuite, à partir du dernier nœud non-feuille, la comparaison et l'échange sont effectués à partir du nœud parent, de l'enfant gauche et de l'enfant droit à chaque fois. L'échange peut empêcher le nœud enfant de satisfaire les propriétés du tas. , donc à chaque fois Après cet échange, les nœuds enfants échangés doivent être réajustés.

2. Effectuez le tri des tas :

Après avoir obtenu le tas initial, vous pouvez trier.

Le tri par tas est un tri par sélection. Le tas initial créé est la zone non ordonnée initiale.

Lorsque le tri commence, l'élément supérieur du tas est affiché en premier (car c'est la valeur la plus élevée), et l'élément supérieur du tas et le dernier élément sont échangés de cette façon, la nième position (. c'est-à-dire la dernière position) est utilisée comme zone ordonnée, et les positions n-1 précédentes sont toujours des zones non ordonnées. Après avoir obtenu le tas, échangez les éléments supérieur et final du tas afin que la longueur. de la zone ordonnée devient 2. . .

Continuez cette opération, réajustez les éléments restants dans le tas, puis sortez l'élément supérieur du tas vers la zone triée. Chaque échange donne -1 pour la zone non ordonnée et +1 pour la zone ordonnée. Ce processus est répété jusqu'à ce que la longueur de la zone ordonnée atteigne n-1 et que le tri soit terminé.

3. Exemple de tri de tas :

Tout d'abord, établissez la structure de tas initiale comme indiqué :

Ensuite , échangez l'élément en haut du tas et le dernier élément. À ce stade, la dernière position est utilisée comme zone ordonnée (la zone ordonnée est affichée en jaune), puis ajustez le tas des autres zones non ordonnées. le grand tas supérieur, échangez les éléments supérieurs et derniers du tas. La position de l'avant-dernier élément...

Répétez ce processus :

Enfin, l'expansion de la zone ordonnée est terminée. Autrement dit, le tri est terminé :

Il ressort du processus de tri que si vous Si vous souhaitez obtenir l'ordre croissant, créez un grand tas supérieur, si vous souhaitez obtenir un ordre décroissant, créez un petit tas supérieur.

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!