Le tri en tas est-il stable ?

Le tri par tas, le tri rapide, le tri Hill et le tri par sélection directe sont des algorithmes de tri instables, tandis que le tri par base, le tri par bulles, le tri par insertion directe, le tri par demi-insertion et le tri par fusion sont un algorithme de tri stable.

Tri par tas

Nous savons que la structure du tas est que les enfants du nœud i sont des nœuds 2*i et 2*i+1. Un grand tas supérieur nécessite que le nœud parent. est supérieur ou égal à ses 2 nœuds enfants. Un petit tas supérieur nécessite que le nœud parent soit supérieur ou égal à ses 2 nœuds enfants. Le tas supérieur nécessite que le nœud parent soit inférieur ou égal à ses 2 nœuds enfants.

Dans une séquence de longueur n, le processus de tri des tas consiste à sélectionner le plus grand (grand tas supérieur) ou le plus petit (petit tas supérieur) parmi le n/2ème et ses nœuds enfants avec un total de 3 Ces 3 valeurs. Le choix entre les éléments ne détruit certainement pas la stabilité. Mais lors de la sélection d'éléments pour les nœuds parents n /2-1, n/2-2, ...1, la stabilité sera détruite.

Il est possible que le n/2ème nœud parent échange l'élément suivant, et que le n/2-1ème nœud parent n'échange pas le prochain même élément. Alors ces deux mêmes éléments La stabilité entre eux est détruite. Par conséquent, le tri par tas n’est pas un algorithme de tri stable.

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!