Làm thế nào để thực hiện một thuật toán sắp xếp tự nhiên trong c + +?

Question

Tôi sắp xếp các chuỗi bao gồm văn bản và số. Tôi muốn sắp xếp các phần số như số, chứ không phải chữ số.

Ví dụ tôi muốn: abc1def, ..., abc9def, abc10def

thay vì: abc10def, abc1def, ..., abc9def

Có ai biết một thuật toán cho việc này (đặc biệt là trong C++)

Cảm ơn

Answer 1

Tôi đã yêu cầu this exact question (although in Java) và được chỉ đến http://www.davekoelle.com/alphanum.html có thuật toán và triển khai bằng nhiều ngôn ngữ.

Answer 2

Điều này được gọi là phân loại tự nhiên. Có một thuật toán here có vẻ đầy hứa hẹn.

Cẩn thận với các vấn đề với ký tự không phải ASCII (xem Jeff's blog entry về chủ đề).

Answer 3

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

Tôi không phải là rất chắc chắn nếu nó là bạn muốn, dù sao, bạn có thể có một thử :-)

Answer 4

Một số triển khai loại tự nhiên đối với C++ có sẵn. Đánh giá ngắn:

• natural_sort<> - dựa trên Boost.Regex.
  • Trong các thử nghiệm của tôi, nó chậm hơn khoảng 20 lần so với các tùy chọn khác.
• Dirk Jagdmann của alnum.hpp, dựa trên nguyên tiềm năng alphanum algorithm
  • Dave Koelle của overlow vấn đề cho các giá trị trên MAXINT
• Martin Pool natsort - viết bằng C, nhưng trivially có thể sử dụng từ C++.
  • Việc triển khai C/C++ duy nhất mà tôi đã thấy cung cấp phiên bản không phân biệt chữ hoa chữ thường, điều này có vẻ là ưu tiên cao đối với loại "tự nhiên".
  • Giống như các triển khai khác, nó không thực sự phân tích các dấu thập phân, nhưng trường hợp đặc biệt dẫn đầu số 0 (bất kỳ thứ gì có số 0 đứng đầu được giả định là phân số), hơi lạ nhưng có khả năng hữu ích.
  • PHP sử dụng thuật toán này.

Answer 5

một phần reposting my another answer:

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() chức năng:

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

Cách sử dụng:

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

Answer 6

Để giải quyết những gì về cơ bản là một vấn đề phân tích cú pháp một máy trạng thái (aka finite state automaton) là con đường để đi. Không hài lòng với các giải pháp trên, tôi đã viết một thuật toán bail-out đơn giản vượt qua nhịp mà C/C++ đã đề xuất ở trên về hiệu suất, không bị lỗi tràn số datatype, và dễ sửa đổi để thêm trường hợp vô cảm nếu cần .

nguồn có thể được tìm thấy here