如何用C++实现自然排序算法？

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

  •  22-07-2019
  •  | 
  •  

题

我正在对由文本和数字组成的字符串进行排序。我希望排序将数字部分排序为数字，而不是字母数字。

例如我想要：abc1def、...、abc9def、abc10def

代替：abc10def、abc1def、...、abc9def

有谁知道这个的算法（特别是在c++中）

谢谢

有帮助吗？

解决方案

我问就这个问题询问并得到指向 http://www.davekoelle.com/alphanum.html 其在许多语言中的算法和它的实现。

其他提示

此被称为天然的排序。还有一种算法这里那看起来很有希望。

小心有非ASCII字符的问题（见杰夫博客条目上的主题）。

有几种 C++ 自然排序实现可用。简要回顾：

  • natural_sort<> - 基于Boost.Regex。
    • 在我的测试中，它比其他选项慢大约 20 倍。
  • 德克·贾格德曼 alnum.hpp, ，基于戴夫·科勒的 字母数字算法
    • 超过 MAXINT 的值可能会出现整数溢出问题
  • 马丁·普尔的 natsort - 用 C 编写，但可以从 C++ 中轻松使用。
    • 我见过的唯一提供不区分大小写版本的 C/C++ 实现，这对于“自然”排序来说似乎是一个高优先级。
    • 与其他实现一样，它实际上并不解析小数点，但它会处理特殊情况的前导零（任何以 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);

要解决什么实质上是一种分析问题的状态机（又名有限状态自动机 ）是要走的路。不满上述解决方案我写击败C / C ++以上在性能方面变种建议，不从数值数据类型溢出错误挨一个简单的通早救市算法，并且很容易修改，以增加不区分大小写如果需要的话

源可以发现此处 

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

我不是很肯定，如果这是你想要的，无论如何，你可以试试： - ）

不隶属于 StackOverflow
scroll top