Explication détaillée de l'algorithme de tri par insertion directe et de l'implémentation du code de la version Java associée

Tri par insertion directe

L'idée du tri par insertion directe est facile à comprendre. Elle est la suivante :
1. Divisez le tableau à trier en parties triées et non triées. le premier Un élément est considéré comme trié.
2. À partir du deuxième élément, recherchez la position appropriée de l'élément dans le sous-tableau trié et insérez-le à cette position.
3. Répétez le processus ci-dessus jusqu'à ce que le dernier élément soit inséré dans le sous-tableau ordonné.
4. Tri terminé.

Exemple :
L'idée est très simple, mais le code n'est pas aussi simple à écrire qu'un tri à bulles. Tout d’abord, comment déterminer l’emplacement approprié ? Supérieur ou égal à gauche, inférieur ou égal à droite ? Non, il y a beaucoup de conditions aux limites à considérer, et il y a trop de jugements. Deuxièmement, l'insertion d'éléments dans un tableau nécessitera inévitablement de déplacer 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, mais quelque chose à voir avec le langage de programmation. Parfois, l’algorithme lui-même est déjà très mature et doit encore être légèrement modifié en ce qui concerne le langage de programmation spécifique. Ce dont nous parlons ici, c'est de l'algorithme Java, parlons donc de Java.
Afin de résoudre le problème ci-dessus, nous affinons légèrement la deuxième étape. Nous ne commençons pas la comparaison à partir de la position de départ du sous-tableau, mais commençons la comparaison à partir de la fin du sous-tableau dans l'ordre inverse. Tant qu'il est supérieur au nombre à insérer, nous reculerons. Jusqu'à ce que le nombre ne soit pas supérieur à ce nombre, le nombre à insérer est placé à cette position vacante. Par conséquent, nous pouvons écrire le code suivant :
InsertArray.java

public class InsertArray {
  // 数组
  private long[] arr;
 
  // 数组中有效数据的大小
  private int elems;
 
  // 默认构造函数
  public InsertArray() {
    arr = new long[50];
  }
 
  public InsertArray(int max) {
    arr = new long[max];
  }
 
  // 插入数据
  public void insert(long value) {
    arr[elems] = value;
    elems++;
  }
 
  // 显示数据
  public void display() {
    for (int i = 0; i < elems; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.println();
  }
 
  // 插入排序
  public void insertSort() {
    long select = 0L;
    for(int i = 1; i < elems; i++) {
      select = arr[i];
      int j = 0;
      for(j = i;j > 0 && arr[j - 1] >= select; j--) {
        arr[j] = arr[j - 1];
      }
      arr[j] = select;
    }
  }
}

Classe de test :
TestInsertArray.java

public class TestInsertArray {
  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();
  }
 
}

Performance/complexité de l'algorithme
Maintenant discutons de la complexité temporelle de l'algorithme d'insertion directe. Quelle que soit l’entrée, l’algorithme effectue toujours n-1 tours de tri. Cependant, comme le point d'insertion de chaque élément est incertain et fortement affecté par les données d'entrée, sa complexité n'est pas certaine. Nous pouvons discuter des situations les meilleures, les pires et les moyennes.
1. Meilleure situation : d'après les caractéristiques de l'algorithme, on peut savoir qu'il est préférable que le tableau à trier lui-même soit dans l'ordre positif (le tableau est dans l'ordre et l'ordre est le même que l'ordre requis , qui est l'ordre croissant basé sur la prémisse de notre 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. Dans le pire des cas : évidemment, le pire des cas est lorsque le tableau à trier est dans l'ordre inverse. Dans ce cas, notre nombre de comparaisons à chaque tour est i. -1, le nombre d'affectations est i. Le degré total 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. analyse, nous pouvons obtenir l'algorithme de cas moyen. Le nombre d'opérations est d'environ (n^2)/2 (Remarque : le calcul ici est basé sur l'affectation et la comparaison. S'il est basé sur le mouvement et la comparaison, il est d'environ n^2 /4). Évidemment, la complexité temporelle est toujours O(n^2 ).
Quant à la complexité spatiale de l'algorithme, tous les mouvements sont effectués au sein des données. Le seul surcoût est que nous introduisons une variable temporaire (appelée "sentinelle" dans certains ouvrages sur la structure des données), donc sa complexité spatiale (espace supplémentaire) est O(1).

Stabilité de l'algorithme
Étant donné qu'il vous suffit de trouver une position qui n'est pas supérieure au nombre actuel et que vous n'avez pas besoin d'échanger, le tri par insertion directe est une méthode de tri stable.

Variante de l'algorithme
S'il y a beaucoup de données à trier, alors la recherche de l'arrière vers l'avant à chaque fois entraînera beaucoup de temps système. Afin d'améliorer la vitesse de recherche, la recherche binaire (Recherche binaire. ) peut être utilisé pour améliorer les performances. Étant donné que la recherche binaire est très efficace et garantit une complexité O(㏒n), elle peut considérablement améliorer l'efficacité de la recherche lorsqu'il y a beaucoup de données ou que les données d'entrée tendent vers le pire des cas. Cette méthode est appelée tri par demi-insertion dans certains livres. Son implémentation de code est relativement compliquée, et je le publierai quand j'aurai le temps dans le futur.
De plus, il existe un tri par insertion bidirectionnel et un tri par insertion de table. Le tri par insertion bidirectionnelle est encore amélioré sur la base du tri par demi-insertion, et son nombre de mouvements est considérablement réduit, environ n ^ 2/8. Cependant, cela n’élimine pas le nombre de mouvements ni ne réduit le niveau de complexité. Le tri par insertion de table modifie complètement la structure de stockage et ne déplace pas les enregistrements, mais il nécessite de maintenir une liste chaînée et de remplacer les enregistrements déplacés par des modifications de pointeur dans la liste chaînée. Par conséquent, sa complexité est toujours O(n^2).
Pour le tri par insertion bidirectionnelle et le tri par insertion de table, vous pouvez vous référer au livre "Data Structure" édité par Yan Weimin et Wu Weimin.

Scénarios applicables de l'algorithme
En raison de la complexité de O(n^2), le tri par insertion n'est pas applicable lorsque le tableau est grand. Cependant, il s'agit d'un bon choix lorsque les données sont relativement petites et est généralement utilisé comme extension d'un tri rapide. Par exemple, dans l'algorithme de tri de STL et l'algorithme qsort de stdlib, le tri par insertion est utilisé en complément du tri rapide pour trier un petit nombre d'éléments. Pour un autre exemple, dans l'implémentation de la méthode de tri utilisée dans le JDK 7 java.util.Arrays, lorsque la longueur du tableau à trier est inférieure à 47, le tri par insertion sera utilisé.

Pour des explications plus détaillées sur l'algorithme de tri par insertion directe et les articles liés à l'implémentation du code de la version Java, veuillez faire attention au site Web PHP chinois !