So verwenden Sie den Radix-Sortieralgorithmus in C++

So verwenden Sie den Radix-Sortieralgorithmus in C++

Der Radix-Sortieralgorithmus ist ein nicht vergleichender Sortieralgorithmus, der die Sortierung durch Aufteilen der zu sortierenden Elemente in einen begrenzten Satz von Ziffern abschließt. In C++ können wir den Radix-Sortieralgorithmus verwenden, um eine Menge von Ganzzahlen zu sortieren. Im Folgenden besprechen wir anhand konkreter Codebeispiele ausführlich, wie der Basissortieralgorithmus implementiert wird.

1. Algorithmusidee
   Die Idee des Radix-Sortieralgorithmus besteht darin, die zu sortierenden Elemente in einen begrenzten Satz digitaler Bits zu unterteilen und die Elemente dann nacheinander nach jedem Bit zu sortieren. Nachdem die Sortierung für jedes Bit abgeschlossen ist, werden die Elemente entsprechend der Reihenfolge dieses Bits neu organisiert, und dann wird die Sortierung für das nächste Bit fortgesetzt, bis alle Bits sortiert sind.
2. Spezifische Implementierungsschritte
   (1) Zuerst müssen wir die Anzahl der Ziffern im Maximalwert aller zu sortierenden Elemente bestimmen. Dadurch wird bestimmt, wie viele Sortierrunden wir durchführen müssen.

(2) Dann müssen wir ein Hilfsarray und ein Zählarray erstellen. Das Hilfsarray wird zum Speichern temporärer Ergebnisse während des Sortiervorgangs verwendet, und das Zählarray wird zum Aufzeichnen der Häufigkeit des Vorkommens jeder Zahl verwendet.

(3) Als nächstes müssen wir mehrere Sortierrunden durchführen. Bei jeder Sortierrunde wird das Array entsprechend der aktuellen Bitgröße neu organisiert.

(4) In jeder Sortierrunde müssen wir das zu sortierende Array durchlaufen, den aktuellen Bitwert jedes Elements als Index verwenden und die Elemente in den entsprechenden Bucket legen.

(5) Dann müssen wir die Anzahl der Elemente in jedem Bucket zählen, was mithilfe eines Zählarrays aufgezeichnet werden kann.

(6) Als nächstes müssen wir die Position der Elemente in jedem Bucket im Hilfsarray bestimmen, indem wir das Array zählen. Dies kann durch Zählen der Präfixsumme der Elemente im Array ermittelt werden.

(7) Abschließend überschreiben wir die Elemente im Hilfsarray in das zu sortierende Array, um eine Sortierrunde abzuschließen.

(8) Wiederholen Sie die Schritte (3) bis (7), bis alle Bits sortiert sind.

3. Codebeispiel
   Das Folgende ist ein Codebeispiel, das C++ verwendet, um den Radix-Sortieralgorithmus zu implementieren:

#include <iostream>
#include <vector>

using namespace std;

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());

    int digit = 1;
    vector<int> temp(arr.size());
    while (maxVal / digit > 0) {
        vector<int> count(10, 0);

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

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

        for (int i = arr.size() - 1; i >= 0; i--) {
            temp[count[(arr[i] / digit) % 10] - 1] = arr[i];
            count[(arr[i] / digit) % 10]--;
        }

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

        digit *= 10;
    }
}

int main() {
    vector<int> arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
    radixSort(arr);

    cout << "排序结果：";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

Im obigen Beispielcode ermitteln wir zunächst den Maximalwert im zu sortierenden Array, um zu bestimmen, wie viele Runden von Sortierung erforderlich. Dann haben wir ein Hilfsarray und ein Zählarray erstellt. Als nächstes führen wir mehrere Sortierrunden durch, um das Array entsprechend der aktuellen Bitgröße neu zusammenzusetzen. Abschließend geben wir die sortierten Ergebnisse aus.

Zusammenfassung:
Mit dem Radix-Sortieralgorithmus können wir eine Menge von Ganzzahlen in C++ sortieren. Die Kernidee des Radix-Sortieralgorithmus besteht darin, die zu sortierenden Elemente in einen begrenzten Satz numerischer Bits zu unterteilen und die Elemente dann nacheinander nach jedem Bit zu sortieren. Dieser nicht vergleichende Sortieralgorithmus kann das Sortierproblem einer Menge von Ganzzahlen effektiv lösen.

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