principe
Le tri des bulles est probablement un algorithme que tous les programmeurs peuvent utiliser et est également l'un des algorithmes les plus familiers.
Ses idées ne sont pas compliquées:
Supposons que le tableau Arr [] soit maintenant trié et qu'il contient des éléments.
1. Si n = 1: évidemment, il n'est pas nécessaire de faire la queue. (En fait, cette discussion semble inutile)
2. Si n> 1:
(1) Nous commençons par le premier élément et comparons tous les deux éléments adjacents. Si l'élément précédent est plus grand que le suivant, le premier sera certainement classé derrière dans le résultat final. Nous échangeons donc ces deux éléments. Comparez ensuite les deux éléments adjacents suivants. De cette façon, jusqu'à ce que la dernière paire d'éléments soit comparée, le premier cycle de tri est terminé. Il est certain que le dernier élément doit être le plus grand du tableau (car le relativement grand est placé à l'arrière à chaque fois).
(2) Répétez le processus ci-dessus, cette fois, nous n'avons pas besoin de considérer le dernier car il est déjà organisé.
(3) Donc, jusqu'à ce qu'il ne reste qu'un élément, l'élément doit être le plus petit, puis notre tri peut se terminer. Apparemment, le tri N-1 a été effectué.
Dans le processus ci-dessus, chaque fois (ou "roue" est trié, un nombre "flottera lentement" d'une certaine position à la position finale (dessiner un diagramme schématique et dessinera le tableau verticalement), tout comme les bulles, il est donc appelé "méthode de tri des bulles".
Implémentation du code:
classe publique Bubblesort {public static void main (String [] args) {int score [] = {67, 69, 75, 87, 89, 90, 99, 100}; pour (int i = 0; i <score.length -1; i ++) {// ne fait pas seulement N-1 Commande pour (int j = 0; j <score.length - i - 1; j ++) {// Trier le score d'intervalle non ordonné [0 ...... Longueur-i-1] (la plage de J est très critique, cette plage est vraiment progressivement) if (score [j] <score [J +) {// SWAP-SWED pour (score [J] <Score [J +) {// SWAP plus tard int temp = score [j]; score [j] = score [J + 1]; score [j + 1] = temp; }} System.out.print ("th" + (i + 1) + "Résultat de tri de séquence:"); for (int a = 0; a <score.length; a ++) {System.out.print (score [a] + "/ t"); } System.out.println (""); } System.out.print ("Résultat de tri final:"); for (int a = 0; a <score.length; a ++) {System.out.print (score [a] + "/ t"); }}}
Performance / complexité de l'algorithme
Nous ignorons le temps où les variables de boucle sont automatiquement augmentées et initialisées. Analysez d'abord le nombre de comparaisons de l'algorithme. Il est facile de voir que le tri des bulles ci-dessus sans aucune amélioration sera effectué en rondes N-1, quelles que soient les données d'entrée, et le nombre de fois que chaque cycle de tri doit être comparé diminue de N-1 à 0. Ensuite, le nombre total de comparaisons est (N-1) + (N-2) + ... + 2 + 1 = (N-1) N / 2--R (N ^ 2) / 2. (Puisque je ne sais pas comment faire des carrés ici, ici, j'utilise n ^ 2 pour représenter les carrés, le même ci-dessous)
Jetons un coup d'œil au nombre d'affectations. L'affectation ici fait référence à l'opération d'échange. Pour le code ci-dessus, 1 échange est égal à trois affectations. Comme il n'est pas nécessaire d'échanger à chaque fois, le nombre d'opérations d'affectation est lié aux données d'entrée. Dans le meilleur des cas, c'est-à-dire que lorsque la commande est au début, le nombre d'affectations est 0. Dans le pire des cas, le nombre d'affectations est (n-1) n / 2. En supposant que les données d'entrée sont une distribution moyenne (ou "complètement aléatoire"), alors environ la moitié du nombre d'échanges. D'après les résultats ci-dessus, nous pouvons obtenir le cas moyen, le nombre d'affectations étant de 3/2 * (n ^ 2) / 2 = 3/4 * (n ^ 2).
En résumé, en tout cas, la complexité de l'espace de tri des bulles (espace supplémentaire) est toujours O (1).
améliorer
La complexité temporelle optimale est montrée lorsque les données sont complètement commandées, qui est O (n). Dans d'autres cas, il est presque toujours o (n ^ 2). Par conséquent, l'algorithme fonctionne le mieux lorsque les données sont essentiellement commandées.
Cependant, comment le code ci-dessus peut-il avoir une complexité O (n)? En fait, comme ce qui précède se concentre sur les idées de base, ce n'est que le cas le plus simple. Pour faire de l'algorithme, avoir une complexité de O (n) dans le meilleur des cas, certaines améliorations doivent être apportées. Le code amélioré est:
public static void bubblesort (int [] arr) {int temp = 0; Swap booléen; for (int i = arr.length - 1; i> 0; --i) {// La longueur de chaque type doit être swap = false; pour (int j = 0; j <i; ++ j) {// du premier élément à l'élément i-th if (arr [j]> arr [j + 1]) {temp = arr [j]; arr [j] = arr [J + 1]; arr [j + 1] = temp; swap = true; }} // Loop j if (swap == false) {break; }} // Loop i} // Méthode BubblesortEn fait, comme le tri des bulles est à peine utilisé dans le cas de grandes quantités de données, les variables booléennes ajoutées lors de l'utilisation de petites données provoqueront en fait des frais généraux supplémentaires. Je pense donc personnellement que l'algorithme amélioré ci-dessus n'est que purement théorique. Habituellement, écrivez simplement le précédent en bouillonnant le tri.
Stabilité de l'algorithme
Il est facile de voir que lorsque les éléments voisins sont égaux, nous n'avons pas besoin d'échanger leurs positions, donc le tri des bulles est un type stable.
Algorithme Scénarios applicables
L'idée du tri des bulles est simple et le code est simple, ce qui convient particulièrement pour le tri de petites données. Cependant, en raison de la forte complexité de l'algorithme, il ne convient pas à une utilisation lorsque le volume de données est important. Si vous devez l'utiliser lorsqu'il y a plus de données, il est préférable d'améliorer l'algorithme, comme la sélection de la méthode de tri.