Maison  >  Article  >  Qu'est-ce que le tri par insertion ?

Qu'est-ce que le tri par insertion ?

藏色散人
藏色散人original
2020-06-30 09:28:572965parcourir

Le tri par insertion a deux types : le tri par insertion simple et le tri Hill. La complexité temporelle du tri par insertion simple est [O(N2) tri stable], et la complexité temporelle du tri Hill est [et la séquence incrémentielle] Sélectionnez. tri connexe et non stable].

Qu'est-ce que le tri par insertion ?

Tri par insertion

Tri par insertion simple

Mettre le groupe à trier La séquence est divisée en deux parties : triée et non triée. 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, il n'y aura aucun élément ; dans la séquence triée sont insérés dans la séquence triée un par un. De cette façon, après N-1 insertions, le nombre d'éléments dans la séquence non triée est 0, puis le tri est terminé

Complexité temporelle : O(N2) Tri stable

Tri Hill

Divisez un ensemble d'éléments à trier en plusieurs séquences à certains intervalles et effectuez respectivement le tri par insertion. L'"intervalle" défini au début est plus grand et l'intervalle est progressivement réduit à chaque tour de tri jusqu'à ce que "l'intervalle" soit 1, c'est-à-dire que la dernière étape consiste à effectuer un tri par insertion simple

Complexité temporelle : incrément de somme La sélection des séquences est liée au tri instable

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!

Déclaration:
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn