Maison  >  Article  >  Que sont les tris d'échange ?

Que sont les tris d'échange ?

藏色散人
藏色散人original
2020-06-30 09:35:174637parcourir

Le tri d'échange comprend le tri à bulles et le tri rapide. Le tri à bulles est un algorithme de tri plus simple dans le domaine de l'informatique, tandis que le tri rapide est une amélioration du tri à bulles. la complexité temporelle est "O(Nlog2N)".

Que sont les tris d'échange ?

Tri d'échange

  • Tri à bulles

Bubble Sort est un algorithme de tri relativement simple dans le domaine de l'informatique.

Lors du tri d'une séquence à trier avec N éléments, un total de N-1 boucles sont effectuées. 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 Position inchangée

Complexité temporelle :O(N2)

  • Tri rapide

Le tri rapide est un risque Une amélioration sur tri à bulles.

Divisez les éléments non triés en deux sous-séquences en fonction d'un "pivot" comme référence. Les enregistrements d'une sous-séquence sont tous supérieurs au pivot, tandis que les enregistrements de l'autre sous-séquence sont tous inférieurs au pivot, et puis récursivement Ces deux sous-séquences sont triées de manière similaire

Complexité temporelle : O(Nlog2N)

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