Sort on a string that may contain a number

Мне нужно написать класс Java-компаратора, который сравнивает строки, однако с одним поворотом. Если две сравниваемые строки одинаковы, в начале и конце строки совпадают, а средняя часть, которая отличается, является целым числом, тогда сравните на основе числовых значений этих целых чисел. Например, я хочу, чтобы следующие строки заканчивались в порядке их отображения:

• aaa


• bbb 3 ccc


• bbb 12 ccc


• ccc 11


• ddd


• eee 3 ddd jpeg2000 eee


• eee 12 ddd jpeg2000 eee

Как вы можете видеть, в строке могут быть и другие целые числа, поэтому я не могу просто использовать регулярные выражения для выделения любого целого числа. Я подумываю о том, чтобы просто пройтись по строкам с начала, пока не найду бит, который не совпадает, затем перейти к концу, пока не найду бит, который не совпадает, а затем сравнить бит в середине с регулярным выражением "[0-9] +", и если он сравнивает, то выполняет числовое сравнение, в противном случае выполняет лексическое сравнение.

Есть ли способ лучше?

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

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

С веб-сайта

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

Редактировать: Вот ссылка на реализацию Java Comparator с этого сайта.

Интересная маленькая задача, мне понравилось ее решать.

Вот мой взгляд на проблему:

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

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

[РЕДАКТИРОВАТЬ] Я добавил еще несколько комментариев, чтобы было понятнее. Я вижу, что ответов гораздо больше, чем когда я начинал кодировать это... Но я надеюсь, что предоставил хорошую отправную базу и / или несколько идей.

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

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

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