Kip*_*Kip 69 java algorithm natural-sort comparator
我想要一些保留自然排序顺序1的字符串比较函数.Java中是否有这样的内容？我在String类中找不到任何内容,而Comparator类只知道两个实现.
我可以自己动手(这不是一个非常难的问题),但如果我不需要,我宁愿不重新发明轮子.
在我的具体情况下,我有我想要排序的软件版本字符串.所以我希望"1.2.10.5"被认为大于"1.2.9.1".
1通过"自然"排序顺序,我的意思是它将字符串与人类比较它们的方式进行比较,而不是"ascii-betical"排序顺序只对程序员有意义.换句话说,"image9.jpg"小于"image10.jpg","album1set2page9photo1.jpg"小于"album1set2page10photo5.jpg","1.2.9.1"小于"1.2.10.5"
Osc*_*Ryz 51
在java中,"自然"顺序含义是"词典"顺序,因此核心中没有像您正在寻找的那样实现.
有开源实现.
这是一个:
请务必阅读:
我希望这有帮助!
我测试了其他人在这里提到的三个Java实现,发现他们的工作略有不同,但没有像我期望的那样.
无论AlphaNumericStringComparator和AlphanumComparator,这样才不会忽略空格pic2之前放置pic 1.
在另一方面NaturalOrderComparator忽略不仅空格也是所有前导零,以便sig[1]先于sig[0].
关于性能AlphaNumericStringComparator比其他两个慢~x10.
String实现了Comparable,这就是Java中的自然顺序(使用类似的接口进行比较).您可以将字符串放在TreeSet中,也可以使用Collections或Arrays类进行排序.
但是,在您的情况下,您不希望"自然排序",您真的需要一个自定义比较器,然后您可以在Collections.sort方法或带有比较器的Arrays.sort方法中使用它.
就你想要在比较器中实现的特定逻辑而言(由点分隔的数字)我不知道任何现有的标准实现,但正如你所说,这不是一个难题.
编辑:在你的评论中,你的链接让你在这里,如果你不介意它是区分大小写的事实,这是一个体面的工作.这是修改后的代码,允许您传入String.CASE_INSENSITIVE_ORDER:
/*
* The Alphanum Algorithm is an improved sorting algorithm for strings
* containing numbers. Instead of sorting numbers in ASCII order like
* a standard sort, this algorithm sorts numbers in numeric order.
*
* The Alphanum Algorithm is discussed at http://www.DaveKoelle.com
*
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*
*/
import java.util.Comparator;
/**
* This is an updated version with enhancements made by Daniel Migowski,
* Andre Bogus, and David Koelle
*
* To convert to use Templates (Java 1.5+):
* - Change "implements Comparator" to "implements Comparator<String>"
* - Change "compare(Object o1, Object o2)" to "compare(String s1, String s2)"
* - Remove the type checking and casting in compare().
*
* To use this class:
* Use the static "sort" method from the java.util.Collections class:
* Collections.sort(your list, new AlphanumComparator());
*/
public class AlphanumComparator implements Comparator<String>
{
private Comparator<String> comparator = new NaturalComparator();
public AlphanumComparator(Comparator<String> comparator) {
this.comparator = comparator;
}
public AlphanumComparator() {
}
private final boolean isDigit(char ch)
{
return ch >= 48 && ch <= 57;
}
/** Length of string is passed in for improved efficiency (only need to calculate it once) **/
private final String getChunk(String s, int slength, int marker)
{
StringBuilder chunk = new StringBuilder();
char c = s.charAt(marker);
chunk.append(c);
marker++;
if (isDigit(c))
{
while (marker < slength)
{
c = s.charAt(marker);
if (!isDigit(c))
break;
chunk.append(c);
marker++;
}
} else
{
while (marker < slength)
{
c = s.charAt(marker);
if (isDigit(c))
break;
chunk.append(c);
marker++;
}
}
return chunk.toString();
}
public int compare(String s1, String s2)
{
int thisMarker = 0;
int thatMarker = 0;
int s1Length = s1.length();
int s2Length = s2.length();
while (thisMarker < s1Length && thatMarker < s2Length)
{
String thisChunk = getChunk(s1, s1Length, thisMarker);
thisMarker += thisChunk.length();
String thatChunk = getChunk(s2, s2Length, thatMarker);
thatMarker += thatChunk.length();
// If both chunks contain numeric characters, sort them numerically
int result = 0;
if (isDigit(thisChunk.charAt(0)) && isDigit(thatChunk.charAt(0)))
{
// Simple chunk comparison by length.
int thisChunkLength = thisChunk.length();
result = thisChunkLength - thatChunk.length();
// If equal, the first different number counts
if (result == 0)
{
for (int i = 0; i < thisChunkLength; i++)
{
result = thisChunk.charAt(i) - thatChunk.charAt(i);
if (result != 0)
{
return result;
}
}
}
} else
{
result = comparator.compare(thisChunk, thatChunk);
}
if (result != 0)
return result;
}
return s1Length - s2Length;
}
private static class NaturalComparator implements Comparator<String> {
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
}
}
看看这个实现.它应该尽可能快,没有任何正则表达式或数组操作或方法调用,只有几个标志和很多情况.
这应该对字符串内的任何数字组合进行排序,并正确支持相等的数字并继续前进.
public static int naturalCompare(String a, String b, boolean ignoreCase) {
if (ignoreCase) {
a = a.toLowerCase();
b = b.toLowerCase();
}
int aLength = a.length();
int bLength = b.length();
int minSize = Math.min(aLength, bLength);
char aChar, bChar;
boolean aNumber, bNumber;
boolean asNumeric = false;
int lastNumericCompare = 0;
for (int i = 0; i < minSize; i++) {
aChar = a.charAt(i);
bChar = b.charAt(i);
aNumber = aChar >= '0' && aChar <= '9';
bNumber = bChar >= '0' && bChar <= '9';
if (asNumeric)
if (aNumber && bNumber) {
if (lastNumericCompare == 0)
lastNumericCompare = aChar - bChar;
} else if (aNumber)
return 1;
else if (bNumber)
return -1;
else if (lastNumericCompare == 0) {
if (aChar != bChar)
return aChar - bChar;
asNumeric = false;
} else
return lastNumericCompare;
else if (aNumber && bNumber) {
asNumeric = true;
if (lastNumericCompare == 0)
lastNumericCompare = aChar - bChar;
} else if (aChar != bChar)
return aChar - bChar;
}
if (asNumeric)
if (aLength > bLength && a.charAt(bLength) >= '0' && a.charAt(bLength) <= '9') // as number
return 1; // a has bigger size, thus b is smaller
else if (bLength > aLength && b.charAt(aLength) >= '0' && b.charAt(aLength) <= '9') // as number
return -1; // b has bigger size, thus a is smaller
else if (lastNumericCompare == 0)
return aLength - bLength;
else
return lastNumericCompare;
else
return aLength - bLength;
}