10
비교를 통한 문자열 정렬 (예 : 표준 QuickSort + strcmp와 같은 기능)은 약간 느릴 수 있습니다. 특히 긴 문자열이 공통 접두사를 공유하는 경우 (비교 함수는 O (s) 시간이 걸립니다. 문자열 길이), 따라서 표준 솔루션은 O (s * nlog n)의 복잡성을 갖습니다. 알고있는 빠른 알고리즘이 있습니까?효율적인 문자열 정렬 알고리즘
A
답변
14
문자열이 특정 문자로만 구성된다는 것을 알고 있다면 (대부분의 경우) BucketSort 또는 RadixSort 변종을 사용할 수 있습니다.
+1
나는 첫째로 quicksort를 사용하여 문자열의 접미사를 정렬하고 나머지는 radixsort를 사용하여 하이브리드 솔루션을 만들었습니다. 그것은 꽤 빨리 작동합니다. 일부 문자열이 길어지기 때문에 순수한 기수 정렬로 가고 싶지 않았지만 접미사는 다소 다르기 때문에 quicksort를 사용하여 정렬하는 것이 좋습니다. 나는 여전히 개선의 여지가 있다고 생각하지만, 현재이 해결책으로 충분하다. 감사 –
9
trie을 만들 수 있는데, 이는 O(s*n)이어야합니다.
+0
+1, 복잡성을 계산하는 데 너무 많은 시간을 낭비했습니다 :-) –
+0
@tyz : trie 에의 삽입은'O (s)'이어야하고'n '번해야합니다. –
+1
나는 그것에 대해 생각해야한다. 간단한 구현에서 약간 메모리가 부족한 것 같다. –
2
"Sedgewick Multikey quick sort"(Sedgewick은 유명한 알고리즘 교과서를 C와 Java로 작성했습니다)를 검색하십시오. 그의 알고리즘은 상대적으로 구현하기 쉽고 빠릅니다. 위에 언급 한 문제를 피할 수 있습니다. 더 빠른 것으로 주장하는 버스트 정렬 알고리즘이 있지만 구현에 대해 알지 못합니다.
알고리즘을 설명하고 C# 코드뿐만 아니라 Sedgewick 코드에 대한 참조를 가지고있는 Fast String Sort in C# and F# 문서가 있습니다. (공개 : Sedgewick의 논문을 기반으로 쓴 기사와 코드).
관련 문제
- 1. 문자열 오버랩을 찾는 효율적인 알고리즘
- 2. Levenstein 알고리즘 결과를 사용하여 정렬 문자열 배열
- 3. 정렬 알고리즘
- 4. 정렬 알고리즘
- 5. 효율적인 알고리즘 제안
- 6. 효율적인 타이머 알고리즘
- 7. 효율적인 단어 스크램블 알고리즘
- 8. 큰 수의 집합에 대한 가장 효율적인 정렬 알고리즘
- 9. 문자열 발생 알고리즘 계산
- 10. 효율적인 트리 정렬
- 11. 대규모 콜렉션에서 AVL 트리를 빌드하기위한 효율적인 알고리즘
- 12. lucene에서 사용하는 문자열 일치 알고리즘
- 13. 관련 제출물을 찾는 효율적인 알고리즘
- 14. 효율적인 접미어 배열 알고리즘 C#
- 15. 불규칙 다각형을위한 효율적인 패킹 알고리즘
- 16. 비교 정렬 알고리즘 복잡성
- 17. 순차 정렬 알고리즘
- 18. Java 정렬 알고리즘
- 19. 바이너리 삽입 정렬 알고리즘
- 20. 도움말이 정렬 알고리즘 결정
- 21. C# 문자열 정렬 VS Oracle 문자열 정렬
- 22. 문자열/정수 배열을 정렬 할 수있는 알고리즘 만들기
- 23. 효율적인 기능은 현재 문자열
- 24. 하스켈에서 효율적인 문자열 구현
- 25. 정렬 문자열
- 26. 효율적인 Out-Of-Core 정렬
- 27. 부분 문자열 알고리즘
- 28. 문자열 비교 알고리즘
- 29. Java에서 문자열 검색 알고리즘
- 30. 문자열 일치 알고리즘
코드가 느려 집니까? 그렇지 않다면 걱정하지 마십시오. – tjameson
이 문제가 발생할 때가 처음은 아니지만 그렇습니다.이 분류는 프로그램이 많은 시간을 보내는 부분입니다. –