Qu'est-ce que le tri par insertion ?

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].

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!