文字列を降順でソートします。

Question

文字列を降順で並べ替えるためのC++（STL）の文字列関数はありますか？ そうでなければ、O（n）時間内に降順で文字列をソートする方法。

Answer 1

文字列をソートする機能がC++にあり、std::lessではなくstd::greaterと比較するように指示することで降順に並べ替えることができます。

ただし、O（n）時間でソートされません（O（n log n）になります）。そのためにバケットソートを使用する必要があります。

Answer 2

最も簡単な方法はstd :: sort it、次にstd :: reverse itです。 ソートはアルゴリズムからのものです。 逆はユーティリティからです。

#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; 
} 

出力：

normal string: 
Hello Beep 5412 

sorted, descending: 
polleeeHB5421 

Answer 3

あなたは線形時間が必要な場合は、汎用的なソートアルゴリズム（彼らはすべてのO(n log n)平均的なケースだ）のいずれかを使用することはできません。そうです：いいえ、標準ライブラリには適切な関数が1つしかありません。

Pigeonhole sortまたは他のバケットソートのようなものがあります：可能な256文字のそれぞれの頻度を追跡し、後でその文字列を書き換えます。

char値に必要な語彙順序付けのアイデアは依然として必要ですが、正しい（降順）順序でバケツを歩いて文字列を書き直すだけです。