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

Tri

1 Concept :

2. Classification

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 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 (

).

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

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 :

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 :

.

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

, 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.

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!