Partage de code de tri à bulles d'algorithme classique Java

Titre original : Algorithme classique en Java : Bubble Sort (Bubble Sort)

Qu'est-ce que le tri à bulles ?

Le tri à bulles est un algorithme de tri simple qui compare les éléments par paires les uns avec les autres en fonction de l'ordre. Si l’ordre va du plus grand au plus petit, alors lorsque deux éléments sont comparés, le plus grand sera classé en premier, sinon le plus grand sera classé plus tard ; Le tri des bulles est divisé en tri du grand au petit et du petit au grand.

Principe : Comparez deux éléments adjacents et échangez l'élément avec la plus grande valeur vers l'extrémité droite.

Idée : Comparez tour à tour deux nombres adjacents, mettez la décimale devant et le grand nombre derrière. Autrement dit, lors de la première passe : comparez d’abord le premier et le deuxième nombre, mettez la décimale en premier et le grand nombre en dernier. Comparez ensuite le deuxième nombre et le troisième nombre, mettez la décimale devant et le grand nombre derrière, et continuez ainsi jusqu'à comparer les deux derniers nombres, mettez la décimale devant et le grand nombre derrière. Répétez la première étape jusqu'à ce que tout le tri soit terminé.

Exemple : Pour trier le tableau : int[] arr={6,3,8,2,9,1};

Premier tri :

Premier tri : 6 et 3 comparaison, 6 est supérieur à 3, échangez les positions : 3 6 8 2 9 1

Deuxième tri : 6 et 8 comparés, 6 est inférieur à 8 , pas d'échange de positions : 3 6 8 2 9 1

Le troisième tri : 8 et 2 sont comparés, 8 est supérieur à 2, échange Position : 3 6 2 8 9 1

Le quatrième classement : 8 et 9 comparaison, 8 est inférieur à 9, pas d'échange de positions : 3 6 2 8 9 1

Le cinquième tri : 9 et 1 comparaison : 9 est supérieur à 1, échangez les positions : 3 6 2 8 1 9

Un total de 5 comparaisons ont été effectuées lors du premier voyage, et les résultats de tri étaient : 3 6 2 8 1 9

-------------------------------------------------------------- -- -----------------------

Deuxième tri :

Premier Tri : 3 et 6 comparés, 3 est inférieur à 6 , n'échangez pas les positions : 3 6 2 8 1 9

Le deuxième tri : 6 et 2 comparaison, 6 est supérieur à 2, échangez les positions : 3 2 6 8 1 9

Le troisième classement : 6 et 8 Comparez, 6 est supérieur à 8, sans échanger les positions : 3 2 6 8 1 9

Le quatrième tri : 8 et 1 comparaison, 8 est supérieur à 1, échangez les positions : 3 2 6 1 8 9

Un total de 4 comparaisons ont été effectuées lors du deuxième passage, et les résultats de tri étaient : 3 2 6 1 8 9

--------- ----------------------------------------- ---------- ---------------

Le troisième tri :

Le premier tri : 3Par rapport à 2, 3 est supérieur à 2 , positions d'échange : 2 3 6 1 8 9

Deuxième tri : 3 et 6 Comparez, 3 est inférieur à 6, n'échangez pas de positions : 2 3 6 1 8 9

Le troisième tri : 6 et 1 comparaison, 6 Plus grand que 1, échangez les positions : 2 3 1 6 8 9

Le deuxième voyage est effectué au total 3 comparaisons, résultats de tri : 2 3 1 6 8 9

--------------- - ------------------------------------------------- - -------

Le quatrième tri :

Le premier tri : 2 et 3 comparaison, 2 est inférieur à 3, pas d'échange de positions : 2 3 1 6 8 9

Deuxième tri : 3 et 1 comparaison , 3 est supérieur à 1, échangez les positions : 2 1 3 6 8 9

Le deuxième voyage a effectué un total de 2 comparaisons, résultats de tri : 2 1 3 6 8 9

