Que signifie la stabilité de l'algorithme ?

La stabilité de l'algorithme fait référence au fait que dans un ensemble d'enregistrements à trier, s'il y a deux enregistrements égaux R et S, et R est avant S dans les enregistrements à trier, si R est toujours avant le tri S signifie que leurs positions avant et arrière ne changent pas avant et après le tri, alors l'algorithme de tri est dit stable.

Stabilité de l'algorithme : dans un ensemble d'enregistrements à trier, s'il existe deux enregistrements égaux R et S, et dans les enregistrements à trier, R est dans Avant S, si R est toujours avant S après le tri, c'est-à-dire que leurs positions avant et arrière ne changent pas avant et après le tri, alors l'algorithme de tri est dit stable.

Stabilité des algorithmes de tri courants

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 et le tri par bulles , le tri par insertion directe, le tri par demi-insertion et le tri par fusion sont des algorithmes de tri stables.

Tout d'abord, tout le monde doit connaître la stabilité de l'algorithme de tri. En termes simples, il garantit que l'ordre des positions avant et arrière des deux nombres égaux avant le tri est le même que l'ordre des nombres. positions avant et arrière des deux après tri. En formalisation simple, si Ai = Aj, Ai est à l'origine devant la position, et Ai sera toujours devant la position de Aj après tri.

Deuxièmement, parlons des avantages de la stabilité. Si l'algorithme de tri est stable, puis tri à partir d'une clé puis tri à partir d'une autre clé, le résultat du premier tri par clé peut être utilisé pour le deuxième tri par clé. Le tri de base est comme ceci, triant d'abord par bits faibles, puis triant par bits élevés. L'ordre des éléments avec les mêmes bits faibles ne changera pas lorsque les bits forts sont les mêmes.

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!