代码之家 › 专栏 › 技术社区 › Saif

排序时python如何决定何时调用比较器?

math sorting algorithm python

Saif · 技术社区 · 2 年前

from functools import cmp_to_key

def compare(a, b):
  print('comparator called')
  return a - b
  
mylist = [5, 1, 2, 4, 3]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)


mylist = [1, 2, 3, 4, 5]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)


mylist = [5, 4, 3, 2, 1]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)


mylist = [5, 1, 2, 3, 4]
sorted_list = sorted(mylist, key=cmp_to_key(compare))
print(sorted_list)

输出:

comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
comparator called
[1, 2, 3, 4, 5]

您可以看到,对于相同的输入大小,4种情况下调用比较器的次数不同。

有人能帮我理解python是如何决定何时或何时不调用比较器的吗?

另外,请告诉我最佳、平均和最坏情况的时间复杂度

1 回复 | 直到 2 年前

juanpa.arrivillaga 2 年前

因此,为列表中的每个项调用键函数 . 但是当你使用 cmp_to_key source code, it is equivalent to :

def cmp_to_key(mycmp):
    """Convert a cmp= function into a key= function"""
    class K(object):
        __slots__ = ['obj']
        def __init__(self, obj):
            self.obj = obj
        def __lt__(self, other):
            return mycmp(self.obj, other.obj) < 0
        def __gt__(self, other):
            return mycmp(self.obj, other.obj) > 0
        def __eq__(self, other):
            return mycmp(self.obj, other.obj) == 0
        def __le__(self, other):
            return mycmp(self.obj, other.obj) <= 0
        def __ge__(self, other):
            return mycmp(self.obj, other.obj) >= 0
        __hash__ = None
    return K

事实上 如果需要,可以用C实现 see that implementation ,但实际上是一样的)

比较函数 调用次数与比较发生的次数相同(另一方面,排序算法仅使用 < 项目之间的比较,但您可能会使用对于其他需要完全丰富的比较实现的事情)。CPython使用Timsort,这是一种高度调优的自适应合并排序,它具有最坏情况下的O(N*log N)行为(但对于几乎排序的数据,最佳情况下可以是O(N))

Daniel Trugman 2 年前

代码是 here .

有关排序算法的更多信息 here

最差(&W);平均情况:O(n log n)

推荐文章

Sanskriti · 在C中,为什么10/3给出3.000,而它应该给出3.333?(保持10和3的变量被声明为“双”)

1 年前

Abhijit Sarkar · 为什么sort忽略了类中定义的总排序方法?

1 年前

Cute dog · 如何将文本与重新排序的图像相匹配?

1 年前

Shefali Kanaujia · 对C中向量的向量进行排序++

1 年前

Lakshya Kashyap · 如何先按数字降序排序,然后按字母升序排序

2 年前