Quelles sont les méthodes de tri de base ?

Les méthodes de tri de base comprennent : 1. Le tri par sélection, qui est divisé en « tri par sélection simple » et « tri par tas » 2. Le tri par insertion, qui est divisé en « tri par insertion simple » et « tri par colline » ; ; 3. Le tri par échange est divisé en « tri à bulles » et « tri rapide » ; 4. Tri par fusion 5. Tri par base ;

Méthode de tri de base

Trier

Aucun Un algorithme de tri est optimal en toutes circonstances, et l'algorithme optimal doit être sélectionné en fonction de la situation réelle pour résoudre le problème

Stabilité de l'algorithme : dans un ensemble d'enregistrements à trier, s'il y a deux enregistrements égaux R et S, et dans les enregistrements à trier, R est 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 appelé stable

• Tri par sélection

Tri par sélection simple

Le tri par sélection simple est intuitif L'algorithme de tri sélectionne le plus petit élément de la séquence non triée et l'échange avec le premier élément de la séquence, puis sélectionne le plus petit élément de la séquence non triée restante et l'échange avec le deuxième élément de la séquence, et ainsi de suite. Enfin, une séquence triée de. petit à grand est formé

Complexité temporelle : O(N2)

Tri des tas

Génère une séquence non ordonnée dans un tas maximum et place le haut du tas Échangez le éléments avec le dernier élément, et générez le tas maximum avec les éléments restants. Échangez les éléments en séquence et générez le tas maximum

Complexité temporelle : O(NlogN) Complexité spatiale : O(1)

• Tri par insertion

Tri par insertion simple

Diviser un ensemble de séquences à trier en triés Il y en a deux parties, ordonnées et non triées 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 ajoutés un à un ; . Insérer dans une séquence triée. 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

• tri par échange

tri à bulles

pour les éléments Lors du tri de N séquences à trier, un total de N-1 cycles sont effectués. Dans la k-ième boucle, les éléments du 1er au N-kième sont comparés d'avant en arrière, et à chaque fois les deux éléments adjacents sont comparés. Si le premier élément est supérieur au dernier élément, les deux positions d'échange, sinon ils restent invariants de position

Complexité temporelle : O(N2)

Tri rapide

Divise les éléments non triés en deux sous-séquences basées sur un "pivot" comme base, Les enregistrements d'une sous-séquence sont tous supérieurs à l'élément pivot, tandis que les enregistrements de l'autre sous-séquence sont inférieurs à l'élément pivot, puis les deux sous-séquences sont triées de manière récursive en utilisant une méthode similaire

Complexité temporelle : O( Nlog2N)

• Tri par fusion

Considérer une séquence de taille N comme N sous-séquences de longueur 1. Suivant Fusionner adjacent sous-séquences par paires pour former N/2(+1) sous-séquences ordonnées d'une longueur de 2 (ou 1) ; puis continuez à fusionner les sous-séquences adjacentes par paires. Si vous continuez à boucler, jusqu'à ce qu'il reste une séquence de longueur N, la séquence. est le résultat du tri de la séquence originale

Complexité temporelle : O(Nlog2N) Complexité spatiale : O(N)

• Tri par base

Tri par compartiment

Si l'on sait que la plage de valeurs de N mots-clés est de 0 à M -1 et que M est beaucoup plus petit que N, l'algorithme de tri par compartiment crée un « bucket » pour chaque valeur du mot-clé, c'est-à-dire que M buckets sont créés lors de l'analyse de N mots-clés, chaque mot-clé est placé dans le bucket correspondant, puis collecté dans l'ordre du bucket, et il le sera naturellement. ordonné

Tri par base

Le tri par base est une généralisation du tri par compartiment, et il considère les enregistrements à trier Contient plus d'un mot-clé

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!