在Python中对类实例排序

Question

Python 2.7是怎么给普通类的实例排序的？我想了解一下默认的排序方式。

假设我有一个类：

class S():
    pass

然后我可以创建几个这个类的实例，并对它们进行排序：

a = S(); b = S(); c = S()
l = [(a,'a'), (b,'b') ,(c, 'c')]
sorted(l)

这样就会打印出这些对象的排序结果。现在我有两个问题：

• Python在排序的时候是用对象的 __hash__() 方法吗？也就是说，它是用对象的 id() 吗？
• 我可以重写 __hash__() 方法来影响排序的行为吗？

Answer 1

我在自己的电脑上试了你的例子（python 2.7）：

>>> sorted(l)
[(<__main__.S instance at 0x107142a70>, 'a'), (<__main__.S instance at 0x107142ab8>, 'b'), (<__main__.S instance at 0x107142b00>, 'c')]

注意，排序后的列表是按照 id() 的顺序排列的：

>>> id(a)
4413729392
>>> id(b)
4413729464
>>> id(c)
4413729536

如果我生成哈希值，我得到：

>>> hash(a)
275858087
>>> hash(b)
-9223372036578917717
>>> hash(c)
275858096

这表明排序并不是基于哈希值的。

想了解如何让python按照你想要的方式排序你的类，可以看看derekerdmann的回答。

补充：顺便说一下，如果你把列表中的项目反向放置，然后再排序，你会得到：

>>> l = [(c,'c'), (b, 'b'), (a, 'a')]
>>> sorted(l)
[(<__main__.S instance at 0x107142a70>, 'a'), (<__main__.S instance at 0x107142ab8>, 'b'), (<__main__.S instance at 0x107142b00>, 'c')]

再次强调，它是按照 id() 的顺序排序的。

Answer 2

Python 3自带的排序功能会用到你类里的__lt__方法。

在Python中，丰富的比较方法很特别，因为如果没有定义__lt__，它们可以返回一个特殊的NotImplemented类型。你可以查看这个页面的文档了解更多信息：http://docs.python.org/reference/datamodel.html#the-standard-type-hierarchy

由于NotImplemented的真值是True，所以任何得到NotImplemented的布尔比较都会继续进行，就好像第一个元素确实小于第二个一样，这样排序就会让列表保持原来的顺序。

你可以看看交互式命令行。你会看到在排序中如何使用真值，Python会认为这两个对象彼此都是小于的：

>>> class S():
...     pass
...
>>> a = S()
>>> b = S()
>>> a.__lt__( b )
NotImplemented
>>> if a.__lt__( b ):
...     print( "derp!" )
...
derp
>>> if b.__lt__(a):
...     print( "derp" )
...
derp

这里还有一些参考资料：

• __lt__方法（非官方Python参考维基）
• 排序迷你教程
• 内置常量

编辑： 在查看Python 2.7后，发现排序时使用的是对象的ID，而在像你例子中的简单类上__lt__方法是未定义的。抱歉造成了任何困惑。

Answer 3

Python的排序算法只通过“小于”这个比较方式来对比项目。这个比较可以通过一个叫做__cmp__()的特殊方法来实现（不过这个方法现在已经不推荐使用了），或者通过类里的__lt__()来实现。

如果没有特别的指示告诉Python怎么比较两个对象，它会使用id()来进行比较（而不是使用哈希值），这适用于同类型的对象，就像你提到的情况一样。