1

我刚看到这个，我想知道实现这样的自然排序的最佳方法是什么？

通常在一个列表中1,4,11,12的字符串排序（用于列出项目）返回1,11,12,4。如何实现自然排序？

在此处输入图像描述

4

3 回答 3

2

The items can also be 

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

For the above mentioned list and the sample list provided in the question, following method can be used:

  1. Convert the number in the elements to a bucket based system, i.e calculate the maximum of the digit in any of the string. For example in the above list, the value is 2. Now convert the numbers in the elements in such a way that its length turns out to be of length as same as the maximum. Therefore,'screen 4 episode 13' will be converted to 'screen 04 episode 13' and 'screen 11 episode 1' will be converted to 'screen 11 episode 01'.

  2. Now sort the modified list like a string.

于 2012-06-11T11:16:14.687 回答
1

您可以将每个字符串拆分为一系列标记。令牌由所有非数字或所有数字组成。然后对标记序列进行比较，而不是对字符串中的字符序列进行比较。非数字标记像字符串一样进行比较，全数字标记使用它们的整数值相互比较。

如何将全数字标记与非数字标记进行比较取决于您，但您很可能希望foo123.txt出现在 之后foo.txt但之前fooA.txt。这意味着当您将标记foo与标记进行比较时foo<something>，您不会仅根据这两个标记立即生成答案——您需要与<something>后面的标记进行比较foo。

然后可以优化该基本方法，以确保您不会进行任何不必要的字符串拆分。

于 2012-06-11T10:02:10.060 回答
1

一个有效的解决方案是为每个要排序的字符串生成一个可以按字典顺序进行比较的键，然后使用这些键对原始字符串进行排序。

要生成这些键，请从原始字符串的副本开始，然后将表示数字的子字符串转换如下：

  • 删除所有前导零。
  • 将数字子串长度编码为数字 '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使用这种方法。

于 2012-06-11T10:14:59.087 回答