Sortieren Sie nach einer Zeichenfolge, die eine Zahl enthalten kann

Ich muss eine Java Comparator-Klasse schreiben, die Strings vergleicht, jedoch mit einer Wendung. Wenn die beiden zu vergleichenden Zeichenfolgen am Anfang und am Ende der Zeichenfolge identisch sind und der mittlere Teil, der sich unterscheidet, eine Ganzzahl ist, vergleichen Sie anhand der numerischen Werte dieser Ganzzahlen. Ich möchte zum Beispiel, dass die folgenden Zeichenfolgen in der Reihenfolge angezeigt werden, in der sie angezeigt werden:

• aaa
• bbb 3 ccc
• bbb 12 ccc
• ccc 11
• ddd
• eee 3 ddd jpeg2000 eee
• eee 12 ddd jpeg2000 eee

Wie Sie sehen können, enthält die Zeichenfolge möglicherweise andere Ganzzahlen, sodass ich nicht einfach reguläre Ausdrücke verwenden kann, um eine Ganzzahl auszubrechen. Ich denke daran, die Saiten von Anfang an zu durchlaufen, bis ich ein Stück finde, das nicht passt, dann vom Ende hinein zu gehen, bis ich ein Stück finde, das nicht passt, und dann das Stück in der Mitte mit dem zu vergleichen regulärer Ausdruck "[0-9] +", und wenn er vergleicht, dann einen numerischen Vergleich durchführen, andernfalls einen lexikalischen Vergleich.

Gibt es einen besseren Weg?

Update Ich glaube nicht, dass ich garantieren kann, dass die anderen Zahlen in der Zeichenfolge, die möglicherweise übereinstimmen, keine Leerzeichen um sie herum haben oder dass diejenigen, die sich unterscheiden, Leerzeichen haben.

Der Alphanum-Algorithmus

Von der Website

"Menschen sortieren Zeichenfolgen mit Zahlen anders als Software. Die meisten Sortieralgorithmen vergleichen ASCII-Werte, wodurch eine Reihenfolge erzeugt wird, die nicht mit der menschlichen Logik übereinstimmt. Hier erfahren Sie, wie Sie dies beheben können."

Bearbeiten: Hier ist ein Link zur Java Comparator-Implementierung von dieser Site.

Interessante kleine Herausforderung, ich habe es genossen, sie zu lösen.

Hier ist meine Einstellung zum Problem:

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

Dieser Algorithmus muss viel mehr getestet werden, scheint sich aber recht gut zu verhalten.

[BEARBEITEN] Ich habe einige weitere Kommentare hinzugefügt, um die Übersichtlichkeit zu verbessern. Ich sehe, dass es viel mehr Antworten gibt als zu Beginn des Codierens ... Aber ich hoffe, ich habe eine gute Ausgangsbasis und / oder einige Ideen geliefert.

Ian Griffiths von Microsoft hat eine C # -Implementierung, die er Natural Sorting nennt . Das Portieren nach Java sollte ziemlich einfach sein, sowieso einfacher als von C!

UPDATE: Es scheint ein Java-Beispiel auf eekboom zu geben , das dies tut. Sehen Sie sich das "compareNatural" an und verwenden Sie es als Vergleicher für Sortierungen.

Die hier vorgeschlagene Implementierung ist einfach und effizient. Es wird weder direkt noch indirekt zusätzlicher Speicher zugewiesen, indem reguläre Ausdrücke oder Methoden wie substring (), split (), toCharArray () usw. verwendet werden.

Diese Implementierung durchläuft zunächst beide Zeichenfolgen, um mit maximaler Geschwindigkeit nach den ersten Zeichen zu suchen, die sich unterscheiden, ohne dabei eine spezielle Verarbeitung durchzuführen. Ein spezifischer Nummernvergleich wird nur ausgelöst, wenn diese Zeichen beide Ziffern sind. Ein Nebeneffekt dieser Implementierung besteht darin, dass eine Ziffer im Gegensatz zur lexikografischen Standardreihenfolge als größer als andere Buchstaben betrachtet wird.

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