------------------------------------------------------------ --- ---------------------

Cinquième tri :

Premier tri : 2 et 1 sont comparés, 2 est supérieur à 1, positions d'échange : 1 2 3 6 8 9

Le deuxième voyage a été effectué au total de 1 Comparer les fois, Tri des résultats : 1 2 3 6 8 9

------------------- ---------- --------------------------------------------- --------

Résultat final :1 2 3 6 8 9

------ ----------- --------------------------------------- -----------

On constate que : N nombres doivent être triés, et un total de N-1 le tri est effectué, à chaque fois. Le nombre d'heures de tri pour i est de (N-i) fois, vous pouvez donc utiliser une instruction à double boucle. La couche externe contrôle le nombre de fois la boucle, et la couche interne contrôle le nombre de fois la boucle. La couche contrôle le nombre de cycles de chaque passe, c'est-à-dire

for(int i=1;i<arr.length;i++){

    for(int j=1;j<arr.length-i;j++){

    //交换位置

}

Avantages du tri à bulles : Chaque fois qu'un tri est effectué, il y aura une comparaison de moins, car à chaque fois un la passe est effectuée. Le tri trouvera toujours une valeur plus grande. Comme dans l'exemple ci-dessus : après la première comparaison, le dernier nombre doit être le plus grand nombre. Lors du deuxième tri, il vous suffit de comparer les autres nombres sauf le dernier nombre, et vous pouvez également trouver le plus grand nombre. Les nombres sont classés. derrière les numéros participant à la deuxième comparaison. Dans la troisième comparaison, seuls les autres numéros à l'exception des deux derniers numéros doivent être comparés, et ainsi de suite... Autrement dit, sans comparaison, à chaque fois Une comparaison de moins par trajet réduit la quantité d'algorithme dans une certaine mesure.

En termes de complexité temporelle :

　1. Si nos données sont en ordre, nous n'avons besoin que d'un seul voyage pour terminer le tri. Le nombre de comparaisons requis et le nombre de mouvements d'enregistrement atteignent tous deux la valeur minimale, soit : C_min=n-1 ; par conséquent, bouillonnant La meilleure complexité temporelle du tri est O_(n).

　_{2 Si malheureusement nos données sont dans l'ordre inverse, n-1} passes sont nécessaires Trier. Chaque opération de tri nécessite n-i comparaisons (1≤i≤n-1), et chaque comparaison doit déplacer l'enregistrement trois fois pour atteindre la position de l'enregistrement d'échange. Dans ce cas, le nombre de comparaisons et de déplacements atteint le maximum : La pire complexité temporelle du tri à bulles est : O(n2_)^.

Pour résumer : la complexité temporelle moyenne totale du tri à bulles est : O(n2 ₎.

Code de tri à bulles de l'algorithme Java classique  :

/*
 * 冒泡排序 */public class BubbleSort {
　　public static void main(String[] args) {
　　　　int[] arr={6,3,8,2,9,1};
　　　　System.out.println("排序前数组为：");
　　　　for(int num:arr){
　　　　　　System.out.print(num+" ");
　　　　}
　　　　for(int i=0;i<arr.length-1;i++){//外层循环控制排序趟数　　　　　　for(int j=0;j<arr.length-1-i;j++){//内层循环控制每一趟排序多少次　　　　　　　　if(arr[j]>arr[j+1]){
　　　　　　　　　　int temp=arr[j];
　　　　　　　　　　arr[j]=arr[j+1];
　　　　　　　　　　arr[j+1]=temp;
　　　　　　　　}
　　　　　　}
　　　　} 
　　　　System.out.println();
　　　　System.out.println("排序后的数组为：");
 　　　　for(int num:arr){
 　　　　　　System.out.print(num+" ");
 　　　　} 
　　}
 }

Pour plus de partage sur le tri à bulles de l'algorithme Java classique, veuillez faire attention au site Web php chinois !