Сортировка по строке, которая может содержать число
Мне нужно написать класс 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);
}