Sortieralgorithmus: Einfügungssortierung und Shell-Sortierung

Heute werden wir über zwei klassische Sortiermethoden sprechen: Einfügungssortierung und Shell-Sortierung. Sie können sich die Shell-Sortierung als eine verbesserte Version der Einfügungssortierung vorstellen.

Insertion-Sortierung

Die Algorithmusbeschreibung von Insertion-Sort ist ein sehr einfacher und intuitiver Sortieralgorithmus. Seine Komplexität ähnelt der Blasensortierung. Das Arbeitsprinzip besteht darin, eine geordnete Sequenz zu erstellen. Scannen Sie die sortierte Sequenz von hinten nach vorne, um die entsprechende Position zu finden, und fügen Sie sie ein.

Ich habe eine Animation aus dem Internet wie folgt gefunden:

Der Ablauf ist wie folgt:

• Von Das erste Element kann zunächst als sortiert betrachtet werden.

• Nehmen Sie das nächste Element heraus und scannen Sie es von hinten nach vorne in der Reihenfolge der sortierten Elemente

Wenn das Element (sortiert) größer als das neue Element ist, verschieben Sie das Element an die nächste Position.
Wiederholen Sie Schritt 3, bis Sie das sortierte Element gefunden haben kleiner oder gleich der neuen Elementposition;
Nach dem Einfügen des neuen Elements an dieser Position
Wiederholen Sie die Schritte 2 bis 5.
Code-Implementierung (hier wird C-Sprache verwendet):

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;
    }
}

Shell-Sortierung Danach Wenn Sie die Einfügungssortierung verstehen, ist es leicht, die Shell-Sortierung zu verstehen.

Der Shell-Sortieralgorithmus wurde 1959 von D.L. Shell erfunden. Seine Grundidee besteht darin, zuerst entfernte Elemente zu vergleichen, was eine große Anzahl ungeordneter Situationen schnell reduzieren und so die spätere Arbeit erleichtern kann. Der Abstand zwischen den verglichenen Elementen nimmt allmählich ab, bis er auf 1 reduziert wird. Zu diesem Zeitpunkt wird die Sortierung zum Austausch benachbarter Elemente.

Hill-Sortierung besteht darin, Datensätze nach einem bestimmten Inkrement in der Tabelle zu gruppieren und den Sortieralgorithmus für direkte Einfügungen zu verwenden, um jede Gruppe mit zunehmender Inkrementierung zu sortieren auf 1 reduziert, die gesamte Datei in eine Gruppe aufgeteilt und der Algorithmus beendet.

Prozessdemonstration (dieses Bild wurde auch online gefunden):

Code-Implementierung (hier wird die Sprache C verwendet):

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;
        }
    }
}

Das obige ist der detaillierte Inhalt vonSortieralgorithmus: Einfügungssortierung und Shell-Sortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!