使用比较函数进行排序

Question

所以我正在使用几个预先存在的比较器，它们会比较两个元组中的某些值，并在第一个元组大于第二个元组时返回true，在相反情况下返回false。这是其中一个比较器的代码：

def cmpValue(subInfo1, subInfo2):
    """
    Returns True if value in (value, work) tuple subInfo1 is GREATER than
    value in (value, work) tuple in subInfo2
    """
    # TODO...
    if subInfo1[0] > subInfo2[0]:
        return True
    else:
        return False

现在，我有一个包含许多类似于上面比较的元组条目的字典。我想将它们全部按照相反的顺序排序，但我不太明白如何实现。我想到了这样的东西：

sortedDict = sorted(subjects, key=comparator, reverse = True)

但是我不知道该传入什么比较器，因为每个比较器都需要两个参数（subInfo1，subInfo2）。我无法更改比较器函数。

- user1427661

---

Python中的比较函数已被弃用，请改用键函数。 - Ignacio Vazquez-Abrams

if condition: return True else: return False 应该改为 return condition。 - Fred Foo

字典不保留顺序。如果您想要一个排序的字典，应该使用collections模块中的OrderedDict。 - Matt

@IgnacioVazquez-Abrams：我想找一下 cmp 操作符被弃用声明的链接。在这里可以找到... Python Wiki上有一篇文章介绍如何从 cmp 转换为 key。 - Pascal

Answer 1

在Python 3中，sorted函数（以及list.sort函数）不再支持cmp参数。

根据文档，现在的函数签名为sorted(iterable, *, key=None, reverse=False)，因此您需要使用一个key函数来进行自定义排序。文档建议使用：

使用functools.cmp_to_key()将旧式的cmp函数转换为key函数。

下面是一个示例：

>>> def compare(x, y):
...     return x[0] - y[0]
... 
>>> data = [(4, None), (3, None), (2, None), (1, None)]
>>> from functools import cmp_to_key
>>> sorted(data, key=cmp_to_key(compare))
[(1, None), (2, None), (3, None), (4, None)]

然而，您的函数也不符合旧的cmp函数协议，因为它返回True或False。针对您特定的情况，您可以这样做：

>>> your_key = cmp_to_key(make_comparator(cmpValue))
>>> sorted(data, key=your_key)
[(1, None), (2, None), (3, None), (4, None)]

使用@Fred Foo回答中的make_comparator函数。

- kaya3

Answer 2

您正在将比较器作为key函数传递。 您应该将其作为cmp传递，并在某种将其转换为正确比较器的函数中进行包装。

def make_comparator(less_than):
    def compare(x, y):
        if less_than(x, y):
            return -1
        elif less_than(y, x):
            return 1
        else:
            return 0
    return compare

sortedDict = sorted(subjects, cmp=make_comparator(cmpValue), reverse=True)

（实际上，您应该使用关键函数：）

sorted(subjects, operator.itemgetter(0), reverse=True)

还要注意，sortedDict 实际上不是一个 dict，所以名称有点令人困惑。

- Fred Foo

---

此外，比较器不应该返回 True 或 False，而应该返回 -1、0 或 1。 - kindall

函数包装器用于比较器的处理得很不错。你可以提一下 functools.cmp_to_key。 - kindall

functools.cmp_to_key 可用于这种排序情况。 - Jon Clements

请注意，这已经被废弃了。请参阅@IgnacioVazquez-Abrams或我在问题评论中的答案。 - Pascal

Answer 3

kaya3的回答是正确的。我提出了另一种实现方式，其中我们可以使用布尔值作为比较器。

class YourTupleComparator(tuple):
    def __lt__(self, other):
        return self[0] < other[0]

sorted(subjects, key=YourTupleComparator)

- Tuan Chau

---

你能解释一下为什么我们可以这样做吗？ - Tengerye

@Tengerye 你想知道什么？ - Tuan Chau

你的答案看起来很优雅。然而，我不知道它为什么有效（比如为什么只有__lt__就足够了？）。这在Python的官方指南中也没有提到。 - Tengerye

@Tengerye 这里有一种隐含的意思：https://docs.python.org/3/reference/datamodel.html#object.__lt__ 默认实现返回 NotImplemented，当排序方法使用对称运算符翻转参数时...所以你可以只实现 __gt__，它也会起作用（在尝试 key(a) < key(b) 后，它会尝试 key(b) > key(a)）。但这取决于排序算法的实现，一个更健壮的选项是使用 functools.total_ordering。 - fortran

Answer 4

我不知道@Tuan Chau的答案是如何工作的。然而，在复杂情况下可能会失败。

考虑以下比较：每个元素都是一个具有两个维度的元组。如果满足以下两个条件之一，则元素A小于B：1. A[0]小于B[0]。2. A[0]==B[0]且A[1]>B[0]。因此，(1, 2) < (2, 1)，(1, 2) < (1, 1)。

尝试以下代码片段：

from functools import cmp_to_key

class Character(tuple):
    def __le__(self, other) -> bool:
        if self[0] < other[0] or (self[0] == other[0] and self[1] >= other[1]):
            return True
        return False


def compare(x, y):
    if x[0] == y[0]:
        return y[1] - x[1]
    return x[0] - y[0]


if __name__ == "__main__":
    array = [[1, 1], [2, 1], [2, 2], [1, 2]]
    print(sorted(array, key=Character))  # [[1, 1], [1, 2], [2, 1], [2, 2]]

    print(sorted(array, key=cmp_to_key(compare)))  # [[1, 2], [1, 1], [2, 2], [2, 1]]

正如你所看到的，class Character 的结果是错误的。

- Tengerye

Answer 5

我们现在可以使用这个来对一个二维数组进行排序：

A.sort(key=lambda a: (a[0], -a[1]))

这将按照A [0]的升序和A [1]的降序对2D数组进行排序。

- Priyanshu Tiwari

---

这个回答似乎与问题无关，问题是关于使用比较函数进行排序的。关键函数不是比较函数。看起来你正在尝试回答一个不同的问题像这个，虽然那个问题已经有一个相同的答案了，所以没有必要再写一遍。 - kaya3

这个答案与此相关！现在，我们可以在Python3中使用作为比较器的键，而不是比较器。 - Priyanshu Tiwari

它与问题有关，但并不直接回答问题：它只是一个单参数的一元函数，而不是两个参数的二元函数。 - WestCoastProjects