1. Aperçu :

　　

Cet article présente les principes et les implémentations en Java de plusieurs algorithmes de tri courants, y compris les algorithmes de tri simples courants et les algorithmes de tri avancés, ainsi que d'autres connaissances algorithmiques couramment utilisées.

  • Tri simple: Tri à bulles, Tri par sélection, Tri par insertion
  • Tri avancé: Tri rapide, Tri par fusion, Tri de Shell
  • Connaissances algorithmiques associées: Partitionnement, Récursivité, Recherche binaire

2. Tri à bulles :

(1) Principe :

  • 1. En partant de la première donnée, comparez-la avec la deuxième donnée. Si la deuxième donnée est plus petite que la première donnée, échangez les positions des deux données.
  • 2. Le pointeur passe de la première donnée à la deuxième donnée, et la deuxième donnée est comparée à la troisième donnée. Si la troisième donnée est plus petite que la deuxième donnée, échangez les positions des deux données.
  • 3. Et ainsi de suite, en terminant le premier tour de tri. Après le premier tour, le plus grand élément a été déplacé tout à droite.
  • 4. Effectuez le deuxième tour de tri selon le processus ci-dessus, en plaçant le deuxième plus grand à l'avant-dernière position.
  • 5. Répétez le processus ci-dessus. À chaque fois qu'un tour est terminé, le nombre de comparaisons diminue de un.

(2) Exemple :

Données à trier : 7, 6, 9, 8, 5, 1

Processus de tri du premier tour :

指针先指向7，7和6比较，6<7，交换6和7的位置，结果为：6,7,9,8,5,1
指针指向第二个元素7，7和9比较，9>7，不用交换位置，结果仍为：6,7,9,8,5,1
指针指向第三个元素9，比较9和8，8<9，交换8和9的位置，结果为：6,7,8,9,5,1
指针指向第四个元素9，比较9和5，5<9，交换5和9，结果为：6,7,8,5,9,1
指针指向第五个元素9，比较9和1，1<9，交换1和9的位置，结果为6,7,8,5,1,9

Après le premier tour de tri, le plus grand nombre, 9, est déplacé tout à droite.

Passez au deuxième tour de tri. Le processus est le même que ci-dessus, sauf que, comme le plus grand nombre 9 est déjà tout à droite, il n'est pas nécessaire de comparer 9 à nouveau, ce qui économise une comparaison. Le résultat après le deuxième tour est : 6,7,5,1,8,9

Résultat du troisième tour : 6,5,1,7,8,9

Résultat de la comparaison du quatrième tour : 5,1,6,7,8,9

Résultat de la comparaison du cinquième tour : 1,5,6,7,8,9

Le résultat final du tri est : 1,5,6,7,8,9. D'après ce qui précède, on peut voir que le tri de N éléments de données nécessite N-1 tours de tri ; le nombre de comparaisons nécessaires au i-ème tour est N-i.

(3) Approche de codage :

Deux niveaux de boucles sont nécessaires. La première boucle, i, représente le nombre de tours de tri, et la seconde boucle, j, représente le nombre de comparaisons.

(4) Implémentation du code :

Exemple

package com.test.insertsort; /** * Tri par sélection * @author Administrator * */ public class ChooseSort { private int[] array; private int length; public ChooseSort(int[] array){ this.array = array; this.length = array.length; } /** * Afficher tous les éléments du tableau **/ public void display(){ for(int i: array){ System.out.print(i+" "); } System.out.println(); } /** * Algorithme de tri par sélection **/ public void chooseSort(){ for(int i=0; i<length-1; i++){ int minIndex = i; for(int j=minIndex+1;j<length;j++){ if(array[j]<array[minIndex]){ minIndex = j; } } int temp = array[i]; array[i] = array[minIndex]; array[minIndex] = temp; } } public static void main(String[] args){ int[] array={100,45,36,21,17,13,7}; ChooseSort cs = new ChooseSort(array); System.out.println("Données avant le tri :"); cs.display(); cs.chooseSort(); System.out.println("Données après le tri :"); cs.display(); } }

(5) Récapitulatif du tri par sélection :

N éléments nécessitent N-1 tours de tri ;

Le i-ème tour nécessite N-i comparaisons ;

Le tri de N éléments nécessite n(n-1)/2 comparaisons ;

La complexité algorithmique du tri par sélection est toujours O(n*n) ;

Comparé au tri à bulles, le tri par sélection réduit considérablement le nombre d'échanges, ce qui le rend plus rapide que le tri à bulles.

