Comparaison d'ordre de tri naturel des chaînes de caractères en Java - est-il intégré? [dupliquer]

j'ai testé trois implémentations Java mentionnées ici par d'autres et j'ai trouvé que leur travail était légèrement différent mais aucun comme je m'y attendais.

les deux comparateur alphanumérique et comparateur alphanumérique ne pas ignorer les espaces blancs de sorte que pic2 est placé avant pic 1 .

d'autre part NaturalOrderComparator ignore non seulement les espaces blancs mais aussi tous les zéros principaux de sorte que sig[1] précède sig[0] .

à propos de la performance AlphaNumericStringComparator est ~x10 plus lent que les deux autres.

les instruments de chaîne de caractères comparables, et c'est ce que l'ordre naturel est en Java (comparer en utilisant l'interface comparable). Vous pouvez placer les cordes dans une palette D'arbres ou trier en utilisant les classes Collections ou tableaux.

Cependant, dans votre cas, vous ne voulez pas "ordre naturel" vous voulez vraiment une coutume de comparaison, que vous pouvez ensuite utiliser dans les Collections.méthode de tri ou les Tableaux.méthode de tri qui prend un comparateur.

en termes de logique que vous cherchez à implémenter dans le comparateur, (Nombres séparés par des Points) Je ne suis pas au courant d'implémentations standard existantes de cela, mais comme vous l'avez dit, ce n'est pas un problème difficile.

modifier: dans votre commentaire , votre lien vous obtient ici , qui fait un travail décent si vous ne vous souciez pas du fait qu'il est sensible à la casse. Voici ce code modifié pour vous permettre de passer dans le 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);
            }
        }
    }

Regardez cette implémentation. Il devrait être aussi rapide que possible, sans aucune expression régulière ou manipulation de tableau ou appels de méthode, juste quelques drapeaux et beaucoup de cas.

cela devrait trier n'importe quelle combinaison de nombres à l'intérieur des chaînes et soutenir correctement les nombres qui sont égaux et passer à autre chose.

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

Que Diriez-vous d'utiliser la méthode split() à partir de la chaîne, analyser la chaîne numérique simple et puis les comparer un par un?

 @Test
public void test(){
    System.out.print(compare("1.12.4".split("\."), "1.13.4".split("\."),0));
}


public static int compare(String[] arr1, String[] arr2, int index){
    // if arrays do not have equal size then and comparison reached the upper bound of one of them
    // then the longer array is considered the bigger ( --> 2.2.0 is bigger then 2.2)
    if(arr1.length <= index || arr2.length <= index) return arr1.length - arr2.length;
    int result = Integer.parseInt(arr1[index]) - Integer.parseInt(arr2[index]);
    return result == 0 ?  compare(arr1, arr2, ++index) : result;
}

Je n'ai pas vérifié les étuis de coin mais ça devrait marcher et c'est assez compact

il concasse les chiffres, puis le compare. Et si elle n'est pas applicable, il continue.

public int compare(String o1, String o2) {
if(o1 == null||o2 == null)
    return 0;
for(int i = 0; i<o1.length()&&i<o2.length();i++){
    if(Character.isDigit(o1.charAt(i)) || Character.isDigit(o2.charAt(i)))
    {
    String dig1 = "",dig2 = "";     
    for(int x = i; x<o1.length() && Character.isDigit(o1.charAt(i)); x++){                              
        dig1+=o1.charAt(x);
    }
    for(int x = i; x<o2.length() && Character.isDigit(o2.charAt(i)); x++){
        dig2+=o2.charAt(x);
    }
    if(Integer.valueOf(dig1) < Integer.valueOf(dig2))
        return -1;
    if(Integer.valueOf(dig1) > Integer.valueOf(dig2))
        return 1;
    }       
if(o1.charAt(i)<o2.charAt(i))
    return -1;
if(o1.charAt(i)>o2.charAt(i))
    return 1;
}
return 0;

}

Pourrait être une réponse tardive. Mais ma réponse peut aider quelqu'un d'autre qui a besoin d'un comparateur comme ça.

j'ai vérifié quelques autres comparateurs aussi. Mais la mienne semble plus efficace que d'autres que j'ai comparées. J'ai aussi essayé celui que Yishai a posté. Le mien ne prend que la moitié du temps comme celle mentionnée pour les données de l'ensemble de données alphanumériques de 100 entrées.

/**
 * Sorter that compares the given Alpha-numeric strings. This iterates through each characters to
 * decide the sort order. There are 3 possible cases while iterating,
 * 
 * <li>If both have same non-digit characters then the consecutive characters will be considered for
 * comparison.</li>
 * 
 * <li>If both have numbers at the same position (with/without non-digit characters) the consecutive
 * digit characters will be considered to form the valid integer representation of the characters
 * will be taken and compared.</li>
 * 
 * <li>At any point if the comparison gives the order(either > or <) then the consecutive characters
 * will not be considered.</li>
 * 
 * For ex., this will be the ordered O/P of the given list of Strings.(The bold characters decides
 * its order) <i><b>2</b>b,<b>100</b>b,a<b>1</b>,A<b>2</b>y,a<b>100</b>,</i>
 * 
 * @author kannan_r
 * 
 */
