Exemple simple de tri par insertion Java

Cet article présente principalement en détail des exemples de tri par insertion simple Java, qui ont une certaine valeur de référence. Les amis intéressés peuvent s'y référer

1 Concepts de base

Le. L'opération de base du tri par insertion consiste à insérer une donnée dans les données ordonnées qui ont été triées, de manière à obtenir une nouvelle donnée ordonnée avec le nombre plus un. L'algorithme est adapté au tri d'une petite quantité de données, et le temps est complexe. est O(n^2). C'est une méthode de tri stable. L'algorithme d'insertion divise le tableau à trier en deux parties : la première partie contient tous les éléments du tableau, sauf le dernier élément (ce qui fait au tableau un espace de plus pour avoir une position d'insertion), et la deuxième partie ne contient que celui-ci. élément (c'est-à-dire l'élément à insérer). Une fois la première partie triée, ce dernier élément est inséré dans la première partie triée.

2. Implémentation du code Java

public class InsertSort {
  public static void inserSort(int[] array){
    if (array==null||array.length<2){
      return;
    }

    for (int i=1;i<array.length;i++){ //默认第一个元素为有序队列，从第二个元素开始循环插入
      int position=array[i];     //设置第二个元素为要插入的数据
      int j=i-1;
      while (j>=0&&position<array[j]){
        array[j+1]=array[j];   //如果插入发数小于第j个元素，将第j个数向后移
        j--;
      }
      array[j+1]=position;     //插入
    }
  }

  public static void main(String ags[]){
    int[] array={2,6,4,7,3,-1};
    inserSort(array);
    for (int i=0;i<array.length;i++){
      System.out.print(array[i]+" ");
    }
  }
}

3. Analyse des performances

Stable
Complexité spatiale O(1)
Complexité temporelle O(n2)
Pire des cas : ordre inverse, nécessité de déplacer n*(n-1)/2 éléments
Meilleur des cas Situation : Positif ordre, pas besoin de déplacer les éléments

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!