Сортировка строк, содержащих числа, в удобной для пользователя форме

Question

Привыкнув к стандартному способу сортировки строк, я удивился, когда заметил, что Windows сортирует файлы по их именам в некоторой продвинутой форме. Позвольте привести пример:

Track1.mp3
Track2.mp3
Track10.mp3
Track20.mp3

Я думаю, что эти имена сравниваются (при сортировке) по буквам и числам отдельно.

С другой стороны, следующий список тот же самый, отсортированный стандартным образом:
Track1.mp3
Track10.mp3
Track2.mp3
Track20.mp3

Я хотел бы создать алгоритм сравнения в Delphi, который позволял бы мне сортировать строки таким же образом. Сначала я подумал, что будет достаточно сравнить последовательные символы двух строк, пока они являются буквами. Когда в какой-либо позиции обеих строк будет найдена цифра, я прочитаю все следующие за ними цифры, чтобы сформировать число, а затем сравню числа.

Для примера приведу сравнение строк «Track10» и «Track2» следующим образом:
1) читать символы, когда они равны, а буквы - «отслеживать», «отслеживать»
2) если найдена цифра, прочитайте все следующие цифры: «10», «2»
2a) если они равны, переходите к 1 или закончите
Десять больше двух, поэтому «Track10» больше, чем «Track2»

Казалось, что все будет хорошо, пока я не заметил во время моих тестов, что Windows считает «Track010» ниже, чем «Track10», в то время как я думал, что первый был больше, поскольку он длиннее (не говоря уже о том, что согласно мой алгоритм обе строки будут равны, что неправильно).

Не могли бы вы дать мне идею, как именно Windows сортирует файлы по именам, или, может быть, у вас есть готовый алгоритм (на любом языке программирования), на котором я мог бы основываться?

Большое спасибо!
Мариуш

Answer 1

Джефф написал статью об этом на Coding Horror. Это называется естественная сортировка , где вы эффективно обрабатываете группу цифр как один «символ». Существуют реализации на всех языках под солнцем, но, как ни странно, они обычно не встроены в стандартные библиотеки большинства языков.

Answer 2

Абсолютно проще всего, как я обнаружил, было выделить нужную строку, поэтому в случае OP Path.GetFileNameWithoutExtension () удалите нецифровые символы, преобразуйте в int и отсортируйте. Используя LINQ и некоторые методы расширения, это одна строка. В моем случае я собирался по каталогам:

Directory.GetDirectories(@"a:\b\c").OrderBy(x => x.RemoveNonDigits().ToIntOrZero())

Где RemoveNonDigits и ToIntOrZero - методы расширений:

public static string RemoveNonDigits(this string value) {
    return Regex.Replace(value, "[^0-9]", string.Empty);
}

public static int ToIntOrZero(this string toConvert) {
    try {
        if (toConvert == null || toConvert.Trim() == string.Empty) return 0;            
        return int.Parse(toConvert);
    } catch (Exception) {
        return 0;
    }
}

Методы расширения являются общими инструментами, которые я использую повсюду. YMMV.

Answer 3

Мать всех сортов:

ls '*.mp3' | sort --version-sort