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

我的看法是：对我来说很好用。我主要用它来处理文件名。

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

修改 this 的答案。

---

• 不区分大小写的顺序（1000a小于1000X）
• null值处理

实现：

;

import static java.lang.Math.pow;

import java.util.Comparator;

public class AlphanumComparator implements Comparator<String> {
    
    public static final AlphanumComparator ALPHANUM_COMPARATOR = new AlphanumComparator();
    private static char[] upperCaseCache = new char[(int) pow(2, 16)];
    private boolean nullIsLess;
    
    public AlphanumComparator() {
    }
    
    public AlphanumComparator(boolean nullIsLess) {
        this.nullIsLess = nullIsLess;
    }
    
    @Override
    public int compare(String s1, String s2) {
        if (s1 == s2)
            return 0;
        if (s1 == null)
            return nullIsLess ? -1 : 1;
        if (s2 == null)
            return nullIsLess ? 1 : -1;
        
        int i1 = 0;
        int i2 = 0;
        int len1 = s1.length();
        int len2 = s2.length();
        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 (isDigit(ch1) && 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 && isDigit(s1.charAt(end1)))
                    end1++;
                while (end2 != len2 && isDigit(s2.charAt(end2)))
                    end2++;
                
                // if the lengths are different, then the longer number is bigger
                int diglen1 = end1 - i1;
                int diglen2 = end2 - i2;
                if (diglen1 != diglen2)
                    return diglen1 - diglen2;
                
                // compare numbers digit by digit
                while (i1 < end1) {
                    ch1 = s1.charAt(i1);
                    ch2 = s2.charAt(i2);
                    if (ch1 != ch2)
                        return ch1 - ch2;
                    i1++;
                    i2++;
                }
            } else {
                ch1 = toUpperCase(ch1);
                ch2 = toUpperCase(ch2);
                if (ch1 != ch2)
                    return ch1 - ch2;
                i1++;
                i2++;
            }
        }
    }
    
    private boolean isDigit(char ch) {
        return ch >= 48 && ch <= 57;
    }
    
    private char toUpperCase(char ch) {
        char cached = upperCaseCache[ch];
        if (cached == 0) {
            cached = Character.toUpperCase(ch);
            upperCaseCache[ch] = cached;
        }
        return cached;
    }
}

在@stanislav提供的答案上补充一点。 使用提供的答案时，我遇到了几个问题：

1. 大写字母和小写字母之间的字符会分开它们的ASCII码。当被排序的字符串中有_或其他位于小写字母和大写字母之间的字符时，这会破坏流程。
2. 如果两个字符串除了前导零计数不同外相同，则函数返回0，这将使排序依赖于字符串在列表中的原始位置。

这些问题已经在新代码中得到解决。我编写了几个函数而不是几个重复的代码集。differentCaseCompared变量跟踪两个字符串是否相同，除了大小写不同。如果是这样，就返回第一个不同大小写字符的差值。这样做是为了避免返回两个仅由大小写区别的字符串为0的问题。

public class NaturalSortingComparator implements Comparator<String> {

    @Override
    public int compare(String string1, String string2) {
        int lengthOfString1 = string1.length();
        int lengthOfString2 = string2.length();
        int iteratorOfString1 = 0;
        int iteratorOfString2 = 0;
        int differentCaseCompared = 0;
        while (true) {
            if (iteratorOfString1 == lengthOfString1) {
                if (iteratorOfString2 == lengthOfString2) {
                    if (lengthOfString1 == lengthOfString2) {
                        // If both strings are the same except for the different cases, the differentCaseCompared will be returned
                        return differentCaseCompared;
                    }
                    //If the characters are the same at the point, returns the difference between length of the strings
                    else {
                        return lengthOfString1 - lengthOfString2;
                    }
                }
                //If String2 is bigger than String1
                else
                    return -1;
            }
            //Check if String1 is bigger than string2
            if (iteratorOfString2 == lengthOfString2) {
                return 1;
            }

            char ch1 = string1.charAt(iteratorOfString1);
            char ch2 = string2.charAt(iteratorOfString2);

            if (Character.isDigit(ch1) && Character.isDigit(ch2)) {
                // skip leading zeros
                iteratorOfString1 = skipLeadingZeroes(string1, lengthOfString1, iteratorOfString1);
                iteratorOfString2 = skipLeadingZeroes(string2, lengthOfString2, iteratorOfString2);

                // find the ends of the numbers
                int endPositionOfNumbersInString1 = findEndPositionOfNumber(string1, lengthOfString1, iteratorOfString1);
                int endPositionOfNumbersInString2 = findEndPositionOfNumber(string2, lengthOfString2, iteratorOfString2);

                int lengthOfDigitsInString1 = endPositionOfNumbersInString1 - iteratorOfString1;
                int lengthOfDigitsInString2 = endPositionOfNumbersInString2 - iteratorOfString2;

                // if the lengths are different, then the longer number is bigger
                if (lengthOfDigitsInString1 != lengthOfDigitsInString2)
                    return lengthOfDigitsInString1 - lengthOfDigitsInString2;

                // compare numbers digit by digit
                while (iteratorOfString1 < endPositionOfNumbersInString1) {

                    if (string1.charAt(iteratorOfString1) != string2.charAt(iteratorOfString2))
                        return string1.charAt(iteratorOfString1) - string2.charAt(iteratorOfString2);

                    iteratorOfString1++;
                    iteratorOfString2++;
                }
            } else {
                // plain characters comparison
                if (ch1 != ch2) {
                    if (!ignoreCharacterCaseEquals(ch1, ch2))
                        return Character.toLowerCase(ch1) - Character.toLowerCase(ch2);

                    // Set a differentCaseCompared if the characters being compared are different case.
                    // Should be done only once, hence the check with 0
                    if (differentCaseCompared == 0) {
                        differentCaseCompared = ch1 - ch2;
                    }
                }

                iteratorOfString1++;
                iteratorOfString2++;
            }
        }
    }