Mir ist klar, dass Sie in Java sind, aber Sie können einen Blick darauf werfen, wie StrCmpLogicalW funktioniert. Mit diesem Explorer werden Dateinamen in Windows sortiert. Sie können an der Wein Umsetzung aussehen hier .

Teilen Sie die Zeichenfolge in Buchstaben- und Zahlenreihen auf, sodass "foo 12 bar" zur Liste wird ("foo", 12, "bar"), und verwenden Sie dann die Liste als Sortierschlüssel. Auf diese Weise werden die Zahlen in numerischer Reihenfolge und nicht in alphabetischer Reihenfolge sortiert.

Ich habe mir eine recht einfache Implementierung in Java mit regulären Ausdrücken ausgedacht:

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

So funktioniert es:

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]

Hier ist die Lösung mit den folgenden Vorteilen gegenüber dem Alphanum-Algorithmus:

1. 3,25x schneller (getestet anhand der Daten aus dem Kapitel 'Epilog' der Alphanum-Beschreibung )
2. Verbraucht keinen zusätzlichen Speicher (kein Aufteilen von Zeichenfolgen, kein Parsen von Zahlen)
3. Verarbeitet führende Nullen korrekt (z. B. "0001"gleich "1", "01234"ist kleiner als "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++;
            }
        }
    }
}

Das Alphanum Algrothim ist nett, aber es entsprach nicht den Anforderungen für ein Projekt, an dem ich arbeite. Ich muss in der Lage sein, negative Zahlen und Dezimalstellen richtig zu sortieren. Hier ist die Implementierung, die ich mir ausgedacht habe. Jedes Feedback wäre sehr dankbar.

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. Ich wollte die Methode java.lang.String.split () verwenden und "lookahead / lookbehind" verwenden, um die Token zu behalten, konnte sie jedoch nicht mit dem von mir verwendeten regulären Ausdruck zum Laufen bringen.

interessantes Problem, und hier meine vorgeschlagene Lösung:

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

}

Bevor ich diesen Thread entdeckte, implementierte ich eine ähnliche Lösung in Javascript. Vielleicht findet Sie meine Strategie trotz unterschiedlicher Syntax gut. Ähnlich wie oben analysiere ich die beiden verglichenen Zeichenfolgen und teile sie in Arrays auf, wobei ich die Zeichenfolgen in fortlaufende Zahlen teile.

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

Dh 'hallo22goodbye 33' => ['hallo', 22, 'goodbye', 33]; Auf diese Weise können Sie die Elemente der Arrays paarweise zwischen Zeichenfolge1 und Zeichenfolge2 durchlaufen, einen Typ-Zwang ausführen (z. B. ist dieses Element wirklich eine Zahl?) Und beim Gehen vergleichen.

Arbeitsbeispiel hier: http://jsfiddle.net/F46s6/3/

Beachten Sie, dass ich derzeit nur Ganzzahltypen unterstütze, obwohl die Behandlung von Dezimalwerten keine allzu schwierige Änderung wäre.

Meine 2 Cent. Funktioniert gut für mich. Ich benutze es hauptsächlich für Dateinamen.

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

Ich habe ein Projekt erstellt , um die verschiedenen Implementierungen zu vergleichen. Es ist alles andere als vollständig, aber es ist ein Ausgangspunkt.

Ergänzung zu der Antwort von @stanislav . Einige Probleme, mit denen ich bei der Verwendung der Antwort konfrontiert war, waren:

1. Groß- und Kleinbuchstaben werden durch die Zeichen zwischen ihren ASCII-Codes getrennt. Dies unterbricht den Fluss, wenn die zu sortierenden Zeichenfolgen _ oder andere Zeichen enthalten, die in ASCII zwischen Kleinbuchstaben und Großbuchstaben liegen.
2. Wenn zwei Zeichenfolgen gleich sind, außer dass die Anzahl der führenden Nullen unterschiedlich ist, gibt die Funktion 0 zurück, wodurch die Sortierung von den ursprünglichen Positionen der Zeichenfolge in der Liste abhängt.

