Exemple de tri par insertion InsertionSort de tri Java

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

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!