编程知识 cdmana.com

Mise à jour du tri des bulles [tri des cocktails]

C'est ma participation11Le défi du mois de juin16Oh, mon Dieu.,Voir les détails de l'événement:2021Un dernier défi

Bienvenue au publicOpenCoder,Viens te faire des amis avec moi~‍

Un..Concept de tri des cocktails

Ordre des cocktails,Est une mise à jour de l'algorithme de tri des bulles.Chaque élément de l'ordre des bulles peut ressembler à une bulle,Selon sa taille,Un petit mouvement vers un côté du tableau.L'algorithme compare les éléments de gauche à droite à chaque tour,En coursUnidirectionnelDe l'échange de position.Et le tri des cocktails est basé sur la comparaison des éléments et le processus d'échange devientDans les deux sensDe.OkCocktailTri aussi appelé tri bidirectionnel des bulles、Ordre de mélange des cocktails、 Tri par agitation 、 Ordre des ondulations 、 Tri aller - retour ou tri happy hour , C'est une déformation de l'ordre des bulles .

Les cocktails sont classés au pire ou le nombre moyen de fois qu'ils sont consommés est O(n²), Mais si la séquence a été triée en grande partie au début , On s'approche. O(n).

2.. Déduction logique

Analyse des problèmes:

Tableau existant, Les données sont : [2,3,4,5,6,7,8,1], Nous utilisons ces données pour analyser :

image-20211013110818725

Le processus de tri des bulles est le suivant :

image-20211013111356725

image-20211013162036391

Analyse des résultats:

Élément 2、3、4、5、6、7、8C'est déjà ordonné., Il suffit de mettre l'élément 1 Juste au bon endroit , Mais c'est quand même fait 7Rotation, C'est trop gênant . Si vous pouviez juste 1 Ajustement de la position , La séquence est ordonnée . Le tri des cocktails est exactement ce qui va résoudre ce problème .

Idées d'optimisation:

Processus détaillé du cocktail :

Première ronde(Comme pour le tri des bulles,8Et1Echange)

image-20211013162754692

Deuxième tour: Ça commence à être différent , Nous comparons de droite à gauche en échange .

image-20211013163352045

image-20211013163912858

Troisième tour: Bien qu'il soit en fait ordonné , Mais le processus n'est pas terminé .

Au troisième tour du tri des cocktails , Besoin de refaire la comparaison de gauche à droite pour l'échange .

1Et2Comparaison,Position inchangée;2Et3Comparaison,Position inchangée;3Et4Comparaison,Position inchangée...7Et8 La position de comparaison reste inchangée .Aucun élément à échanger, Prouver l'ordre actuel ,Fin du tri.

Résumé:

J'aurais dû.7 Scénario de tri des roues ,Avec3 La roue est réglée , Le tri des cocktails est un algorithme si ingénieux .

Et l'idée de trier les cocktails , Le processus de tri est comme un pendule , Première ronde de gauche à droite , Deuxième tour de droite à gauche , Troisième tour de gauche à droite ...

Trois. Algorithme de tri des cocktails

Code:

    public static void sort(int[] array) {
        //Nombre de cycles
        int count = 0;
        // Échange de données variables temporaires 
        int tmp = 0;
        for (int i = 0; i < array.length / 2; i++) {
            System.out.println("No" + (++count) + "Sous - cycle");
            // La valeur initiale de chaque tour est true, Marques ordonnées :true Représentant l'ordre 
            boolean isSorted = true;
            //Nombre impair de Tours,Comparer et échanger de gauche à droite
            for (int j = i; j < array.length - i - 1; j++) {
​
                if (array[j] > array[j + 1]) {
                    tmp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = tmp;
                    //L'échange a eu lieu, Pas dans l'ordre , Remplacer la marque par false
                    isSorted = false;
                }
            }
            //Ordre
            if (isSorted) {
                break;
            }
            // Avant les rondes paires ,Oui.isSortedRe - Tag astrue
            isSorted = true;
            System.out.println("No" + (++count) + "Sous - cycle");
            //Nombre pair de Tours, Direction comparer et échanger de droite à gauche 
            for (int j = array.length - i - 1; j > i; j--) {
                if (array[j] < array[j - 1]) {
                    tmp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = tmp;
                    isSorted = false;
                }
            }
            //Ordre
            if (isSorted) {
                break;
            }
        }
    }
Copier le Code

Résultats obtenus:

No1Sous - cycle
No2Sous - cycle
No3Sous - cycle
[1, 2, 3, 4, 5, 6, 7, 8]
Copier le Code

Résumé:

Ce code est l'implémentation originale du tri des cocktails . La grande boucle en dehors du Code contrôle tous les tours de tri , Le grand cycle contient deux petits cycles à l'intérieur ,No1 Petits cycles de gauche à droite pour comparer et échanger des éléments ,No2 Une petite boucle compare de droite à gauche et échange des éléments .

L'avantage du cocktail est , Avec la plupart des éléments déjà ordonnés ,Réduire le nombre de Tours triés; Et les inconvénients sont évidents , C'est que la quantité de code a presque doublé .

Bienvenue au publicOpenCoder,Viens te faire des amis avec moi~‍

版权声明
本文为[Opencoder]所创,转载请带上原文链接,感谢
https://cdmana.com/2021/11/20211125174151698l.html

Tags mise jour du tri des
Scroll to Top