Que signifie le tri rapide ?

Le tri rapide est une amélioration du tri à bulles. Son principe de mise en œuvre est de diviser les éléments non triés en deux sous-séquences basées sur un "pivot" comme référence. Les enregistrements dans l'une des sous-séquences sont plus grands que l'élément principal. . et l'autre sous-séquence est plus petite que l'élément pivot, puis les deux sous-séquences sont triées de manière récursive en utilisant une méthode similaire.

Tri rapide

Divise les éléments non triés en groupes sur la base d'un "pivot" Deux sous-séquences, dont l'une a des enregistrements supérieurs au pivot, tandis que l'autre sous-séquence est plus petite que le pivot, puis trier récursivement les deux sous-séquences de la même manière

Complexité temporelle : O(Nlog2N)

Introduction :

Quicksort est une amélioration du tri à bulles.

Le tri rapide a été proposé par C. A. R. Hoare en 1960. Son idée de base est de diviser les données à trier en deux parties indépendantes via un tri. Toutes les données d'une partie sont plus petites que toutes les données de l'autre partie, puis d'utiliser cette méthode pour séparer rapidement les deux parties des données. . Tri, l'ensemble du processus de tri peut être effectué de manière récursive, de sorte que l'ensemble des données devienne une séquence ordonnée.

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!