Explication détaillée d'exemples d'implémentation du tri par insertion en Java

Cet article présente principalement la structure des données Java et le tri par insertion d'algorithmes, et analyse les concepts, classifications, principes, méthodes de mise en œuvre et précautions associées du tri par insertion Java sous forme d'exemples. Les amis dans le besoin peuvent s'y référer

<.>L'exemple de cet article décrit le type d'insertion de la structure de données et de l'algorithme Java. Je le partage avec vous pour votre référence. Les détails sont les suivants :

Après examen, j'ai trié les connaissances sur le tri dans la structure des données. Je l'ai écrit parce que je souhaite le partager avec plus de personnes. La chose la plus importante est de simplement faire une sauvegarde pour référence future.

Tri

1 Concept :

Séquence à n enregistrements {R1, R2, .......,Rn} (notez ici : 1,2,n sont les séquences du tableau ci-dessous, et les suivantes ont le même effet), et la séquence des mots-clés correspondants est {K1,K2,. ... .....,Kn}. Par tri, il est nécessaire de trouver un arrangement p1, p2,...pn de la séquence d'indice actuelle 1,2,...,n, tel que le mot-clé correspondant satisfasse la relation non décroissante (non croissante) suivante , soit : Kp1<=Kp2<=Kpn, obtenant ainsi une séquence d'enregistrements ordonnés par mot-clé : {Rp1, Rp2,.....,Rpn}.

2. Classification

Le tri peut être divisé en deux catégories en fonction de la différence de mémoire occupée par les données lors du tri.

Tri interne : L'ensemble du processus de tri est entièrement effectué en mémoire, comme suit :

Tri par insertion (tri par insertion directe, tri par demi-insertion, tri Hill ; 🎜>Tri par sélection, tri par sélection d'arbre, tri par tas)

Tri par fusion

Tri par affectation (multi-clés) ; Implémentation de la table de séquence du tri par mots, du tri par base chaînée et du tri par base) );

Tri externe : En raison de la grande quantité de données d'enregistrement à trier, la mémoire ne peut pas accueillir toutes les données. Le tri nécessite l'utilisation de périphériques de stockage externes (

tri sur disque, tri sur bande

).

3. Stabilité

Supposons qu'il existe plusieurs enregistrements avec le même mot-clé dans la séquence à trier. Supposons Ki=Kj(1<=i<=n,1<=j<=n,i != j), si Ri mène Rj (c'est-à-dire i<=j) dans la séquence avant le tri, nous obtenons après le tri Si Ri toujours en tête de Rj dans la séquence, la méthode de tri utilisée est dite stable ; à l'inverse, lorsque la relation dominante d'un même mot-clé change au cours du processus de tri, la méthode de tri utilisée est instable ;

Tri par insertion : Idée : Chaque fois qu'un enregistrement à trier est inséré à la position appropriée dans le sous-fichier précédemment trié en fonction de sa taille de clé, jusqu'à ce que tous les enregistrements soient insérés jusqu'à la fin .

Tri par insertion directe :

Idée d'algorithme : Supposons que les enregistrements à trier soient stockés dans le

tableau

R [1..n] dans. Initialement, R[1] forme une zone ordonnée et la zone non ordonnée est R[2..n]. De i=2 jusqu'à i=n, ​​​​R[i] est inséré séquentiellement dans la zone ordonnée actuelle R[1..i-1] pour générer une zone ordonnée contenant n enregistrements.

Le code implémenté en java est le suivant :

Analyse de l'algorithme :

Le meilleur des cas est que l'enregistrement à être trié lui-même a été organisé dans l'ordre selon les mots-clés, le pire des cas est que les enregistrements à trier sont classés dans l'ordre inverse selon les mots-clés La complexité temporelle est O(N^2), et la complexité spatiale est O(1);

Cet algorithme est un algorithme de tri stable :

est plus adapté aux situations où le nombre d'enregistrements à trier est petit et fondamentalement dans l'ordre

.

package exp_sort;
public class DirectInsertSort {
  public static void DircstSort(int array[]) {
    int j;
    // 循环从第二个数开始，第一个数用做存放待插入的记录
    for (int i = 1; i < array.length; i++) {
      int temp = array[i];
      // 寻找插入位置
      for (j = i; j > 0 && temp < array[j - 1]; j--) {
        array[j] = array[j - 1];
      }
      // 将待插入记录插入到已经排序的序列中
      array[j] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    DircstSort(array);
  }
}

Tri par demi-insertion : Idée d'algorithme : les performances de la recherche divisée par deux pour les tables ordonnées sont meilleures que celles de la recherche séquentielle. Le code d'implémentation de l'algorithme est le suivant :

Analyse de l'algorithme : est un algorithme de tri stable, meilleur que le algorithme d'insertion directe Il réduit considérablement le nombre de comparaisons entre les mots-clés, donc

est plus rapide que l'algorithme de tri par insertion directe

, mais le nombre de déplacements d'enregistrement n'a pas changé, donc la

complexité temporelle de l'algorithme de tri par insertion réduit de moitié est toujours O(n^2),

est le même que l'algorithme de tri par insertion directe.

Espace supplémentaire O(1).

package exp_sort;
public class BinaryInsertSort {
  public static void sort(int array[]) {
    int temp, low, mid, high;
    for (int i = 1; i < array.length; i++) {
      temp = array[i];
      low = 0;
      high = i -1;
      //确定插入位置
      while (low <= high) {
        mid = (low + high) / 2;
        if (temp < array[mid]) {
          high = mid - 1;
        } else {
          low = mid + 1;
        }
      }
      //记录依次向后移动
      for (int j = i; j >= low + 1; j--) {
        array[j] = array[j-1];
      }
      //插入记录
      array[low] = temp;
    }
    for (int i = 0; i < array.length; i++) {
      System.out.print(array[i] + " ");
    }
    System.out.println("\n");
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array[] = {38, 62, 35, 77, 55, 14, 35, 98};
    sort(array);
  }
}

【Recommandations associées】1 Recommandation spéciale : "php. Téléchargement de la version "Programmer Toolbox" V0.1

2. Tutoriel vidéo gratuit Java

3. Manuel en ligne YMP

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!