So verwenden Sie den Zählsortieralgorithmus in C++

So verwenden Sie den Zählsortieralgorithmus in C++

Der Zählsortieralgorithmus ist ein relativ einfacher und effizienter Sortieralgorithmus, der für Szenarien geeignet ist, in denen ganzzahlige Sequenzen sortiert werden. Seine Grundidee besteht darin, zu bestimmen, wie viele Elemente vor jedem Element kleiner als es selbst sind, und so seine Position im geordneten Array zu bestimmen.

Die Schritte des Zählsortieralgorithmus lauten wie folgt:

1. Finden Sie den Maximalwert im zu sortierenden Array, um die Länge des Zählarrays zu bestimmen.
2. Erstellen Sie ein Zählarray mit der Länge des Maximalwerts plus eins und initialisieren Sie es auf 0.
3. Durchlaufen Sie das zu sortierende Array, zählen Sie die Anzahl der Vorkommen jedes Elements und speichern Sie die statistischen Ergebnisse im Zählarray.
4. Transformieren Sie das Zählarray so, dass der Wert jeder Position gleich der Summe ihrer vorherigen Positionswerte ist.
5. Erstellen Sie ein temporäres Array mit derselben Länge wie das zu sortierende Array, um die Sortierergebnisse zu speichern.
6. Durchlaufen Sie das zu sortierende Array von hinten nach vorne, bestimmen Sie die Position jedes Elements im sortierten Ergebnis basierend auf dem Zählarray und speichern Sie die Elemente in einem temporären Array.
7. Kopieren Sie die Ergebnisse des temporären Arrays zurück in das zu sortierende Array, um die Sortierung abzuschließen.

Das Folgende ist ein Beispielcode eines in der C++-Sprache implementierten Zählsortieralgorithmus:

#include <iostream>
#include <vector>

using namespace std;

void countingSort(vector<int>& arr) {
    int max_val = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }

    vector<int> count(max_val + 1, 0);

    for (int i = 0; i < arr.size(); i++) {
        count[arr[i]]++;
    }

    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    vector<int> temp(arr.size());
    for (int i = arr.size() - 1; i >= 0; i--) {
        temp[count[arr[i]] - 1] = arr[i];
        count[arr[i]]--;
    }

    for (int i = 0; i < arr.size(); i++) {
        arr[i] = temp[i];
    }
}

int main() {
    vector<int> arr = {5, 1, 4, 3, 2};
    countingSort(arr);

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

    return 0;
}

Im obigen Code verwenden wir ein Hilfszählarray, um die Anzahl der Vorkommen jedes Elements zu zählen und dann die Anzahl der Vorkommen zu berechnen jedes Elements durch Verformung Position in sortierten Ergebnissen. Abschließend kopieren wir die sortierten Ergebnisse zurück in das ursprüngliche Array.

Anhand des obigen Beispielcodes können wir den Implementierungsprozess des Zählsortieralgorithmus sehen. Seine zeitliche Komplexität beträgt O(n+k), wobei n die Länge der zu sortierenden Sequenz und k die Summe ist maximaler Elementwert und minimaler Elementwert. Die Differenz beträgt plus eins.

Zusammenfassend ist der Zählsortieralgorithmus ein einfacher, aber effizienter Sortieralgorithmus, der für Szenarien geeignet ist, in denen ganzzahlige Sequenzen sortiert werden. Durch den Einsatz geeigneter Datenstrukturen und Algorithmen können wir die Sortieraufgabe besser bewältigen.

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