Tri bulle
Toi de bulles, quand j'ai vu cet algorithme, je me suis souvenu du dicton "Les décimales flottent et les grands chiffres coulent". Grâce à la comparaison de couche par couche, les décimales flottent à la surface et les grands nombres "coulent les pierres au fond de l'eau". Cela réalise l'effet du tri. Le tri des bulles est un algorithme de tri simple. Il visite à plusieurs reprises la séquence à tri, compare deux éléments à la fois et les échange s'ils sont incorrects. Le travail de visite de la séquence est répété jusqu'à ce qu'aucun échange ne soit nécessaire, c'est-à-dire que la séquence a été triée. L'origine de cet algorithme est parce que plus l'élément "flottera lentement" vers le haut de la séquence via l'échange.
Le fonctionnement de l'algorithme de tri des bulles est le suivant:
1. Comparez les éléments adjacents. Si le premier est plus grand que le second, échangez-les contre les deux.
2. Faites le même travail pour chaque paire d'éléments adjacents, à partir de la première paire à la dernière paire à la fin. À ce stade, le dernier élément devrait être le plus grand nombre.
3. Répétez les étapes ci-dessus pour tous les éléments sauf le dernier.
4. Continuez à répéter les étapes ci-dessus pour de moins en moins d'éléments à chaque fois jusqu'à ce qu'il n'y ait pas de paires de nombres qui doivent être comparés.
Diagramme de processus de tri à bulles:
Exemple de code
classe publique Bubblesort {public static int [] bubblesort (int [] array) {for (int i = 0; i <array.length; i ++) {for (int j = 0; j <array.length-i-1; j ++) {if (array [j]> array [j + 1]) {int temp = array [j]; Array [J] = Array [J + 1]; Array [J + 1] = temp; }} System.out.println ("th" + (i + 1) + "tri"); for (int k = 0; k <array.length; k ++) {System.out.print (array [k] + ""); } System.out.println (); } Return Array; } / ** * @param args * / public static void main (String [] args) {int [] array = {7,3,9,5,6,8,1}; Bubblesort (tableau); }}Résultat d'impression:
1ère commande 3 7 5 6 8 1 9 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 6th order 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th Order 3 5 6 7 8 9Sorting 5th Order 3 5 6 7 8 9Sorting 5th Order 3 5 6 7 8 9Sorting 5th Order 3 5 6 7 8 9Sorting 5th Order 3 5 6 7 8 9Sorting 5th Order 5th Order Order 5th Order 5th Order 5th Order 5th Order.
Recherche binaire
Après avoir trié la commande, nous devons également trouver les données que nous voulons. La recherche dichotomique est un algorithme de section et de base couramment utilisé. La recherche binaire consiste à rechercher et à comparer de la position centrale des données triées, similaires à la paire moyenne du bâton en bois, de sorte qu'elle est également appelée pliage et demi-recherche. Il s'agit d'une méthode de recherche plus efficace.
[Exigences de recherche binaire]: 1. La structure de stockage séquentielle doit être adoptée. 2. La clé doit être organisée de manière ordonnée en fonction de la taille du mot-clé.
[PROS et inconvénients] Les avantages de la méthode de recherche en demi-finale sont qu'il a moins de temps de comparaison, de vitesse de recherche rapide et de bonnes performances moyennes; Son inconvénient est que la table à rechercher est une table commandée et il est difficile à insérer et à supprimer. Par conséquent, la méthode à moitié d'abondance convient aux listes ordonnées qui ne sont pas fréquemment modifiées et sont fréquemment trouvées.
[Pensée d'algorithme] Tout d'abord, comparez les mots clés enregistrés dans la position moyenne du tableau avec les mots clés de recherche. Si les deux sont égaux, la recherche réussira; Sinon, le tableau sera divisé en deux sous-tables avec l'enregistrement de position intermédiaire. Si les mots clés enregistrés en position centrale sont supérieurs au mot clé de recherche, recherchez davantage la sous-table précédente, sinon la recherche plus approfondie de la sous-table suivante.
Répétez le processus ci-dessus jusqu'à ce que l'enregistrement qui remplit les conditions soit trouvé afin que la recherche soit réussie, ou jusqu'à ce que le tableau des enfants n'existe pas, la recherche échoue pour le moment.
[Complexité de l'algorithme] En supposant que la longueur du tableau est n, sa complexité d'algorithme est o（log（n））， la complexité du temps le pire des cas est O(n)。
Exemple de code
package com.somnus.array; / ** * Méthode de recherche binaire * @Author Compaq * * / classe publique BinarySearch {public static int binararysearch (int [] array, int valum) {int low = 0; int high = array.length-1; int middle = 0; while (bas <= high) {middle = (Low + High) / 2; // 0 6 4 6 6 6 pour (int i = 0; i <array.length; i ++) {System.out.print (array [i] + ""); if (i == Middle) // 3 5 6 Imprimez le délimiteur immédiatement après le point central {System.out.print ("##"); }} System.out.println (); if (array [middle] == valeur) {return middle; } if (valeur <array [middle]) {high = middle - 1; } if (valeur> array [middle]) {low = middle + 1; }} return -1; } / ** * @param args * / public static void main (String [] args) {int [] array = {7,3,9,5,6,8,1}; int [] array1 = bubblesort.bubblesort (array); int index = binarysearch (array1,1); System.out.println ("local:" + index); }}Résultat d'impression:
1ère commande 3 7 5 6 8 1 9Sorting 2nd Order 3 5 6 7 1 8 9Sorting 3 5 6 1 7 8 9Sorting 4th Order 3 5 1 6 7 8 9Sorting 5th Commande 3 1 5 6 7 8 9Sorting 6th Order
Analyse et résumé
Dans les algorithmes de recherche, la dichotomie est la plus rapide, mais doit être une séquence ordonnée. Ce sont les fondements des algorithmes, et nous devons encore faire beaucoup d'efforts pour expérimenter, résumer, absorber et nous en tenir à l'apprentissage des algorithmes.