class AlphaNumericSorter implements Comparator<String>
{
    /**
     * Does the Alphanumeric sort of the given two string
     */
    public int compare(String theStr1, String theStr2)
    {
        char[] theCharArr1 = theStr1.toCharArray();
        char[] theCharArr2 = theStr2.toCharArray();
        int aPosition = 0;
        if (Character.isDigit(theCharArr1[aPosition]) && Character.isDigit(theCharArr2[aPosition]))
        {
            return sortAsNumber(theCharArr1, theCharArr2, aPosition++ );
        }
        return sortAsString(theCharArr1, theCharArr2, 0);
    }

    /**
     * Sort the given Arrays as string starting from the given position. This will be a simple case
     * insensitive sort of each characters. But at any given position if there are digits in both
     * arrays then the method sortAsNumber will be invoked for the given position.
     * 
     * @param theArray1 The first character array.
     * @param theArray2 The second character array.
     * @param thePosition The position starting from which the calculation will be done.
     * @return positive number when the Array1 is greater than Array2<br/>
     *         negative number when the Array2 is greater than Array1<br/>
     *         zero when the Array1 is equal to Array2
     */
    private int sortAsString(char[] theArray1, char[] theArray2, int thePosition)
    {
        int aResult = 0;
        if (thePosition < theArray1.length && thePosition < theArray2.length)
        {
            aResult = (int)theArray1[thePosition] - (int)theArray2[thePosition];
            if (aResult == 0)
            {
                ++thePosition;
                if (thePosition < theArray1.length && thePosition < theArray2.length)
                {
                    if (Character.isDigit(theArray1[thePosition]) && Character.isDigit(theArray2[thePosition]))
                    {
                        aResult = sortAsNumber(theArray1, theArray2, thePosition);
                    }
                    else
                    {
                        aResult = sortAsString(theArray1, theArray2, thePosition);
                    }
                }
            }
        }
        else
        {
            aResult = theArray1.length - theArray2.length;
        }
        return aResult;
    }

    /**
     * Sorts the characters in the given array as number starting from the given position. When
     * sorted as numbers the consecutive characters starting from the given position upto the first
     * non-digit character will be considered.
     * 
     * @param theArray1 The first character array.
     * @param theArray2 The second character array.
     * @param thePosition The position starting from which the calculation will be done.
     * @return positive number when the Array1 is greater than Array2<br/>
     *         negative number when the Array2 is greater than Array1<br/>
     *         zero when the Array1 is equal to Array2
     */
    private int sortAsNumber(char[] theArray1, char[] theArray2, int thePosition)
    {
        int aResult = 0;
        int aNumberInStr1;
        int aNumberInStr2;
        if (thePosition < theArray1.length && thePosition < theArray2.length)
        {
            if (Character.isDigit(theArray1[thePosition]) && Character.isDigit(theArray1[thePosition]))
            {
                aNumberInStr1 = getNumberInStr(theArray1, thePosition);
                aNumberInStr2 = getNumberInStr(theArray2, thePosition);

                aResult = aNumberInStr1 - aNumberInStr2;

                if (aResult == 0)
                {
                    thePosition = getNonDigitPosition(theArray1, thePosition);
                    if (thePosition != -1)
                    {
                        aResult = sortAsString(theArray1, theArray2, thePosition);
                    }
                }
            }
            else
            {
                aResult = sortAsString(theArray1, theArray2, ++thePosition);
            }
        }
        else
        {
            aResult = theArray1.length - theArray2.length;
        }
        return aResult;
    }

    /**
     * Gets the position of the non digit character in the given array starting from the given
     * position.
     * 
     * @param theCharArr /the character array.
     * @param thePosition The position after which the array need to be checked for non-digit
     *        character.
     * @return The position of the first non-digit character in the array.
     */
    private int getNonDigitPosition(char[] theCharArr, int thePosition)
    {
        for (int i = thePosition; i < theCharArr.length; i++ )
        {
            if ( !Character.isDigit(theCharArr[i]))
            {
                return i;
            }
        }
        return -1;
    }

    /**
     * Gets the integer value of the number starting from the given position of the given array.
     * 
     * @param theCharArray The character array.
     * @param thePosition The position form which the number need to be calculated.
     * @return The integer value of the number.
     */
    private int getNumberInStr(char[] theCharArray, int thePosition)
    {
        int aNumber = 0;
        for (int i = thePosition; i < theCharArray.length; i++ )
        {
            if(!Character.isDigit(theCharArray[i]))
            {
               return aNumber;
            }
            aNumber += aNumber * 10 + (theCharArray[i] - 48);
        }
        return aNumber;
    }
}

en utilisant RuleBasedCollator pourrait aussi être une option. Bien que vous devez ajouter toutes les règles d'ordre de tri à l'avance donc ce n'est pas une bonne solution si vous voulez prendre en compte de plus grands nombres aussi bien.

ajouter des personnalisations spécifiques comme 2 < 10 est assez facile cependant et pourrait être utile pour trier des identificateurs de version spéciaux comme Trusty < Precise < Xenial < Yakkety .

RuleBasedCollator localRules = (RuleBasedCollator) Collator.getInstance();

String extraRules = IntStream.range(0, 100).mapToObj(String::valueOf).collect(joining(" < "));
RuleBasedCollator c = new RuleBasedCollator(localRules.getRules() + " & " + extraRules);

List<String> a = asList("1-2", "1-02", "1-20", "10-20", "fred", "jane", "pic01", "pic02", "pic02a", "pic 5", "pic05", "pic   7", "pic100", "pic100a", "pic120", "pic121");
shuffle(a);

a.sort(c);
System.out.println(a);