排序可能包含数字的字符串

我需要编写一个比较字符串的Java比较器类，然而只有一个转折点。 如果它比较的两个字符串在字符串的开头和末尾是相同的，并且不同的中间部分是一个整数，则根据这些整数的数字值进行比较。 例如，我需要下列字符串才能显示出来：

• AAA
• bbb 3 ccc
• bbb 12 ccc
• ccc 11
• DDD
• eee 3 ddd jpeg2000 eee
• eee 12 ddd jpeg2000 eee

正如你所看到的，字符串中可能还有其他整数，所以我不能只用正则表达式来分解任何整数。 我想从一开始就走字符串，直到找到一个不匹配的位，然后从最后走到最后找到一个不匹配的位，然后比较中间位和正则表达式“[0-9] +”，如果比较，则进行数字比较，否则进行词法比较。

有没有更好的办法？

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

Answer 1

阿尔法算法

来自网站

“人们用不同于软件的字符串排序，大多数排序算法比较ASCII值，这会产生一个与人类逻辑不一致的排序，下面介绍如何解决这个问题。

编辑：这是从该网站的Java比较器实施的链接。

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()); 

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

[编辑]我增加了一些意见要更清楚。 当我开始编写代码时，我发现有更多的答案…但我希望我提供了一个很好的开始基础和/或一些想法。

Answer 3

微软的伊恩·格里菲斯（Ian Griffiths）有一个他称之为自然排序的C＃实现。 移植到Java应该相当容易，比从C更容易！

更新：在eekboom上似乎有一个Java示例，请参阅“compareNatural”，并将其用作比较器进行排序。

Answer 4

我意识到你在java中，但是你可以看看StrCmpLogicalW是如何工作的。 这是Explorer在Windows中使用排序文件名。 你可以在这里看看WINE的实现。

Answer 5

我在这里提出的实现简单而高效。 它不会使用正则表达式或方法（如substring（），split（），toCharArray（）等）直接或间接地分配任何额外的内存。

这个实现首先遍历两个字符串，以最快的速度搜索不同的第一个字符，而在此期间不做任何特殊的处理。 只有当这些字符都是数字时才会触发特定的数字比较。 这种实现的副作用是数字被认为比其他字母更大，与默认字典顺序相反。

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

Answer 6

将字符串拆分为字母和数字，“foo 12 bar”变成列表（“foo”，12，“bar”），然后使用列表作为排序键。 这样数字将按数字顺序排列，而不是按字母排序。

Answer 7

我使用正则表达式在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); 

[x2a，x2b，x15，xa，y11，y16，z，z，z5]

Answer 8