    private boolean ignoreCharacterCaseEquals(char character1, char character2) {

        return Character.toLowerCase(character1) == Character.toLowerCase(character2);
    }

    private int findEndPositionOfNumber(String string, int lengthOfString, int end) {

        while (end < lengthOfString && Character.isDigit(string.charAt(end)))
            end++;

        return end;
    }

    private int skipLeadingZeroes(String string, int lengthOfString, int iteratorOfString) {

        while (iteratorOfString < lengthOfString && string.charAt(iteratorOfString) == '0')
            iteratorOfString++;

        return iteratorOfString;
    }
}

以下是我使用的单元测试。

public class NaturalSortingComparatorTest {

    private int NUMBER_OF_TEST_CASES = 100000;

    @Test
    public void compare() {

        NaturalSortingComparator naturalSortingComparator = new NaturalSortingComparator();

        List<String> expectedStringList = getCorrectStringList();
        List<String> testListOfStrings = createTestListOfStrings();
        runTestCases(expectedStringList, testListOfStrings, NUMBER_OF_TEST_CASES, naturalSortingComparator);

    }

    private void runTestCases(List<String> expectedStringList, List<String> testListOfStrings,
                              int numberOfTestCases, Comparator<String> comparator) {

        for (int testCase = 0; testCase < numberOfTestCases; testCase++) {
            Collections.shuffle(testListOfStrings);
            testListOfStrings.sort(comparator);
            Assert.assertEquals(expectedStringList, testListOfStrings);
        }
    }

    private List<String> getCorrectStringList() {
        return Arrays.asList(
                "1", "01", "001", "2", "02", "10", "10", "010",
                "20", "100", "_1", "_01", "_2", "_200", "A 02",
                "A01", "a2", "A20", "t1A", "t1a", "t1AB", "t1Ab",
                "t1aB", "t1ab", "T010T01", "T0010T01");
    }

    private List<String> createTestListOfStrings() {
        return 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");
    }

}

欢迎提出建议！我不确定添加这些功能是否会改变除可读性之外的任何内容。
附言：很抱歉又回答了这个问题。但是我没有足够的声望来评论我修改后的答案。

我创建了一个项目来比较不同的实现。虽然它还远未完成，但它是一个起点。

有趣的问题，这里是我的解决方案：

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

}

在发现这个线程之前，我用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/ 请注意，我目前只支持整数类型，但处理小数值不会太难进行修改。

虽然问题要求使用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
   })

}

虽然有点晚，但这是一种简洁而优美的解决方案：

Collections.sort(b, new Comparator<String>(){
        @Override
        public int compare(String a, String b){
            if(a.equals(b)) return 0;
            for(int i = 0; i < Math.min(a.length(), b.length()); i++){
                char aChar = a.charAt(i), bChar = b.charAt(i);
                int comp = Character.compare(aChar, bChar);
                if(comp == 0) continue;
                return comp;
            }
            return a.length() < b.length() ? -1 : 1;
        }
    });

我遇到了一个类似的问题，我的字符串内部有由空格分隔的段落。我是这样解决它的：

public class StringWithNumberComparator implements Comparator<MyClass> {

@Override
public int compare(MyClass o1, MyClass o2) {
    if (o1.getStringToCompare().equals(o2.getStringToCompare())) {
        return 0;
    }
    String[] first = o1.getStringToCompare().split(" ");
    String[] second = o2.getStringToCompare().split(" ");
    if (first.length == second.length) {
        for (int i = 0; i < first.length; i++) {

            int segmentCompare = StringUtils.compare(first[i], second[i]);
            if (StringUtils.isNumeric(first[i]) && StringUtils.isNumeric(second[i])) {

                segmentCompare = NumberUtils.compare(Integer.valueOf(first[i]), Integer.valueOf(second[i]));
                if (0 != segmentCompare) {
                    // return only if uneven numbers in case there are more segments to be checked
                    return segmentCompare;
                }
            }
            if (0 != segmentCompare) {
                return segmentCompare;
            }
        }
    } else {
        return StringUtils.compare(o1.getDenominazione(), o2.getDenominazione());
    }

    return 0;
}

正如您所看到的，我使用了Apache的StringUtils.compare()和NumberUtils.compare()作为标准帮助。

我认为你需要逐个字符进行比较。获取一个字符，如果它是数字字符，则继续获取，然后重新组合成单个数字字符串并将其转换为int。在另一个字符串上重复此操作，然后再进行比较。