Diese beiden Probleme wurden im neuen Code behoben. Und ich habe ein paar Funktionen anstelle einiger sich wiederholender Codes gemacht. Die Variable differentCaseCompared verfolgt, ob zwei Zeichenfolgen identisch sind, mit Ausnahme der unterschiedlichen Fälle. In diesem Fall wird der Wert der ersten subtrahierten Groß- und Kleinschreibung zurückgegeben. Dies geschieht, um das Problem zu vermeiden, dass zwei Zeichenfolgen, die sich je nach Groß- und Kleinschreibung unterscheiden, als 0 zurückgegeben werden.

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

Das Folgende ist ein Unit-Test, den ich verwendet habe.

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

}

Vorschläge willkommen! Ich bin nicht sicher, ob das Hinzufügen der Funktionen etwas anderes als den Lesbarkeitsteil der Dinge ändert.

PS: Es tut uns leid, eine weitere Antwort auf diese Frage hinzuzufügen. Aber ich habe nicht genug Wiederholungen, um die Antwort zu kommentieren, die ich für meine Verwendung geändert habe.

Ich denke, Sie müssen den Vergleich von Charakter zu Charakter durchführen. Schnappen Sie sich ein Zeichen, wenn es sich um ein Zahlenzeichen handelt, greifen Sie weiter, setzen Sie es dann wieder zu Zeichen zu einer einzelnen Zahlenfolge zusammen und konvertieren Sie es in eine int. Wiederholen Sie dies für die andere Zeichenfolge und führen Sie erst dann den Vergleich durch.

Kurze Antwort: Aufgrund des Kontexts kann ich nicht sagen, ob dies nur ein schneller und schmutziger Code für den persönlichen Gebrauch oder ein wichtiger Bestandteil der neuesten internen Buchhaltungssoftware von Goldman Sachs ist. Ich werde also mit den Worten: eww . Das ist ein ziemlich funky Sortieralgorithmus; Versuchen Sie, etwas weniger "kurviges" zu verwenden, wenn Sie können.

Lange Antwort:

Die beiden Probleme, die in Ihrem Fall sofort in den Sinn kommen, sind Leistung und Korrektheit. Stellen Sie informell sicher, dass es schnell ist, und stellen Sie sicher, dass Ihr Algorithmus eine Gesamtbestellung ist .

(Wenn Sie nicht mehr als 100 Elemente sortieren, können Sie diesen Absatz wahrscheinlich ignorieren.) Die Leistung ist wichtig, da die Geschwindigkeit des Komparators der größte Faktor für die Geschwindigkeit Ihrer Sortierung ist (vorausgesetzt, der Sortieralgorithmus ist "ideal" zur typischen Liste). In Ihrem Fall hängt die Geschwindigkeit des Komparators hauptsächlich von der Größe der Zeichenfolge ab. Die Zeichenfolgen scheinen ziemlich kurz zu sein, sodass sie wahrscheinlich nicht so stark dominieren wie die Größe Ihrer Liste.

Das Umwandeln jeder Zeichenfolge in ein Zeichenfolge-Nummer-Zeichenfolge-Tupel und das anschließende Sortieren dieser Liste von Tupeln, wie in einer anderen Antwort vorgeschlagen, schlägt in einigen Fällen fehl, da anscheinend Zeichenfolgen mit mehreren Zahlen angezeigt werden.

Das andere Problem ist die Richtigkeit. Insbesondere wenn der von Ihnen beschriebene Algorithmus jemals A> B> ...> A zulässt, ist Ihre Sortierung nicht deterministisch. In Ihrem Fall befürchte ich, dass es könnte, obwohl ich es nicht beweisen kann. Betrachten Sie einige Analysefälle wie:

  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

Obwohl die Frage eine Java-Lösung stellte, für alle, die eine Scala-Lösung wollen:

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

}

Mein Problem war, dass ich Listen habe, die aus einer Kombination von alphanumerischen Zeichenfolgen (z. B. C22, C3, C5 usw.), alphanumerischen Zeichenfolgen (z. B. A, H, R usw.) und nur Ziffern (z. B. 99, 45 usw.) bestehen, die sortiert werden müssen Die Reihenfolge A, C3, C5, C22, H, R, 45, 99. Ich habe auch Duplikate, die entfernt werden müssen, sodass ich nur einen einzigen Eintrag erhalte.

Ich arbeite auch nicht nur mit Strings, sondern bestelle ein Objekt und verwende ein bestimmtes Feld innerhalb des Objekts, um die richtige Reihenfolge zu erhalten.

Eine Lösung, die für mich zu funktionieren scheint, ist:

SortedSet<Code> codeSet;
codeSet = new TreeSet<Code>(new Comparator<Code>() {

private boolean isThereAnyNumber(String a, String b) {
    return isNumber(a) || isNumber(b);
}

private boolean isNumber(String s) {
    return s.matches("[-+]?\\d*\\.?\\d+");
}

private String extractChars(String s) {
    String chars = s.replaceAll("\\d", "");
    return chars;
}

private int extractInt(String s) {
    String num = s.replaceAll("\\D", "");
    return num.isEmpty() ? 0 : Integer.parseInt(num);
}

private int compareStrings(String o1, String o2) {

    if (!extractChars(o1).equals(extractChars(o2))) {
        return o1.compareTo(o2);
    } else
        return extractInt(o1) - extractInt(o2);
}

@Override
public int compare(Code a, Code b) {

    return isThereAnyNumber(a.getPrimaryCode(), b.getPrimaryCode()) 
            ? isNumber(a.getPrimaryCode()) ? 1 : -1 
                : compareStrings(a.getPrimaryCode(), b.getPrimaryCode());
                }
            });

Es leiht sich einen Code aus, den ich hier auf Stackoverflow gefunden habe, sowie einige eigene Verbesserungen, damit es genau so funktioniert, wie ich es auch brauchte.

Da ich versuchte, Objekte zu bestellen, einen Komparator sowie das Entfernen von Duplikaten benötigte, musste ich einen negativen Fehler machen, indem ich meine Objekte zuerst in eine TreeMap schreiben musste, bevor ich sie in ein Treeset schrieb. Dies kann die Leistung ein wenig beeinträchtigen, aber da die Listen maximal etwa 80 Codes enthalten, sollte dies kein Problem sein.

Ich hatte ein ähnliches Problem, bei dem meine Zeichenfolgen durch Leerzeichen getrennte Segmente enthielten. Ich habe es so gelöst:

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

Wie Sie sehen können, habe ich Apaches StringUtils.compare () und NumberUtils.compere () als Standardhilfe verwendet.

Anstatt das Rad neu zu erfinden, würde ich vorschlagen, einen Gebietsschema-fähigen Unicode-kompatiblen Zeichenfolgenkomparator zu verwenden, der über eine integrierte Nummernsortierung aus der ICU4J-Bibliothek verfügt .

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

In Ihrem Beispiel sind die Zahlen, die Sie vergleichen möchten, mit Leerzeichen umgeben, während die anderen Zahlen dies nicht tun. Warum sollte ein regulärer Ausdruck also nicht funktionieren?

bbb 12 ccc

vs.

eee 12 ddd jpeg2000 eee

Wenn Sie eine Vergleichsklasse schreiben, sollten Sie eine eigene Vergleichsmethode implementieren, mit der zwei Zeichenfolgen Zeichen für Zeichen verglichen werden. Diese Vergleichsmethode sollte prüfen, ob es sich um alphabetische Zeichen, numerische Zeichen oder gemischte Typen (einschließlich Leerzeichen) handelt. Sie müssen definieren, wie ein gemischter Typ funktionieren soll, ob Zahlen vor oder nach alphabetischen Zeichen stehen und wo Leerzeichen hineinpassen usw.

Unter Linux bietet glibc strverscmp () an, das aus Gründen der Portabilität auch von gnulib verfügbar ist. Wirklich "menschliches" Sortieren hat jedoch viele andere Macken wie "The Beatles", die als "Beatles, The" sortiert werden. Es gibt keine einfache Lösung für dieses generische Problem.