So verwenden Sie den Einfügungssortierungsalgorithmus in C++

Verwenden Sie den Einfügungssortierungsalgorithmus in C++, um die Array-Sortierung zu implementieren.

Einfügungssortierung ist ein einfacher, aber effektiver Sortieralgorithmus, der die zu sortierenden Elemente einzeln in die sortierte Liste einfügt und schließlich eine geordnete Liste erhält. In diesem Artikel wird erläutert, wie die Programmiersprache C++ zum Implementieren des Einfügungssortierungsalgorithmus verwendet wird, und es werden spezifische Codebeispiele gegeben.

Algorithmusidee:
Die Grundidee der Einfügungssortierung besteht darin, das Array in sortierte Intervalle und unsortierte Intervalle zu unterteilen. Jedes Mal wird ein Element aus dem unsortierten Bereich ausgewählt und an der entsprechenden Position des sortierten Bereichs eingefügt, bis der unsortierte Bereich leer ist.

Spezifische Schritte:

1. Durchlaufen Sie das Array und fügen Sie die Elemente des unsortierten Intervalls nacheinander in das sortierte Intervall ein.
2. Vergleichen Sie jedes Element im unsortierten Bereich mit den Elementen im sortierten Bereich, um die Einfügeposition zu ermitteln.
3. Fügen Sie das Element an der entsprechenden Position des sortierten Intervalls ein und verschieben Sie die Elemente des sortierten Intervalls eine Position nach hinten.

Codebeispiel:
Das Folgende ist ein Beispielcode, der die Programmiersprache C++ verwendet, um den Einfügungssortierungsalgorithmus zu implementieren:

#include <iostream>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = { 5, 2, 4, 6, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "原始数组：";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    insertionSort(arr, n);

    std::cout << "排序后的数组：";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

Im obigen Code definieren wir eine Funktion namens insertionSort的函数来实现插入排序。在main函数中，我们定义了一个待排序的数组并调用insertionSort zum Sortieren. Abschließend geben wir die sortierten Ergebnisse an die Konsole aus.

Ausführungsergebnisse:
Ursprüngliches Array: 5 2 4 6 1 3
Sortiertes Array: 1 2 3 4 5 6

Zusammenfassung:
Durch den obigen Beispielcode können wir sehen, wie der Einfügungssortierungsalgorithmus in C++ zum Sortieren verwendet wird das Array. Obwohl die Einfügungssortierung einfach ist, beträgt ihre zeitliche Komplexität O(n^2) und ihre Sortiereffizienz für große Datenmengen ist gering. Wenn in praktischen Anwendungen eine große Datenmenge sortiert werden muss, empfiehlt es sich, einen effizienteren Sortieralgorithmus zu verwenden, z. B. Schnellsortierung oder Zusammenführungssortierung.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Einfügungssortierungsalgorithmus in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!