Maison > Java > javaDidacticiel > le corps du texte

Exemple de tri par insertion InsertionSort de tri Java

黄舟
Libérer: 2017-09-16 10:34:20
original
1610 Les gens l'ont consulté

Tri par insertion implémentation


Le tri par insertion, c'est comme faire un pari, comme une double boucle. Lorsque vous piochez des cartes, vous prenez une carte à la fois et comparez cette carte avec les cartes précédentes une par une. Choisissez où insérer cette carte et jouez aux cartes plus facilement après avoir organisé la séquence. Sinon, il serait difficile de les retrouver un par un. Cela n’est pas non plus propice à la situation globale du jeu de cartes. Regardez l'image ci-dessous

En supposant que le 7 de trèfle soit tiré pour la première fois, il n'y a pas lieu de trier. Parce qu'il n'y a qu'une seule carte

, alors je tire 10 de trèfle . Puisque 10 est supérieur à 7, il n’est pas nécessaire de trier.

Ensuite, piochez des cartes. J'ai découvert que j'avais dessiné 5 trèfles . N'hésitez pas à cette heure, 14 heures, ce n'est vraiment pas grave. Jeter les cartes de manière décisive

Ensuite, nous comparons 5 et 10. 5 est inférieur à 10, alors échangez vos places.

Prenez 5 et comparez-le avec 7. 5 est plus petit que 7. Alors échangez les positions de 5 et 7 pour obtenir .

C'est déjà réglé à ce moment-là. Le principe est comme ça.

Parce que c'est relativement simple. Collez le code directement

// O(n^2) 最坏的情况
    // 最好的情况 O(n)
    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i ; j > 0; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }
    
    public static void sort(Comparable[] a, int low, int hi) {
        for (int i = low; i <= hi ; i++) {
            for (int j = i ; j > low; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }

InsertSort
Copier après la connexion

Analyse des performances

Le pire des cas est La carte tirée à chaque fois est la plus petite. À ce stade, vous devez passer de la queue à la tête à chaque fois. Le temps est proportionnel à N^2

Le meilleur des cas est qu'il ait été trié. Parce que c'est déjà réglé. Ainsi, les cartes tirées à chaque fois n'ont pas besoin d'être triées. Le temps est proportionnel à N


Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
source:php.cn
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal