Сортировка по строке, которая может содержать число

Ответ 1

Алфавитный алгоритм

С веб-сайта

"Люди сортируют строки с номерами по-разному, чем программное обеспечение. Большинство алгоритмов сортировки сравнивают значения ASCII, что приводит к упорядочению, которое несовместимо с человеческой логикой. Здесь, как исправить это.

Изменить: здесь ссылка на Java Comparator Implementation с этого сайта.

Ответ 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 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());

Этот алгоритм требует гораздо большего тестирования, но, похоже, он выглядит довольно хорошо.

[EDIT] Я добавил еще несколько комментариев, чтобы быть более четкими. Я вижу, что ответов гораздо больше, чем когда я начал кодировать это... Но я надеюсь, что я дал хорошую стартовую базу и/или некоторые идеи.

Ответ 3

Ян Гриффитс из Microsoft имеет реализацию С#, которую он называет Natural Sorting. Портирование на Java должно быть довольно простым, проще, чем с C в любом случае!

ОБНОВЛЕНИЕ: Кажется, что пример Java на eekboom, который делает это, см. "compareNatural" и используйте это как сортировщик для сортировки.

Ответ 4

Реализация, которую я предлагаю здесь, проста и эффективна. Он не выделяет лишнюю память, прямо или косвенно, с помощью регулярных выражений или методов, таких как 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);
}

Ответ 5

Я понимаю, что вы в java, но вы можете посмотреть, как работает StrCmpLogicalW. Это то, что Explorer использует для сортировки имен файлов в Windows. Вы можете посмотреть реализацию WINE здесь.

Ответ 6

Разделите строку на строки букв и цифр, поэтому "foo 12 bar" станет списком ( "foo", 12, "bar" ), а затем используйте список в качестве ключа сортировки. Таким образом, числа будут упорядочены в цифровом порядке, а не в алфавитном порядке.

Ответ 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]

Ответ 8

Alphanum algrothim это хорошо, но это не соответствует требованиям, предъявляемым к проекту, я работаю. Мне нужно уметь правильно сортировать отрицательные и десятичные числа. Вот реализация, которую я придумал. Любая обратная связь будет высоко ценится.

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. Я хотел использовать метод java.lang.String.split() и использовать "lookahead/lookbehind" для хранения токенов, но я не мог заставить его работать с регулярным выражением, которое я использовал.

Ответ 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);
    }

}

Ответ 10

До открытия этого потока я реализовал аналогичное решение в javascript. Возможно, моя стратегия найдет вас хорошо, несмотря на различный синтаксис. Как и выше, я анализирую две сравниваемые строки и разбиваю их на массивы, разделяя строки на непрерывные числа.

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

I.e., 'hello22goodbye 33' = > ['hello', 22, 'goodbye', 33]; Таким образом, вы можете перемещаться по элементам массивов в парах между строками1 и строкой2, делать какое-то принуждение типа (например, этот элемент действительно является числом?) И сравнивать по ходу.

Рабочий пример здесь: http://jsfiddle.net/F46s6/3/

Обратите внимание: в настоящее время я поддерживаю только целочисленные типы, хотя обработка десятичных значений не будет слишком сложной.

Ответ 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);
        }

Ответ 12

Я создал проект для сравнения различных реализаций. Это далеко не завершено, но это отправная точка.

Ответ 13

Вот решение со следующими преимуществами по сравнению с алгоритмом Alphanum:

1. В 3,25 раза быстрее (проверено на данных из главы "Эпилог" описания Alphanum)
2. Не потребляет дополнительной памяти (без разделения строк, без разбора чисел)
3. Обрабатывает ведущие нули правильно (например, "0001" равно "1", "01234" меньше, чем "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++;
            }
        }
    }
}

Ответ 14

Я думаю, вам придется делать сравнение по-характеру. Возьмите символ, если он является символом числа, продолжайте схватывать, а затем снова создайте символы в одну строку чисел и преобразуйте их в int. Повторите на другой строке, и только тогда выполните сравнение.

Ответ 15

Короткий ответ: исходя из контекста, я не могу сказать, является ли это всего лишь очень быстро и грязным кодом для личного использования или ключевой частью последнего внутреннего программного обеспечения Goldman Sachs, поэтому я открою говоря: 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

Ответ 16

Несмотря на то, что вопрос задан с помощью 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
   })

}

Ответ 17

Моя проблема заключалась в том, что у меня есть списки, состоящие из комбинации буквенно-цифровых строк (например, C22, C3, C5 и т.д.), Буквенных строк (например, A, H, R и т.д.) И просто цифр (например, 99, 45 и т.д.), Которые необходимо отсортировать в порядок A, C3, C5, C22, H, R, 45, 99. У меня также есть дубликаты, которые нужно удалить, поэтому я получаю только одну запись.

Я также не просто работаю со строками, я упорядочиваю объект и использую определенное поле в объекте, чтобы получить правильный порядок.

Решение, которое, кажется, работает для меня:

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

Он "заимствует" некоторый код, который я нашел здесь в Stackoverflow, плюс несколько моих собственных настроек, чтобы заставить его работать так, как мне это тоже нужно.

Из-за попытки упорядочить объекты, нуждающихся в компараторе, а также в удалении дубликатов, мне пришлось использовать одну отрицательную пометку: мне сначала нужно записать свои объекты в TreeMap, прежде чем записывать их в Treeset. Это может немного повлиять на производительность, но, учитывая, что списки будут содержать максимум около 80 кодов, это не должно быть проблемой.

Ответ 18

У меня была похожая проблема, когда мои строки имели разделенные пробелами сегменты внутри. Я решил это так:

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

Как вы можете видеть, я использовал Apaches StringUtils.compare() и NumberUtils.compere() в качестве стандартной справки.

Ответ 19

В приведенном примере числа, которые вы хотите сравнить, имеют пробелы вокруг них, а другие числа - нет, поэтому почему регулярное выражение не работает?

bbb 12 ccc

против.

eee 12 ddd jpeg2000 eee

Ответ 20

Если вы пишете класс компаратора, вы должны реализовать свой собственный метод сравнения, который будет сравнивать два символа строки по символу. Этот метод сравнения должен проверять, имеете ли вы дело с алфавитными символами, числовыми символами или смешанными типами (включая пробелы). Вам нужно будет определить, как вы хотите, чтобы смешанный тип действовал, независимо от того, числятся ли они до буквенных символов или после, и где пробелы подходят и т.д.

Ответ 21

В Linux glibc предоставляет strverscmp(), он также доступен из gnulib для переносимости. Однако действительно "человеческая" сортировка имеет множество других причуд, таких как "The Beatles", которые сортируются как "Beatles, The". Нет простого решения этой общей проблемы.