4. Tri par insertion

Le tri par insertion est l'algorithme de tri le plus rapide parmi les tris simples. Bien que sa complexité temporelle soit toujours O(n*n), il est bien plus rapide que le tri à bulles et le tri par sélection.

(1) Principe :

  • 1. Pointez le pointeur sur un élément. Supposez que tous les éléments à sa gauche sont ordonnés. Extrayez cet élément, puis comparez-le avec les éléments à sa gauche de droite à gauche. Si vous rencontrez un élément plus grand que lui, déplacez cet élément vers la droite. Arrêtez-vous lorsque vous trouvez un élément plus petit que lui, ou lorsque vous atteignez l'extrémité gauche et constatez que tous les éléments à sa gauche sont plus grands que lui.
  • 2. À ce stade, une position vide apparaît. Placez l'élément dans cette position vide. Maintenant, tous les éléments à gauche de cet élément sont plus petits que lui, et tous les éléments à droite sont plus grands que lui.
  • 3. Reculez le pointeur d'une position et répétez le processus ci-dessus. Après chaque tour d'opération, le nombre d'éléments ordonnés à gauche augmente de un, et le nombre d'éléments non ordonnés à droite diminue de un.

(2) Exemple :

Données à comparer : 7, 6, 9, 8, 5, 1

  • Premier tour : Le pointeur pointe vers le deuxième élément, 6. Supposons que les éléments à gauche de 6 soient ordonnés. Extrayez 6, ce qui donne 7,_,9,8,5,1. En partant de 7, comparez 6 avec 7 et constatez que 7>6. Déplacez 7 vers la droite, ce qui donne _,7,9,8,5,1. Insérez 6 dans la position vide avant 7. Résultat : 6,7,9,8,5,1
  • Deuxième tour : Le pointeur pointe vers le troisième élément, 9. À ce moment, les éléments à sa gauche, 6,7, sont ordonnés. Extrayez 9, ce qui donne 6,7,_,8,5,1. En partant de 7, comparez chaque élément avec 9 à tour de rôle, et constatez que tous les éléments à gauche de 9 sont inférieurs à 9, donc aucun déplacement n'est nécessaire. Placez 9 dans la position vide. Le résultat reste : 6,7,9,8,5,1
  • Troisième tour : Le pointeur pointe vers le quatrième élément, 8. À ce moment, les éléments à sa gauche, 6,7,9, sont ordonnés. Extrayez 8, ce qui donne 6,7,9,_,5,1. En partant de 9, comparez chaque élément avec 8 à tour de rôle, et constatez que 8<9. Déplacez 9 vers la droite, ce qui donne 6,7,_,9,5,1. Insérez 8 dans la position vide. Résultat : 6,7,8,9,5,1
  • Quatrième tour : Le pointeur pointe vers le cinquième élément, 5. À ce moment, les éléments à sa gauche, 6,7,8,9, sont ordonnés. Extrayez 5, ce qui donne 6,7,8,9,_,1. En partant de 9, comparez chaque élément avec 5 à tour de rôle, et constatez que 5 est inférieur à tous les éléments à sa gauche. Tous les éléments à gauche de 5 se déplacent vers la droite, ce qui donne _,6,7,8,9,1. Placez 5 dans la position vide. Résultat : 5,6,7,8,9,1.
  • Cinquième tour : Comme ci-dessus. 1 est déplacé à l'extrême gauche. Résultat final : 1,5,6,7,8,9.

(3) Analyse du code :

Deux boucles imbriquées sont nécessaires. La première boucle, index, représente le pointeur dans l'exemple ci-dessus, c'est-à-dire qu'elle parcourt chaque élément en commençant à la coordonnée 1. La deuxième boucle commence à leftindex=index-1 et parcourt vers la gauche avec leftindex--, en comparant chaque élément avec l'élément à i, jusqu'à ce que l'élément à j soit plus petit que l'élément à i ou que leftindex<0. Parcourez chaque élément de i à j pour le déplacer vers la droite, et placez enfin l'élément à index dans la position vide à leftindex.

(4) Implémentation du code :

Exemple

