Le tri rapide est souvent adopté car son efficacité de tri est relativement élevée parmi plusieurs méthodes de tri qui sont toutes en O(N*logN). De plus, l'idée du tri rapide — la méthode diviser pour régner — est effectivement pratique. C'est pourquoi de nombreuses entreprises de logiciels aiment le tester lors d'épreuves écrites et d'entretiens, y compris des entreprises informatiques connues telles que Tencent et Microsoft. De plus, le tri rapide apparaît fréquemment dans des examens liés à la programmation de tailles diverses, comme l'examen de qualification en logiciel et l'examen d'entrée aux études supérieures.

=a

Le tri rapide est un tri par partition-échange proposé par C.R.A.Hoare en 1962. Il utilise une stratégie de diviser pour régner, généralement appelée méthode diviser pour régner (Divide-and-Conquer Method).

L'idée de base de cette méthode est :

• 1. Prenez d'abord un nombre dans la séquence comme pivot.
• 2. Dans le processus de partition, placez tous les nombres supérieurs à ce nombre à sa droite, et tous les nombres inférieurs ou égaux à celui-ci à sa gauche.
• 3. Répétez l'étape 2 pour les intervalles gauche et droit jusqu'à ce que chaque intervalle ne contienne qu'un seul nombre.

Bien que le tri rapide soit appelé méthode diviser pour régner, ces trois mots ne peuvent manifestement pas résumer entièrement toutes les étapes du tri rapide. Par conséquent, j'ai fourni une explication plus approfondie du tri rapide : creuser des trous et remplir des nombres + diviser pour régner.

Regardons d'abord un exemple. La définition est donnée ci-dessous (il est préférable de résumer la définition dans vos propres mots, car cela aidera à implémenter le code).

 

Prenons un tableau comme exemple, et prenons le premier nombre de l'intervalle comme pivot.

0	1	2	3	4	5	6	7	8	9
72	6	57	88	60	42	83	73	48	85

Initialement, i = 0 ; j = 9 ; X = a[i] = 72

Comme le nombre dans a

En partant de j, cherchez vers la gauche un nombre inférieur ou égal à X. Lorsque j=8, la condition est remplie. Extrayez a

 

Le tableau devient :

0	1	2	3	4	5	6	7	8	9
48	6	57	88	60	42	83	73	88	85

 

i = 3;   j = 7;   X=72

Répétez les étapes ci-dessus : cherchez d'abord de la fin vers le début, puis du début vers la fin.

Cherchez vers la gauche en partant de j. Lorsque j=5, la condition est remplie. Extrayez a

Cherchez vers la droite en partant de i. Lorsque i=5, sortez car i==j.

À ce stade, i = j = 5, et a

Le tableau devient :

0	1	2	3	4	5	6	7	8	9
48	6	57	42	60	72	83	73	88	85

On peut voir que les nombres avant a

 

Résumons le creusement de trous et le remplissage de nombres :

• 1. i = L ; j = R ; extraire le pivot pour former le premier trou a[i].
• 2. j--, rechercher de la fin vers le début un nombre qui lui est inférieur. Après l'avoir trouvé, extraire ce nombre et le placer dans le trou précédent a[i].
• 3. i++, rechercher du début vers la fin un nombre qui lui est supérieur. Après l'avoir trouvé, extraire aussi ce nombre et le placer dans le trou précédent a[j].
• 4. Répéter les étapes 2 et 3 jusqu'à ce que i==j, puis placer le pivot dans a[i].

En suivant ce résumé, il est facile d'implémenter le code pour le creusement de trous et le remplissage de nombres :

int AdjustArray(int s[], int l, int r) //Retourne la position du pivot ajusté { int i = l, j = r; int x = s[l]; //s[l], c'est-à-dire s[i], est le premier trou while (i < j) { // Trouver un nombre inférieur à x de droite à gauche pour remplir s[i] while(i < j && s[j] >= x) j--; if(i < j) { s[i] = s[j]; //Remplir s[i] avec s[j], puis s[j] forme un nouveau trou i++; } // Trouver un nombre supérieur ou égal à x de gauche à droite pour remplir s[j] while(i < j && s[i] < x) i++; if(i < j) { s[j] = s[i]; //Remplir s[j] avec s[i], puis s[i] forme un nouveau trou j--; } } //À la sortie, i est égal à j. Remplir ce trou avec x. s[i] = x; return i; }

Écrivez ensuite le code pour la méthode diviser pour régner :

void quick_sort1(int s[], int l, int r) { if (l < r) { int i = AdjustArray(s, l, r);//Utilisez d'abord la méthode du creusement de trou et de remplissage de nombre pour ajuster s[] quick_sort1(s, l, i - 1); // Appel récursif quick_sort1(s, i + 1, r); } }

Ce code n'est manifestement pas assez concis, alors combinez-le et nettoyez-le :

//Tri rapide void quick_sort(int s[], int l, int r) { if (l < r) { //Swap(s[l], s[(l + r) / 2]); // Échangez le nombre du milieu avec le premier nombre. Voir la note 1 int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j] >= x) //Trouvez le premier nombre inférieur à x de droite à gauche j--; if(i < j) s[i++] = s[j]; while(i < j && s[i] < x) //Trouvez le premier nombre supérieur ou égal à x de gauche à droite i++; if(i < j) s[j--] = s[i]; } s[i] = x; quick_sort(s, l, i - 1); // Appel récursif quick_sort(s, i + 1, r); } }

Il existe de nombreuses versions améliorées du tri rapide, comme la sélection aléatoire du pivot, ou l'utilisation directe d'une autre méthode de tri lorsqu'il y a moins de données dans l'intervalle afin de réduire la profondeur de récursion. Les amis intéressés peuvent l'étudier plus en détail.

Remarque 1 : certains livres utilisent le nombre du milieu comme pivot. Pour ce faire, c'est très simple—il suffit d'échanger le nombre du milieu avec le premier nombre.

Auteur : MoreWindows

Article original : https://blog.csdn.net/morewindows/article/details/6684558