exemple de tri par insertion directe Java

Les facteurs qui affectent l'efficacité du tri sont généralement comparés sous trois aspects : le nombre de comparaisons de données, le nombre de déplacements de données et la quantité d'espace mémoire occupée.
Faisons une comparaison générale du tri à bulles, du tri par sélection, du tri par insertion et du tri rapide. L'algorithme de tri à bulles n'est généralement pas utilisé car son nombre de comparaisons et de déplacements est le plus grand parmi plusieurs algorithmes de tri. Son seul avantage est que l'algorithme est simple et facile à comprendre, il peut donc être utilisé lorsque la quantité de données est faible. sera une valeur d'application. Le tri par sélection a le même nombre de comparaisons que le tri à bulles, qui est n au carré, mais il réduit le nombre d'échanges au minimum, il peut donc être appliqué lorsque la quantité de données est petite et que l'échange de données prend plus de temps que la comparaison. données. Sélectionnez trier.
Dans la plupart des cas, lorsque la quantité de données est relativement petite ou essentiellement ordonnée, l'algorithme de tri par insertion est le meilleur choix. Pour trier de plus grandes quantités de données, le tri rapide est généralement la meilleure méthode.
L'algorithme de tri ci-dessus prend très peu d'espace mémoire et ne nécessite qu'une variable supplémentaire pour stocker temporairement les éléments de données lors de l'échange. Il n’y a donc aucune comparaison possible quant à la taille de l’espace mémoire occupé.

Le nombre de comparaisons du tri par insertion est toujours de n au carré, mais en général, il est deux fois plus rapide que le tri à bulles et légèrement plus rapide que le tri par sélection. Il est souvent utilisé dans les étapes finales d’algorithmes de tri complexes, tels que le tri rapide.

Algorithme : Après le traitement i-1, L[1..i-1] a été trié. La ième passe de traitement insère uniquement L[i] dans la position appropriée de L[1..i-1],
faisant de L[1..i] à nouveau une séquence triée. Pour atteindre cet objectif, nous pouvons utiliser la comparaison séquentielle.
Comparez d'abord L[i] et L[i-1]. Si L[i-1] Sinon, échangez les positions de L[i] et L[i-1], et continuez à comparer L[i-1] et L[i-2] jusqu'à une certaine position j (1≤j≤i -1),
jusqu'à L[j] ≤ L[j 1]
Avantages : moins de nombre d'éléments mobiles, un seul espace auxiliaire est nécessaire
Complexité temporelle n*n
quand le tri doit être effectué C'est une bonne méthode de tri lorsque le nombre d'enregistrements n est petit. Mais quand n est très grand, c'est inapproprié

Par exemple : int[] valeurs = { 5, 2, 4, 1, 3 }

Processus de tri :
; 1ère fois : 2,5,4,1,3
La 2ème fois : 2,4,5,1,3
La 3ème fois : 1,2,4,5,3
La 4ème fois : 1,2 ,3,4,5

code java :

public class InsertSort {
   public static void main(String[] args) {
       int[] values = { 5, 2, 4, 1, 3 };
       sort(values);
       for (int i = 0; i < values.length; ++i) {
           System.out.println(values[i]);
       }
   }
   public static void sort(int[] values) {
       int temp;
       int j = 0;
       for (int i = 1; i < values.length; i++) {
           if(values[i]<values[i-1])//此处的判断很重要，这里体现了插入排序比冒泡排序和选择排序快的原因。
           {
               temp = values[i];
               //数据往后移动
               for (j=i-1; j>=0 && temp<values[j]; j--)
               {
                   values[j+1] =values[j];
               }
               //将数据插入到j+1位置
               values[j+1] =temp;
               System.out.print("第" + (i + 1) + "次：");
               for (int k = 0; k < values.length; k++) {
                   System.out.print(values[k]+",");
               }
               System.out.println("");
           }
       }
   }
}

Deuxième exemple

package cn.cqu.coce.xutao;
public class zhijiecharu {

 public static void main(String args[]){

 int a[]={1,2,34,67,8,9,6,7,56,34,232,99};
 int i,j,k;
 for(i=0;i<a.length;i++)
  System.out.print(a[i]+"\t");
 System.out.println();
 for(i=1;i<a.length;i++){

  for(j=i-1;j>=0;j--)
   if(a[i]>a[j])
    break;

  if(j!=i-1){
   int temp;
   temp=a[i];
   for(k=i-1;k>j;k--)
    a[k+1]=a[k];
   a[k+1]=temp;  
  }  
 }
 for(i=0;i<a.length;i++)
  System.out.print(a[i]+"\t");
 System.out.println();
  }
}

Pour plus d'articles sur les exemples de tri par insertion directe Java, veuillez faire attention au site Web PHP chinois !