package com.test.insertsort; /** * Algorithme de tri par insertion : * 1. Utilisez une certaine position dans le tableau comme position de séparation, par exemple index=1, et supposez que le côté gauche est entièrement ordonné. * * 2. Retirez la donnée à la position index et placez-la dans une variable temporaire. Maintenant, la position index est vide. * * 3. En partant de leftindex=index-1, comparez la donnée à gauche avec la donnée à l'index actuel (c'est-à-dire temp). Si array[leftindex]>temp, * alors déplacez array[leftindex] d'une position vers la droite, c'est-à-dire array[leftindex+1]=array[leftindex]. À ce moment, leftindex devient vide. * * 4. Ensuite, comparez la donnée à index-2 (c'est-à-dire leftindex=leftindex-1) avec temp, répétez l'étape 3, * jusqu'à trouver une donnée <=temp ou jusqu'à comparer tout le chemin jusqu'à l'extrémité gauche (ce qui signifie que temp est la plus petite), arrêtez la comparaison et placez temp dans la position vide actuelle. * * 5. Déplacez index d'une position vers la droite, c'est-à-dire index=index+1, temp=array[index], répétez les étapes 2-4 jusqu'à index=array.length, le tri se termine, * et les données du tableau sont maintenant en ordre croissant. * * @author bjh * */ public class InsertSort { private int[] array; private int length; public InsertSort(int[] array){ this.array = array; this.length = array.length; } public void display(){ for(int a: array){ System.out.print(a+" "); } System.out.println(); } /** * Méthode de tri par insertion **/ public void doInsertSort(){ for(int index = 1; index<length; index++){//L'index externe se déplace vers la droite, c'est-à-dire l'index de la donnée utilisée comme objet de comparaison. int temp = array[index];//La donnée utilisée pour la comparaison. int leftindex = index-1; while(leftindex>=0 && array[leftindex]>temp){//Lorsque la comparaison atteint l'extrémité gauche ou rencontre une donnée inférieure à temp, terminez la boucle. array[leftindex+1] = array[leftindex]; leftindex--; } array[leftindex+1] = temp;//Placez temp dans la position vide. } } public static void main(String[] args){ int[] array = {38,65,97,76,13,27,49}; InsertSort is = new InsertSort(array); System.out.println("Données avant le tri :"); is.display(); is.doInsertSort(); System.out.println("Données après le tri :"); is.display(); } }

(5) Analyse du tri par insertion :

Complexité temporelle : comme deux niveaux de boucles sont encore nécessaires, la complexité temporelle du tri par insertion est toujours O(n*n).

Nombre de comparaisons : lors du premier tour de tri, le tri par insertion compare au plus une fois ; lors du deuxième tour, au plus deux fois ; et ainsi de suite. Lors du dernier tour, il compare au plus N-1 fois. Par conséquent, le nombre maximal de comparaisons du tri par insertion est 1+2+...+N-1=N*(N-1)/2. Néanmoins, le tri par insertion effectue rarement réellement autant de comparaisons, car dès qu'un élément plus petit que l'élément cible est trouvé à gauche, la comparaison s'arrête. Par conséquent, le nombre moyen de comparaisons du tri par insertion est N*(N-1)/4.

Nombre de déplacements : le nombre de déplacements dans le tri par insertion est presque le même que le nombre de comparaisons, mais le déplacement est bien plus rapide que l'échange.

En résumé, le tri par insertion est environ deux fois plus rapide que le tri à bulles (moitié moins de comparaisons), et un peu plus rapide que le tri par sélection. Pour des données presque ordonnées, le tri par insertion est très rapide, ce qui en fait l'algorithme de tri le plus efficace parmi les tris simples.

Tri rapide, tri à bulles, tri par sélection, tri par insertion, tri fusion

1. Aperçu :

L'article précédent a présenté les algorithmes simples courants : le tri à bulles, le tri par sélection et le tri par insertion. Cet article présente des algorithmes de tri avancés : le tri rapide et le tri fusion. Avant d'introduire les algorithmes, nous présentons d'abord les connaissances de base nécessaires aux algorithmes avancés : le partitionnement et la récursivité, et nous abordons également l'algorithme de recherche dichotomique.

2. Partitionnement :

Le partitionnement est le prérequis du tri rapide, c'est-à-dire qu'il divise les données en deux groupes : les données supérieures à une valeur spécifique dans un groupe, et les données inférieures à une valeur spécifique dans l'autre groupe. Le tri rapide est réalisé au moyen d'opérations de partitionnement et de récursivité.

(1) Principe :

Définissez un seuil. Parcourez les éléments depuis l'extrême gauche et l'extrême droite vers le milieu. Arrêtez-vous lorsque vous trouvez à gauche des données supérieures au seuil, et arrêtez-vous lorsque vous trouvez à droite des données inférieures au seuil. Si les côtés gauche et droit n'ont pas encore atteint le milieu, échangez les données supérieures au seuil à gauche avec les données inférieures au seuil à droite. Répétez le processus ci-dessus jusqu'à ce que les pointeurs gauche et droit se rencontrent. À ce stade, les données à gauche sont toutes inférieures au seuil, et les données à droite sont toutes supérieures au seuil, et le partitionnement se termine. Après le partitionnement, les données sont encore non ordonnées, mais plus proches de l'ordre.

(2) Exemple :

Données à partitionner : 7, 6, 9, 8, 5, 1, en supposant que le seuil est 5

Première passe : Le pointeur gauche pointe vers 7, le pointeur droit pointe vers 1. Le pointeur gauche se déplace vers l'arrière, et le pointeur droit se déplace vers la gauche. Il trouve que le premier élément supérieur à 5 à gauche est 7, et le premier élément inférieur à 5 à droite est 1. Échanger 7 et 1. Résultat : 1, 6, 9, 8, 5, 7;

Deuxième passe : En partant de 6, trouver un nombre supérieur à 5, et trouver 6. À droite, en partant de 5, trouver un nombre inférieur à 5, et trouver 1. Mais maintenant, comme 6 est à droite de 1, c'est-à-dire pointeur droit < pointeur gauche, les pointeurs gauche et droit se croisent, et la partition se termine. La séquence d'origine est divisée en deux parties. La sous-séquence gauche n'a qu'un seul élément, 1, qui est la sous-séquence inférieure au seuil ; la sous-séquence droite comprend 5 éléments, tous supérieurs au seuil 5.

(3) Implémentation du code :

Exemple

package com.test.insertsort; /** * Partition, récursivité, tri rapide * @author bjh * */ public class QuickSort { /** Tableau à trier/partitionner*/ private int[] array; /** Longueur du tableau*/ private int length; public QuickSort(int[] array){ this.array = array; this.length = array.length; } /** * Afficher l'élément*/ public void printArray(){ for(int i=0; i<length; i++){ System.out.print(array[i]+" "); } System.out.println(); } /** * Partition @return Le point de frontière de la partition*/ public int partition(int left, int right, int pivot){ //Le point de départ du pointeur gauche. left-1 s'explique par le fait que dans la boucle suivante, chaque fois que la boucle s'exécute, le pointeur gauche se déplace vers la droite. //Cela garantit que le pointeur gauche part du premier élément à gauche ; sinon, il partirait du deuxième. int leftpoint = left-1; //Le point de départ du pointeur droit. right+1 s'explique par le fait que dans la boucle suivante, chaque fois que la boucle s'exécute, le pointeur droit se déplace vers la gauche. //Cela garantit que le pointeur droit part de l'extrémité droite ; sinon, il partirait de l'avant-dernier. int rightpoint = right+1; while(true){ //Trouver à gauche des données supérieures au pivot, ou atteindre l'extrémité droite sans trouver de données supérieures au pivot. while(leftpoint<right && array[++leftpoint]<pivot); //Trouver à droite des données inférieures au pivot, ou atteindre l'extrémité gauche sans trouver de données inférieures au pivot. while(rightpoint>left && array[--rightpoint]>pivot); //Le pointeur gauche et le pointeur droit se chevauchent ou se croisent. if(leftpoint >= rightpoint){ break; }else{ //Échangez la donnée plus grande à gauche avec la donnée plus petite à droite. swap(leftpoint,rightpoint); } } //Renvoie le point limite, c'est-à-dire le point le plus à gauche dans le sous-tableau de droite. return leftpoint; } /** * Échanger les données*/ public void swap(int leftpoint,int rightpoint){ int temp = array[leftpoint]; array[leftpoint] = array[rightpoint]; array[rightpoint] = temp; } public static void main(String args[]){ int[] array = {99,78,26,17,82,36,9,81,22,100,30,20,17,85}; QuickSort qs = new QuickSort(array); System.out.println("Les données avant le partitionnement sont :"); qs.printArray(); int bound = qs.partition(0, array.length-1, 50); System.out.println("Les données après partitionnement sont :"); qs.printArray(); System.out.println("Le point frontière de la partition est :" + array[bound] + ", la coordonnée du point frontière est :" + borne); } }

Le résultat d'exécution est :

Lien original : https://www.cnblogs.com/bjh1117/p/8335628.html