Qu'est-ce que le tri par insertion simple

Le tri par insertion simple est un algorithme efficace qui divise un ensemble de séquences à trier en deux parties : triées et non triées. Dans l'état initial, la séquence triée ne contient que le premier élément, les éléments non triés. La séquence sont des éléments "N-1" sauf le premier, puis les éléments de la séquence non triée sont insérés un par un dans la séquence triée.

Tri par insertion simple

Diviser un ensemble de séquences à trier en triées et Les deux non triées parties. Dans l'état initial, la séquence triée ne contient que le premier élément, et les éléments de la séquence non triée sont N-1 éléments sauf le premier par la suite, les éléments de la séquence non triée sont insérés un par un dans une séquence triée ; séquence. De cette façon, après N-1 insertions, le nombre d'éléments dans la séquence non triée est de 0 et le tri est terminé

Complexité temporelle : O(N2) Tri stable

Introduction connexe :

L'algorithme dit de tri fait référence à la réorganisation d'un ou plusieurs ensembles de données selon un modèle prédéterminé grâce à des facteurs d'algorithme spécifiques. Cette nouvelle séquence suit certaines règles et reflète certains modèles. Par conséquent, les données traitées sont faciles à filtrer et à calculer, ce qui améliore considérablement l'efficacité des calculs. Pour le tri, nous exigeons d'abord qu'il ait un certain degré de stabilité, c'est-à-dire que lorsque deux éléments identiques apparaissent dans une séquence en même temps, après un certain algorithme de tri, les positions relatives des deux avant et après le tri ne changeront pas. . Autrement dit, même s’il existe deux éléments identiques, ils sont différents lors du tri et ne peuvent pas être confondus.

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!