如何使用键函数对python中的填充字符串属性进行排序

Question

假设l是一个具有字符串属性x的c类对象的列表。l应该根据以下条件进行排序:对于任意两个项:在最后一个斜杠字符处分割x，取后缀，在两者前面加一个零填充，使它们长度相等，并按字母顺序进行比较。我读到，应该使用键函数在python中进行排序。然而，我无法找到任何方法来实现这种方式所需的排序标准。如果关键函数不是实现所需排序的正确方法，我很乐意使用“正确”的解决方案。

Answer 1

使用键函数是有点棘手的；使用自定义比较函数会更容易。Python2支持sort的自定义比较函数，但Python3不支持。但是，使用键函数进行排序要比使用自定义比较函数高效得多:对列表中的每个项只调用一次键函数，而对于进行的每个比较必须调用一个自定义比较函数。

解决这个问题的“关键”是要认识到，只要两个字符串的长度相等，那么每个字符串加多少个零并不重要。因此，我们只需确定数据中最长字符串的长度，并将所有字符串填充到该长度。

要确定长度，我们可以使用一个相对简单的生成器表达式，该表达式使用rsplit获取最后斜杠后字符串部分的长度，并将这些长度传递给内置的max函数。然后我们可以在我们的关键函数中使用最大长度。

下面的代码用于Python2，但是如果您修复show函数中的print语句，它将在Python3上工作。

#!/usr/bin/env python

data = [
    'a/bc/this',
    'a/bc/is',
    'a/bc/a',
    'a/bc/short',
    'a/bc/test',
    'a/bc/123',
    'a/bc/24',
    'a/bc/5',
]

#Simple sequence printer
def show(seq):
    for row in seq:
        print row
    print

#Get maximum length of the string after the last slash in each data string
maxlen = max(len(s.rsplit('/', 1)[1]) for s in data)

#Key function that pads the string after the last slash
key = lambda s: s.rsplit('/', 1)[1].rjust(maxlen, '0')

#Test the key function
show([(s, key(s)) for s in data])

new_data = sorted(data, key=key)
show(new_data)

输出

('a/bc/this', '0this')
('a/bc/is', '000is')
('a/bc/a', '0000a')
('a/bc/short', 'short')
('a/bc/test', '0test')
('a/bc/123', '00123')
('a/bc/24', '00024')
('a/bc/5', '00005')

a/bc/5
a/bc/a
a/bc/24
a/bc/is
a/bc/123
a/bc/test
a/bc/this
a/bc/short

我不知道Timsort如何使用键函数进行排序的确切细节，但它相当于：

1. 将项目列表转换为(键、项)元组的列表。
2. 对元组列表进行排序，只对键进行排序&忽略项。
3. 通过从排序列表中的元组中删除项，重新生成新的项列表。

这只是一个粗略的指南，因为Timsort是用C语言编写的。