Tri d'insert direct
L'idée d'insérer directement le tri est facile à comprendre, il ressemble à ceci:
1. Divisez le tableau à tri en deux parties: trié et non trié. Au début, le premier élément est considéré comme trié.
2. Commencez avec le deuxième élément, trouvez la position appropriée de l'élément dans le sous-réseau trié et insérez-le.
3. Répétez le processus ci-dessus jusqu'à ce que le dernier élément soit inséré dans le sous-réseau ordonné.
4. Le tri est terminé.
Exemple:
L'idée est simple, mais le code n'est pas aussi facile à écrire que le tri des bulles. Tout d'abord, comment déterminer la bonne position? Supérieur ou égal à la gauche, inférieur ou égal à la droite? Non, de nombreuses conditions aux limites doivent être prises en compte et il y a trop de jugements. Deuxièmement, l'insertion d'éléments dans un tableau nécessitera inévitablement le déplacement d'un grand nombre d'éléments. Comment contrôler leur mouvement?
En fait, ce n'est pas un problème avec l'algorithme lui-même, et cela a quelque chose à voir avec le langage de programmation. Parfois, l'algorithme lui-même est déjà très mature, et il doit encore être légèrement modifié en ce qui concerne le langage de programmation spécifique. Ce dont nous parlons ici, c'est l'algorithme Java, alors parlons de Java.
Pour résoudre le problème ci-dessus, nous avons fait un peu de raffinement de la deuxième étape. Nous ne commençons pas la comparaison de la position de départ de la sous-table, mais commençons la comparaison inverse de la queue de la sous-table. Tant qu'il est plus grand que le nombre qui doit être inséré, nous retournons en arrière. Jusqu'à ce que le nombre ne soit pas supérieur au nombre, le nombre à insérer sera placé dans cette position vide. Par conséquent, nous pouvons écrire le code suivant:
Insertarray.java
classe publique insertArray {// array privé long [] arr; // la taille des données valides dans le tableau des int elems privés; // Par défaut Constructeur public insertarray () {arr = new Long [50]; } public insertArray (int max) {arr = new long [max]; } // insérer des données publiques void insert (valeur longue) {arr [elems] = valeur; elems ++; } // Afficher les données publiques void affiche () {for (int i = 0; i <elems; i ++) {System.out.print (arr [i] + ""); } System.out.println (); } // insérer le tri public void insertsort () {long select = 0l; for (int i = 1; i <elems; i ++) {select = arr [i]; int j = 0; pour (j = i; j> 0 && arr [j - 1]> = select; j--) {arr [j] = arr [j - 1]; } arr [j] = select; }}} Classe de test:
TestiNsertArray.java
classe publique TesInsertArray {public static void main (String [] args) {insertarray iarr = new INSERTARRAY (); iarr.insert (85); iarr.insert (7856); iarr.insert (12); iarr.insert (8); iarr.insert (5); iarr.insert (56); iarr.display (); iarr.insertsort (); iarr.display (); }} Résultat d'impression:
Performance / complexité de l'algorithme
Discutons maintenant de la complexité temporelle de l'algorithme d'insertion directe. Quelle que soit l'entrée, l'algorithme effectue toujours des tours de tri n-1. Cependant, comme le point d'insertion de chaque élément est incertain et considérablement affecté par les données d'entrée, sa complexité n'est pas certaine. Nous pouvons discuter des situations les meilleures, les pires et moyennes.
1. Meilleur cas: D'après les caractéristiques de l'algorithme, on peut voir que lorsque le tableau à disposer lui-même est en ordre positif (le tableau est ordonné et que l'ordre est le même que l'ordre requis, qui est en ordre croissant sous notre prémisse de discussion). La raison en est que dans ce cas, chaque élément ne doit être comparé qu'une seule fois et n'a pas besoin d'être déplacé. La complexité temporelle de l'algorithme est O (n);
2. Pire des cas: Évidemment, lorsque le tableau à disposer est dans l'ordre inverse, c'est le pire des cas. Dans ce cas, notre nombre de comparaisons par tour est I-1 et le nombre de missions est i. Le nombre total de fois est la somme des n premiers termes de la série 2n-1, c'est-à-dire n ^ 2. La complexité temporelle de l'algorithme est O (n ^ 2);
3. Situation moyenne: D'après l'analyse ci-dessus, nous pouvons obtenir que le nombre d'opérations de l'algorithme dans la situation moyenne est approximativement (n ^ 2) / 2 (note: le calcul ici est basé sur l'affectation et la comparaison. S'il est basé sur le mouvement et la comparaison, il est approximativement n ^ 2/4). De toute évidence, la complexité du temps est toujours o (n ^ 2).
Quant à la complexité spatiale de l'algorithme, tous les mouvements sont effectués à l'intérieur des données. Le seul frais général est que nous avons introduit une variable temporaire (certaines structures de données sont appelées "sentinelles" dans les livres), donc sa complexité spatiale (espace supplémentaire) est O (1).
Stabilité de l'algorithme
Étant donné que vous n'avez besoin que de trouver une position qui n'est pas supérieure au nombre actuel et n'a pas besoin d'échanger, l'insertion du tri est une méthode de tri stable.
Variantes d'algorithme
S'il y a beaucoup de données à disposer, cela provoquera beaucoup de frais généraux à chaque fois que vous regardez par derrière. Afin d'améliorer la vitesse de recherche, la recherche binaire peut être utilisée pour l'optimisation des performances. Parce que l'efficacité de la recherche binaire est très élevée, la complexité O (n) est assurée et l'efficacité de la recherche peut être considérablement améliorée lorsqu'il y a plus de données ou que les données d'entrée ont tendance à être au pire. Dans certains livres, cette méthode est appelée pliage et tri à moitié insert. Son implémentation de code est assez compliquée et peut être publiée si vous avez du temps à l'avenir.
De plus, il y a des types d'insert à 2 voies et des types d'insertion de table. Le type d'insertion à 2 voies est encore amélioré sur la base du pliage et de la demi-insertion, et son nombre de mouvements est considérablement réduit, environ n ^ 2/8. Cependant, il n'évite pas le nombre de mouvements et ne réduit pas le niveau de complexité. Le tri de l'insertion de table modifie complètement la structure de stockage et ne déplace pas les enregistrements, mais une liste liée doit être maintenue, et le pointeur de la liste liée est modifié au lieu de déplacer des enregistrements. Par conséquent, sa complexité est toujours o (n ^ 2).
Pour le tri insertion à 2 voies et le tri de l'insertion de table, vous pouvez vous référer au livre "Data Structure" édité par Yan Weimin et Wu Weimin.
Algorithme Scénarios applicables
Le tri de l'insertion n'est pas applicable lorsque le tableau est important en raison de la complexité de O (n ^ 2). Cependant, lorsqu'il y a relativement peu de données, c'est un bon choix, généralement utilisé comme extension pour le tri rapide. Par exemple, dans l'algorithme de tri de STL et l'algorithme QSORT de STDLIB, le tri des inserts est utilisé comme complément au tri rapide et est utilisé pour trier un petit nombre d'éléments. Par exemple, dans la mise en œuvre de la méthode de tri utilisée dans JDK 7 Java.util.arrays, lorsque la longueur du tableau à tri est inférieure à 47, le tri des inserts sera utilisé.