对可能包含数字的字符串进行排序

Question

我需要编写一个比较字符串的 Java Comparator 类，但是有一个转折。如果它比较的两个字符串相同，首尾相同，中间不同的部分是一个整数，则根据这些整数的数值进行比较。例如，我希望以下字符串按显示顺序结束：

• 啊啊
• bbb 3 抄送
• bbb 12 ccc
• CCC 11
• DDD
• eee 3 ddd jpeg2000 eee
• eee 12 ddd jpeg2000 eee

如您所见，字符串中可能还有其他整数，所以我不能只使用正则表达式来分解任何整数。我正在考虑从头开始遍历字符串，直到找到不匹配的位，然后从末尾走直到找到不匹配的位，然后将中间的位与正则表达式“[0-9]+”，如果比较，则进行数值比较，否则进行词法比较。

有没有更好的办法？

更新 我认为我不能保证字符串中的其他数字（可能匹配的数字）周围没有空格，或者不同的数字确实有空格。

原文由 Paul Tomblin 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

字母数字算法

从网站

“人们用数字对字符串进行排序与软件不同。大多数排序算法比较 ASCII 值，这会产生与人类逻辑不一致的排序。下面是解决方法。”

编辑：这是从该站点到 Java Comparator Implementation 的链接。

原文由 ScArcher2 发布，翻译遵循 CC BY-SA 2.5 许可协议

Answer 2

有趣的小挑战，我喜欢解决它。

这是我对这个问题的看法：

 String[] strs =
{
  "eee 5 ddd jpeg2001 eee",
  "eee 123 ddd jpeg2000 eee",
  "ddd",
  "aaa 5 yy 6",
  "ccc 555",
  "bbb 3 ccc",
  "bbb 9 a",
  "",
  "eee 4 ddd jpeg2001 eee",
  "ccc 11",
  "bbb 12 ccc",
  "aaa 5 yy 22",
  "aaa",
  "eee 3 ddd jpeg2000 eee",
  "ccc 5",
};

Pattern splitter = Pattern.compile("(\\d+|\\D+)");

public class InternalNumberComparator implements Comparator
{
  public int compare(Object o1, Object o2)
  {
    // I deliberately use the Java 1.4 syntax,
    // all this can be improved with 1.5's generics
    String s1 = (String)o1, s2 = (String)o2;
    // We split each string as runs of number/non-number strings
    ArrayList sa1 = split(s1);
    ArrayList sa2 = split(s2);
    // Nothing or different structure
    if (sa1.size() == 0 || sa1.size() != sa2.size())
    {
      // Just compare the original strings
      return s1.compareTo(s2);
    }
    int i = 0;
    String si1 = "";
    String si2 = "";
    // Compare beginning of string
    for (; i < sa1.size(); i++)
    {
      si1 = (String)sa1.get(i);
      si2 = (String)sa2.get(i);
      if (!si1.equals(si2))
        break;  // Until we find a difference
    }
    // No difference found?
    if (i == sa1.size())
      return 0; // Same strings!

    // Try to convert the different run of characters to number
    int val1, val2;
    try
    {
      val1 = Integer.parseInt(si1);
      val2 = Integer.parseInt(si2);
    }
    catch (NumberFormatException e)
    {
      return s1.compareTo(s2);  // Strings differ on a non-number
    }

    // Compare remainder of string
    for (i++; i < sa1.size(); i++)
    {
      si1 = (String)sa1.get(i);
      si2 = (String)sa2.get(i);
      if (!si1.equals(si2))
      {
        return s1.compareTo(s2);  // Strings differ
      }
    }

    // Here, the strings differ only on a number
    return val1 < val2 ? -1 : 1;
  }

  ArrayList split(String s)
  {
    ArrayList r = new ArrayList();
    Matcher matcher = splitter.matcher(s);
    while (matcher.find())
    {
      String m = matcher.group(1);
      r.add(m);
    }
    return r;
  }
}

Arrays.sort(strs, new InternalNumberComparator());

这个算法需要更多的测试，但它似乎表现得相当好。

[编辑] 为了更清楚，我添加了更多评论。我发现答案比我开始编写代码时多得多……但我希望我提供了一个良好的起点和/或一些想法。

原文由 PhiLho 发布，翻译遵循 CC BY-SA 2.5 许可协议