C ++에서 자연스러운 정렬 알고리즘을 구현하는 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/642213

  •  22-07-2019
  •  | 
  •  

문제

나는 텍스트와 숫자로 구성된 문자열을 정렬하고 있습니다. 나는 분류가 영숫자가 아닌 숫자로 숫자 부품을 정렬하기를 원합니다.

예를 들어 INTE : ABC1DEF, ..., ABC9DEF, ABC10DEF

대신 : ABC10DEF, ABC1DEF, ..., ABC9DEF

누구든지 이것에 대한 알고리즘을 알고 있습니까 (특히 C ++)

감사

도움이 되었습니까?

해결책

나는 물었다 이 정확한 질문 (Java에서는 있지만) 그리고 지적되었습니다 http://www.davekoelle.com/alphanum.html 여기에는 많은 언어로 알고리즘과 IT의 구현이 있습니다.

다른 팁

이것은 자연 분류라고합니다. 알고리즘이 있습니다 여기 유망한 것처럼 보입니다.

비 ASCII 문자에 대한 문제에주의하십시오 (참조 Jeff의 블로그 항목 주제에 대해).

C ++에 대한 몇 가지 자연적인 정렬 구현을 사용할 수 있습니다. 간단한 리뷰 :

  • natural_sort<> - 부스트를 기반으로합니다.
    • 내 테스트에서는 다른 옵션보다 약 20 배 느려집니다.
  • Dirk Jagdmann 's alnum.hpp, Dave Koelle의 기반 알파늄 알고리즘
    • Maxint의 값에 대한 잠재적 인 정수 오퍼 오버 로우 문제
  • 마틴 수영장 natsort -C로 작성되었지만 C ++에서 사소하게 사용할 수 있습니다.
    • 내가 보았던 유일한 C/C ++ 구현은 Case Insensitive 버전을 제공하는 것으로 보았습니다.이 버전은 "자연적인"종류의 우선 순위가 높을 것 같습니다.
    • 다른 구현과 마찬가지로 실제로 소수점을 구문 분석하지는 않지만 특별한 케이스를 이끄는 제로 (주요 0이있는 것은 분수로 가정)를 수행합니다. 이는 약간 이상하지만 잠재적으로 유용합니다.
    • PHP는이 알고리즘을 사용합니다.

부분적으로 다시 게시 나의 또 다른 대답:

bool compareNat(const std::string& a, const std::string& b){
    if (a.empty())
        return true;
    if (b.empty())
        return false;
    if (std::isdigit(a[0]) && !std::isdigit(b[0]))
        return true;
    if (!std::isdigit(a[0]) && std::isdigit(b[0]))
        return false;
    if (!std::isdigit(a[0]) && !std::isdigit(b[0]))
    {
        if (a[0] == b[0])
            return compareNat(a.substr(1), b.substr(1));
        return (toUpper(a) < toUpper(b));
        //toUpper() is a function to convert a std::string to uppercase.
    }

    // Both strings begin with digit --> parse both numbers
    std::istringstream issa(a);
    std::istringstream issb(b);
    int ia, ib;
    issa >> ia;
    issb >> ib;
    if (ia != ib)
        return ia < ib;

    // Numbers are the same --> remove numbers and recurse
    std::string anew, bnew;
    std::getline(issa, anew);
    std::getline(issb, bnew);
    return (compareNat(anew, bnew));
}

toUpper() 기능:

std::string toUpper(std::string s){
    for(int i=0;i<(int)s.length();i++){s[i]=toupper(s[i]);}
    return s;
    }

용법:

std::vector<std::string> str;
str.push_back("abc1def");
str.push_back("abc10def");
...
std::sort(str.begin(), str.end(), compareNat);

본질적으로 구문 분석 문제를 해결하려면 상태 기계 (일명 유한 상태 자동)가가는 길입니다. 위의 솔루션에 불만족 한 I는 성능 측면에서 제안 된 C/C ++ 변형을 능가하는 간단한 1 패스 초기 보석 알고리즘을 썼으며, 수치 데이터 유형 오버플로 오류로 어려움을 겪지 않으며 필요한 경우 사례 무감각성을 추가하기가 쉽습니다. .

출처를 찾을 수 있습니다 여기

// -1: s0 < s1; 0: s0 == s1; 1: s0 > s1
static int numericCompare(const string &s0, const string &s1) {
    size_t i = 0, j = 0;
    for (; i < s0.size() && j < s1.size();) {
        string t0(1, s0[i++]);
        while (i < s0.size() && !(isdigit(t0[0]) ^ isdigit(s0[i]))) {
            t0.push_back(s0[i++]);
        }
        string t1(1, s1[j++]);
        while (j < s1.size() && !(isdigit(t1[0]) ^ isdigit(s1[j]))) {
            t1.push_back(s1[j++]);
        }
        if (isdigit(t0[0]) && isdigit(t1[0])) {
            size_t p0 = t0.find_first_not_of('0');
            size_t p1 = t1.find_first_not_of('0');
            t0 = p0 == string::npos ? "" : t0.substr(p0);
            t1 = p1 == string::npos ? "" : t1.substr(p1);
            if (t0.size() != t1.size()) {
                return t0.size() < t1.size() ? -1 : 1;
            }
        }
        if (t0 != t1) {
            return t0 < t1 ? -1 : 1;
        }
    }
    return i == s0.size() && j == s1.size() ? 0 : i != s0.size() ? 1 : -1;
}

나는 그것이 당신이 원하는지 확실하지 않습니다. 어쨌든, 당신은 시도해 볼 수 있습니다 :-)

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top