Algorithme de tri : tri par insertion et tri shell

Aujourd'hui, nous allons parler de deux méthodes de tri classiques, le tri par insertion et le tri par shell. Vous pouvez considérer le tri shell comme une version améliorée du tri par insertion.

Tri par insertion

La description de l'algorithme de tri par insertion est un algorithme de tri très simple et intuitif. Sa complexité est similaire à celle du tri à bulles. Le principe de fonctionnement est de construire une séquence ordonnée. Pour les données non triées, parcourez d'arrière en avant dans la séquence triée pour trouver la position correspondante et insérez-la.

J'ai trouvé une animation sur Internet comme suit :

Le processus est le suivant :

• De le premier élément Dans un premier temps, l'élément peut être considéré comme ayant été trié

• Sortir l'élément suivant et scanner d'arrière en avant dans la séquence des éléments triés

• Si l'élément (trié) est supérieur au nouvel élément, déplacez l'élément à la position suivante

• Répétez l'étape 3 jusqu'à ce que vous trouviez l'élément trié qui est ; inférieur ou égal à la position du nouvel élément ;

• Après avoir inséré le nouvel élément dans cette position

• Répétez les étapes 2 à 5.

Implémentation du code (le langage C est utilisé ici) :

void insort (int arr[], int len)
{
    int i,current,preindex;
    for (i = 1; i < len; i++) {
        preindex = i - 1;
        current = arr[i];
        while (preindex >= 0 && current < arr[preindex]) {
            arr[preindex + 1] = arr[preindex];
            preindex --;
        }
        arr[preindex + 1] = current;
    }
}

tri des shells

Après comprendre le tri par insertion, il est facile de comprendre le tri shell.

L'algorithme de tri Shell a été inventé par D.L. Shell en 1959. Son idée de base est de comparer d'abord des éléments distants, ce qui peut rapidement réduire un grand nombre de situations désordonnées, facilitant ainsi le travail ultérieur. La distance entre les éléments comparés diminue progressivement jusqu'à atteindre 1, moment auquel le tri devient un échange d'éléments adjacents.

Le tri Hill consiste à regrouper les enregistrements selon un certain incrément dans le tableau et à utiliser l'algorithme de tri par insertion directe pour trier chaque groupe à mesure que l'incrément diminue progressivement, chaque groupe contient de plus en plus de mots-clés. est réduit à 1, le fichier entier est divisé en un seul groupe et l'algorithme se termine.

Démonstration du processus (cette image a également été trouvée en ligne) :

Implémentation du code (le langage C est utilisé ici) :

void shell_sort (int arr[], int len)
{
    int gap,i,current,preindex;
    for (gap = len / 2; gap > 0; gap /= 2) {
        for (i = gap; i < len; i++) {
            preindex = i - gap;
            current = arr[i];
            while (preindex >= 0 && current < arr[preindex]) {
                arr[preindex + gap] = arr[preindex];
                preindex -= gap;
            }
            arr[preindex + gap] = current;
        }
    }
}

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!