Sortierung der Zeichenfolge in absteigender Reihenfolge.

Question

Gibt es eine Zeichenfolgefunktion in C++ (STL), um eine Zeichenfolge in absteigender Reihenfolge zu sortieren. Wenn nicht, wie sortiere ich einen String in absteigender Reihenfolge in O (n) Zeit.

Answer 1

Es gibt eine Funktion in C++, um eine Zeichenfolge zu sortieren, und Sie können sie in absteigender Reihenfolge sortieren, indem Sie sie mit std::greater anstelle von std::less vergleichen.

Es wird jedoch nicht in O (n) Zeit sortieren (es wird O (n Log n) sein). Sie müssen dafür eine Bucket-Sortierung verwenden.

Answer 2

Der einfachste Weg wäre std :: sort it, dann std :: reverse it. Sortierung ist vom Algorithmus. Reverse ist vom Dienstprogramm.

#include <iostream> 
#include <string> 
#include <algorithm> 
#include <utility> 

int main(){ 

    std::string str = "Hello Beep 5412"; 

    std::cout << "normal string:" << std::endl; 
    std::cout << str << std::endl; 


    std::sort(str.begin(), str.end()); //sort it 
    std::reverse(str.begin(), str.end()); //reverse it 

    std::cout << "\nsorted, descending:" << std::endl; 
    std::cout << str << std::endl; 

    system("pause"); 
    return 0; 
} 

Ausgang:

normal string: 
Hello Beep 5412 

sorted, descending: 
polleeeHB5421 

Answer 3

Wenn Sie die lineare Zeit benötigen, können Sie keine der Allzweck-Sortieralgorithmen verwenden (sie sind alle O(n log n) durchschnittlichen Fall). Also: Nein, in der Standardbibliothek gibt es keine einzige geeignete Funktion.

So etwas wie eine Pigeonhole sort oder andere Bucket-Sortierung würde funktionieren: Verfolgen Sie einfach die Häufigkeit von jedem der 256 möglichen Zeichen, und schreiben Sie die Zeichenfolge danach neu.

Beachten Sie, dass Sie immer noch eine Vorstellung von der lexikalischen Reihenfolge haben müssen, die Sie für Ihre char-Werte haben möchten, aber dann schreiben Sie Ihre Zeichenfolge einfach neu, indem Sie in der richtigen (absteigenden) Reihenfolge über Ihre Buckets laufen.