Самый простой способ сделать "естественную" сортировку чисел в строках?

Question

Я только что видел это, и мне интересно, каков наилучший способ реализовать естественную сортировку, как это?

Обычно в списке 1,4,11,12 сортировка строк (используется в элементах списка) возвращает 1,11,12,4, Как мне реализовать естественный порядок?

Answer 1

Предметы также могут быть

[ 'screen 4 episode 13', 'screen 11 episode 1', .... ]

Для приведенного выше списка и примера списка, приведенного в вопросе, можно использовать следующий метод:

1. Преобразуйте число в элементах в систему на основе сегмента, то есть вычислите максимум цифры в любой строке. Например, в приведенном выше списке значение равно 2. Теперь преобразуйте числа в элементах так, чтобы их длина оказалась такой же, как и максимальная. Следовательно, "эпизод 13 экрана 4" будет преобразован в "эпизод 13 экрана 04", а "эпизод 1 экрана 11" будет преобразован в "эпизод 01 экрана 11".

2. Теперь сортируйте измененный список как строку.

Answer 2

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

Чтобы сгенерировать эти ключи, начните с копии исходных строк, а затем преобразуйте подстроки, представляющие числа, следующим образом:

• Удалите все ведущие нули.
• Подготовьте длину подстроки цифр, закодированную в виде цифры "9", повторенной int(len/9) раз, за ​​которой следует цифра, представляющая len % 9.

Например:

1          -> 11
10         -> 210
9          -> 19
12345678   -> 812345678
987654321  -> 90987654321    // len = 9, int(len / 9) = 1, len % 9 = 0
9876543210 -> 919876543210   // len = 10, int(len / 9) = 1, len % 9 = 1

Вы также можете заменить знаки препинания на клавишах, чтобы "Foo 123" и "Foo-123" сравнивались одинаково.

Модуль Perl Sort::Key::Natural использует этот подход.

Answer 3

Вы можете разбить каждую строку на последовательность токенов. Токен состоит из всех не цифр или всех цифр. Затем выполните сравнение по последовательности токенов, а не по последовательности символов в строке. Токены без цифр сравниваются как строки, токены без цифр сравниваются друг с другом, используя их целочисленные значения.

Это зависит от вас, как все-цифровые токены сравниваются с не-цифровыми токенами, но, скорее всего, вы хотите foo123.txt появляться после foo.txt но прежде fooA.txt, Это означает, что при сравнении токена foo против знака foo<something>, вы не получите ответ сразу, основываясь только на этих двух токенах - вам нужно сравнить <something> против токена следующего foo,

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