我需要编写一个Java Comparator类来比较字符串，但有一个要求。如果正在比较的两个字符串在开头和结尾相同，并且不同之处是整数，则基于这些整数的数值进行比较。例如，我希望以下字符串按照它们显示的顺序结束：
您可以看到，字符串中可能有其他整数，因此我不能只使用正则表达式来提取任何整数。我考虑从字符串开头开始遍历字符串，直到找到一个不匹配的位，然后从结尾开始遍历字符串，直到找到一个不匹配的位，然后将中间的位与正则表达式"[0-9]+ "进行比较，如果相似，则进行数字比较，否则进行字典比较。
有更好的方法吗？
更新 我认为我无法保证字符串中的其他数字（可能匹配）周围没有空格，或者不同的数字确实有空格。
来自该网站的介绍：
"人们和软件对字符串中的数字排序方式不同。大多数排序算法比较ASCII值，这导致排序结果与人类逻辑不一致。以下是如何解决这个问题的方法。"
编辑：这里是该网站上的Java Comparator实现链接。
有趣的小挑战，我很喜欢解决它。
这是我的解决方案：
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());
这个算法需要进行更多的测试，但它似乎表现得相当好。
[编辑] 我添加了一些更多的注释以使其更清晰。我看到有比我开始编写代码时更多的答案......但我希望我提供了一个良好的起点和/或一些想法。
public static final int compareNatural (String s1, String s2)
{
// Skip all identical characters
int len1 = s1.length();
int len2 = s2.length();
int i;
char c1, c2;
for (i = 0, c1 = 0, c2 = 0; (i < len1) && (i < len2) && (c1 = s1.charAt(i)) == (c2 = s2.charAt(i)); i++);
// Check end of string
if (c1 == c2)
return(len1 - len2);
// Check digit in first string
if (Character.isDigit(c1))
{
// Check digit only in first string
if (!Character.isDigit(c2))
return(1);
// Scan all integer digits
int x1, x2;
for (x1 = i + 1; (x1 < len1) && Character.isDigit(s1.charAt(x1)); x1++);
for (x2 = i + 1; (x2 < len2) && Character.isDigit(s2.charAt(x2)); x2++);
// Longer integer wins, first digit otherwise
return(x2 == x1 ? c1 - c2 : x1 - x2);
}
// Check digit only in second string
if (Character.isDigit(c2))
return(-1);
// No digits
return(c1 - c2);
}
for循环改为while循环，像这样：while ((x1 < len1) && Character.isDigit(s1.charAt(x1))) { x1++;} - Michael Böckling我使用正则表达式在Java中实现了一种非常简单的方法：
public static Comparator<String> naturalOrdering() {
final Pattern compile = Pattern.compile("(\\d+)|(\\D+)");
return (s1, s2) -> {
final Matcher matcher1 = compile.matcher(s1);
final Matcher matcher2 = compile.matcher(s2);
while (true) {
final boolean found1 = matcher1.find();
final boolean found2 = matcher2.find();
if (!found1 || !found2) {
return Boolean.compare(found1, found2);
} else if (!matcher1.group().equals(matcher2.group())) {
if (matcher1.group(1) == null || matcher2.group(1) == null) {
return matcher1.group().compareTo(matcher2.group());
} else {
return Integer.valueOf(matcher1.group(1)).compareTo(Integer.valueOf(matcher2.group(1)));
}
}
}
};
}
final List<String> strings = Arrays.asList("x15", "xa", "y16", "x2a", "y11", "z", "z5", "x2b", "z");
strings.sort(naturalOrdering());
System.out.println(strings);
将字符串分割成字母和数字的序列，例如 "foo 12 bar" 变成列表 ("foo", 12, "bar")，然后使用该列表作为排序关键字。这样数字将按照数值大小而非字典序排序。
"0001"等于"1"，"01234"小于"4567"）public class NumberAwareComparator implements Comparator<String>
{
@Override
public int compare(String s1, String s2)
{
int len1 = s1.length();
int len2 = s2.length();
int i1 = 0;
int i2 = 0;
while (true)
{
// handle the case when one string is longer than another
if (i1 == len1)
return i2 == len2 ? 0 : -1;
if (i2 == len2)
return 1;
char ch1 = s1.charAt(i1);
char ch2 = s2.charAt(i2);
if (Character.isDigit(ch1) && Character.isDigit(ch2))
{
// skip leading zeros
while (i1 < len1 && s1.charAt(i1) == '0')
i1++;
while (i2 < len2 && s2.charAt(i2) == '0')
i2++;
// find the ends of the numbers
int end1 = i1;
int end2 = i2;
while (end1 < len1 && Character.isDigit(s1.charAt(end1)))
end1++;
while (end2 < len2 && Character.isDigit(s2.charAt(end2)))
end2++;
int diglen1 = end1 - i1;
int diglen2 = end2 - i2;
// if the lengths are different, then the longer number is bigger
if (diglen1 != diglen2)
return diglen1 - diglen2;
// compare numbers digit by digit
while (i1 < end1)
{
if (s1.charAt(i1) != s2.charAt(i2))
return s1.charAt(i1) - s2.charAt(i2);
i1++;
i2++;
}
}
else
{
// plain characters comparison
if (ch1 != ch2)
return ch1 - ch2;
i1++;
i2++;
}
}
}
}
char ch1 = Character.toUpperCase(s1.charAt(i1)); 来进行不区分大小写的比较，这样 1000a 就会小于 1000X。 - Mike建议不要重复造轮子，使用具有内置数字排序功能的区域设置感知、Unicode 兼容的字符串比较器，可使用 ICU4J 库。
import com.ibm.icu.text.Collator;
import com.ibm.icu.text.RuleBasedCollator;
import java.util.Arrays;
import java.util.List;
import java.util.Locale;
public class CollatorExample {
public static void main(String[] args) {
// Make sure to choose correct locale: in Turkish uppercase of "i" is "İ", not "I"
RuleBasedCollator collator = (RuleBasedCollator) Collator.getInstance(Locale.US);
collator.setNumericCollation(true); // Place "10" after "2"
collator.setStrength(Collator.PRIMARY); // Case-insensitive
List<String> strings = Arrays.asList("10", "20", "A20", "2", "t1ab", "01", "T010T01", "t1aB",
"_2", "001", "_200", "1", "A 02", "t1Ab", "a2", "_1", "t1A", "_01",
"100", "02", "T0010T01", "t1AB", "10", "A01", "010", "t1a"
);
strings.sort(collator);
System.out.println(String.join(", ", strings));
// Output: _1, _01, _2, _200, 01, 001, 1,
// 2, 02, 10, 10, 010, 20, 100, A 02, A01,
// a2, A20, t1A, t1a, t1ab, t1aB, t1Ab, t1AB,
// T010T01, T0010T01
}
}
Alphanum算法很好，但它不能满足我正在处理的项目需求。我需要能够正确排序负数和小数。这是我想出的实现方法。非常感谢您提供任何反馈。
public class StringAsNumberComparator implements Comparator<String> {
public static final Pattern NUMBER_PATTERN = Pattern.compile("(\\-?\\d+\\.\\d+)|(\\-?\\.\\d+)|(\\-?\\d+)");
/**
* Splits strings into parts sorting each instance of a number as a number if there is
* a matching number in the other String.
*
* For example A1B, A2B, A11B, A11B1, A11B2, A11B11 will be sorted in that order instead
* of alphabetically which will sort A1B and A11B together.
*/
public int compare(String str1, String str2) {
if(str1 == str2) return 0;
else if(str1 == null) return 1;
else if(str2 == null) return -1;
List<String> split1 = split(str1);
List<String> split2 = split(str2);
int diff = 0;
for(int i = 0; diff == 0 && i < split1.size() && i < split2.size(); i++) {
String token1 = split1.get(i);
String token2 = split2.get(i);
if((NUMBER_PATTERN.matcher(token1).matches() && NUMBER_PATTERN.matcher(token2).matches()) {
diff = (int) Math.signum(Double.parseDouble(token1) - Double.parseDouble(token2));
} else {
diff = token1.compareToIgnoreCase(token2);
}
}
if(diff != 0) {
return diff;
} else {
return split1.size() - split2.size();
}
}
/**
* Splits a string into strings and number tokens.
*/
private List<String> split(String s) {
List<String> list = new ArrayList<String>();
try (Scanner scanner = new Scanner(s)) {
int index = 0;
String num = null;
while ((num = scanner.findInLine(NUMBER_PATTERN)) != null) {
int indexOfNumber = s.indexOf(num, index);
if (indexOfNumber > index) {
list.add(s.substring(index, indexOfNumber));
}
list.add(num);
index = indexOfNumber + num.length();
}
if (index < s.length()) {
list.add(s.substring(index));
}
}
return list;
}
}
PS. 我想使用java.lang.String.split()方法并使用“lookahead/lookbehind”保留标记，但我无法通过我正在使用的正则表达式使其工作。
Pattern.compile() 的时间复杂度为 O(N log N)，您可能希望对其进行缓存！ - Lukas EderScanner，你可以直接调用NUMBER_PATTERN.matcher(s)，然后在返回的Matcher上重复调用find。最好的事情是，匹配器将为每个匹配告诉您开始和结束位置，使整个拆分操作变得微不足道。而且它不需要一个资源密集型的try(…) {…}块。 - Holgerif(str1 == null || str2 == null) { return 0; } 是错误的，因为它意味着如果任一参数为 null，它将被报告为等于另一个参数。但是当 null 等于任何其他输入时，所有输入必须相等（传递性规则）。最简单的解决方案是根本不支持 null。否则，您将不得不使用类似 if(str1 == str2) return 0; if(str1 == null) return 1; if(str2 == null) return -1; 的东西。 - Holger