Alphanum algrothim很好，但它不符合我正在进行的一个项目的要求。 我需要能够正确排序负数和小数。 这是我提出的实现。 任何反馈将不胜感激。

 public class StringAsNumberComparator implements Comparator<String> { public static final String NUMBER_PATTERN = "(\\-?\\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 == null || str2 == null) { return 0; } 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(token1.matches(NUMBER_PATTERN) && token2.matches(NUMBER_PATTERN)) { 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>(); 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”来保留标记，但是我无法使用正则表达式来使用它。

Answer 9

有趣的问题，在这里我提出的解决方案：

 import java.util.Collections; import java.util.Vector; public class CompareToken implements Comparable<CompareToken> { int valN; String valS; String repr; public String toString() { return repr; } public CompareToken(String s) { int l = 0; char data[] = new char[s.length()]; repr = s; valN = 0; for (char c : s.toCharArray()) { if(Character.isDigit(c)) valN = valN * 10 + (c - '0'); else data[l++] = c; } valS = new String(data, 0, l); } public int compareTo(CompareToken b) { int r = valS.compareTo(b.valS); if (r != 0) return r; return valN - b.valN; } public static void main(String [] args) { String [] strings = { "aaa", "bbb3ccc", "bbb12ccc", "ccc 11", "ddd", "eee3dddjpeg2000eee", "eee12dddjpeg2000eee" }; Vector<CompareToken> data = new Vector<CompareToken>(); for(String s : strings) data.add(new CompareToken(s)); Collections.shuffle(data); Collections.sort(data); for (CompareToken c : data) System.out.println ("" + c); } } 

Answer 10

在发现这个线程之前，我在JavaScript中实现了一个类似的解决方案。 尽管语法不同，也许我的策略会很好地找到你。 与上面类似，我解析了两个正在比较的字符串，并将它们分成数组，将字符串连续分割。

 ... var regex = /(\d+)/g, str1Components = str1.split(regex), str2Components = str2.split(regex), ... 

也就是说，'hello22goodbye 33'=> ['hello'，22，'goodbye'，33]; 因此，你可以在string1和string2之间对数组元素进行遍历，做一些类型的强制（比如，这个元素是一个数字吗？），并且在你走路时进行比较。

工作示例： http : //jsfiddle.net/F46s6/3/

请注意，我目前只支持整数类型，虽然处理十进制值不会太难修改。

Answer 11

我的2分钱，对我来说工作很好。 我主要使用它的文件名。

  private final boolean isDigit(char ch) { return ch >= 48 && ch <= 57; } private int compareNumericalString(String s1,String s2){ int s1Counter=0; int s2Counter=0; while(true){ if(s1Counter>=s1.length()){ break; } if(s2Counter>=s2.length()){ break; } char currentChar1=s1.charAt(s1Counter++); char currentChar2=s2.charAt(s2Counter++); if(isDigit(currentChar1) &&isDigit(currentChar2)){ String digitString1=""+currentChar1; String digitString2=""+currentChar2; while(true){ if(s1Counter>=s1.length()){ break; } if(s2Counter>=s2.length()){ break; } if(isDigit(s1.charAt(s1Counter))){ digitString1+=s1.charAt(s1Counter); s1Counter++; } if(isDigit(s2.charAt(s2Counter))){ digitString2+=s2.charAt(s2Counter); s2Counter++; } if((!isDigit(s1.charAt(s1Counter))) && (!isDigit(s2.charAt(s2Counter)))){ currentChar1=s1.charAt(s1Counter); currentChar2=s2.charAt(s2Counter); break; } } if(!digitString1.equals(digitString2)){ return Integer.parseInt(digitString1)-Integer.parseInt(digitString2); } } if(currentChar1!=currentChar2){ return currentChar1-currentChar2; } } return s1.compareTo(s2); } 

Answer 12

我认为你必须做一个逐字符的比较。 抓住一个字符，如果它是一个数字字符，继续抓取，然后重新组合成一个数字字符串的字符，并将其转换为一个int 。 重复另一个字符串，然后才进行比较。

Answer 13

简短的回答：根据上下文，我不能说这是否只是一些个人使用的快速和肮脏的代码，或高盛最新的内部会计软件的关键部分，所以我打开说：eww 。 这是一个相当时髦的排序算法; 如果可以的话，尽量少用一些“曲折”的东西。

很长的回答：

立即想到的两个问题就是性能和正确性。 非正式的，确保它是快速的，并确保你的算法是一个完整的排序 。

（当然，如果你没有排序超过100个项目，你可能会忽略这个段落）。性能很重要，因为比较的速度将是排序速度的最大因素（假设排序算法是“理想”的典型名单）。 在你的情况下，比较器的速度将主要取决于字符串的大小。 字符串似乎很短，所以它们可能不会像列表的大小一样占优势。

将每个字符串转换为一个字符串 – 数字字符串元组，然后按照另一个答案中的建议对这个元组列表进行排序，在某些情况下会失败，因为显然会出现多个字符串。

另一个问题是正确的。 具体来说，如果你描述的算法将允许A> B> …> A，那么你的排序将是非确定性的。 在你的情况下，我担心它可能，虽然我不能证明这一点。 考虑一些解析案例，如：

  aa 0 aa aa 23aa aa 2a3aa aa 113aa aa 113 aa a 1-2 a a 13 a a 12 a a 2-3 a a 21 a a 2.3 a 

Answer 14

虽然这个问题提出了一个java解决方案，对于任何想要scala解决方案的人来说：

 object Alphanum { private[this] val regex = "((?<=[0-9])(?=[^0-9]))|((?<=[^0-9])(?=[0-9]))" private[this] val alphaNum: Ordering[String] = Ordering.fromLessThan((ss1: String, ss2: String) => (ss1, ss2) match { case (sss1, sss2) if sss1.matches("[0-9]+") && sss2.matches("[0-9]+") => sss1.toLong < sss2.toLong case (sss1, sss2) => sss1 < sss2 }) def ordering: Ordering[String] = Ordering.fromLessThan((s1: String, s2: String) => { import Ordering.Implicits.infixOrderingOps implicit val ord: Ordering[List[String]] = Ordering.Implicits.seqDerivedOrdering(alphaNum) s1.split(regex).toList < s2.split(regex).toList }) } 

Answer 15

在你给定的例子中，你想要比较的数字在它们周围有空格，而其他数字没有，所以为什么正则表达式不起作用？

bbb 12 ccc

与

eee 12 ddd jpeg2000 eee

Answer 16

如果你正在编写一个比较器类，你应该实现你自己的比较方法，它将逐个字符地比较两个字符串。 这个比较方法应该检查你是否处理字母字符，数字字符或混合类型（包括空格）。 你必须定义你想要一个混合类型的行为，数字是否在字母字符之前或之后，以及空间适合等等。

Answer 17

在Linux上，glibc提供了strverscmp（），它也可以从gnulib获得可移植性。 然而，真正的“人”排序有许多其他的怪癖，如“甲壳虫”排序为“披头士”。 这个一般问题没有简单的解决方案。