Вопрос-ответ

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] +", и если он сравнивает, то выполняет числовое сравнение, в противном случае выполняет лексическое сравнение.

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

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

Переведено автоматически
Ответ 1

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

С веб-сайта

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

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

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

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

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

Ответ 3

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

ОБНОВЛЕНИЕ: Кажется, на eekboom есть пример Java, который делает это, смотрите "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);
}
java algorithm string