Ich versuche, mein C ++ zu verbessern, indem ich ein Programm erstelle, das eine große Anzahl von Zahlen zwischen 1 und 10 ^ 6 benötigt. Die Buckets, die die Zahlen in jedem Durchgang speichern, sind ein Array von Knoten (wobei Knoten eine von mir erstellte Struktur ist, die einen Wert und ein nächstes Knotenattribut enthält).
Nach dem Sortieren der Zahlen in Buckets nach dem niedrigstwertigen Wert, habe ich das Ende eines Bucket-Punktes an den Anfang eines anderen Buckets (damit ich die gespeicherten Zahlen schnell abrufen kann, ohne die Reihenfolge zu stören). Mein Code hat keine Fehler (entweder Compilieren oder Runtime), aber ich habe eine Wand in Bezug darauf getroffen, wie ich die verbleibenden 6 Iterationen lösen werde (da ich den Zahlenbereich kenne).
Das Problem, das ich habe, ist, dass anfänglich die Zahlen der radixSort-Funktion in Form eines int-Arrays übergeben wurden. Nach der ersten Iteration der Sortierung werden die Zahlen nun im Array von Strukturen gespeichert. Gibt es irgendeine Möglichkeit, dass ich meinen Code überarbeiten könnte, so dass ich nur eine for-Schleife für die 7 Iterationen habe, oder brauche ich eine for-Schleife, die einmal ausgeführt wird, und eine weitere Schleife darunter, die 6 mal ausgeführt wird, bevor die vollständig sortierten zurückgegeben werden Liste?
%Vor%Ich denke, dass Sie Ihre Lösung stark überkomplizieren. Sie können Radix mit dem einzelnen Array implementieren, das in der Eingabe empfangen wird, wobei die Buckets in jedem Schritt durch ein Array von Indizes dargestellt werden, die den Startindex jedes Buckets im Eingabearray markieren.
Tatsächlich könnten Sie das sogar rekursiv tun:
%Vor% Natürlich wird buckets[i+1] - buckets[i] einen Pufferüberlauf verursachen, wenn i 9 ist, aber ich habe die zusätzliche Überprüfung oder Lesbarkeit ausgelassen; Ich vertraue darauf, dass du weißt, wie du damit umgehen kannst.
Damit müssen Sie nur radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) aufrufen und Ihr Array sollte sortiert sein.
Da Ihre Werte im Bereich von 0 ... 1.000.000
liegenSie können ein int-Array der Größe 1.000.001 erstellen und das Ganze in zwei Durchgängen erledigen
Initiiere das zweite Array auf alle Nullen.
Machen Sie einen Durchlauf durch Ihr Eingabe-Array und verwenden Sie den Wert als Index um den Wert im zweiten Array zu erhöhen.
Sobald Sie das tun, ist der zweite Durchgang einfach. gehe durch das zweite Array und jedes Element sagt dir, wie oft das ist Nummer erschien im ursprünglichen Array. Verwenden Sie diese Informationen zum erneuten Befüllen Ihr Eingabe-Array.
Um den Prozess mit besserer Speicherverwaltung zu beschleunigen, erstellen Sie eine Matrix für die Zählungen, die in Indizes konvertiert werden, indem Sie einen einzelnen Durchlauf über das Array ausführen. Ordnen Sie ein zweites temp-Array der gleichen Größe wie das ursprüngliche Array zu und radix sort zwischen den beiden Arrays, bis das Array sortiert ist. Wenn eine ungerade Anzahl von Radix-Sortierdurchläufen ausgeführt wird, muss das temporäre Array am Ende wieder in das ursprüngliche Array kopiert werden.
Um den Prozess weiter zu beschleunigen, verwenden Sie die Basis 256 anstelle der Basis 10 für die Radix-Sortierung. Dies erfordert nur einen Scan-Durchlauf, um die Matrix- und vier Radix-Sortierdurchgänge zu erzeugen, um die Sortierung durchzuführen. Beispielcode:
%Vor%Tags und Links algorithm c++ sorting radix-sort