문자열을 내림차순으로 정렬합니다.

Question

내림차순으로 문자열을 정렬하는 C++ (STL)의 문자열 함수가 있습니까? 그렇지 않으면 O (n) 시간에 내림차순으로 문자열을 정렬하는 방법.

Answer 1

C++에서 문자열을 정렬하는 함수가 있으며 std::less이 아닌 std::greater과 비교하여 내림차순으로 정렬 할 수 있습니다.

그러나 O (n) 시간은 정렬되지 않습니다 (O (n log n)가됩니다). 이를 위해 버킷 정렬을 사용해야합니다.

Answer 2

가장 간단한 방법은 std :: sort, 다음 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) 평균 경우있어) 중 하나를 사용할 수 없습니다. 그래서 : 아니오, 표준 라이브러리에는 적절한 함수가 하나도 없습니다.

Pigeonhole sort 또는 다른 버킷 정렬과 같은 것이 작동 할 수 있습니다. 가능한 256 자의 빈도를 추적하고 그 후에 문자열을 다시 작성하십시오.

char 값에 대해 원하는 어휘 순서에 대한 아이디어가 필요하지만 올바른 (내림차순) 순서로 버킷을 걷는 것으로 문자열을 다시 작성한다는 점에 유의하십시오.