通过将列表转换为集合并重新转换为列表来对列表进行排序的时间复杂性

问题描述

我最近看了Raymond Hettingers talk about python dictionaries(以及扩展集.)他还提到，整数会自行散列，将整数加到字典(或集合……)将按顺序插入它们，只要您不删除项，顺序将在python3.6中保留(可能在更高版本？)。在this question的回答中，说明字典保持插入顺序，但是对于集合，它看起来就像整数是根据它们的值排序的。

现在：根据time-complexity section of python.org和更详细的here，将一个元素添加到集合的平均时间复杂度为O(1)。这意味着如果您有一个未排序的整数列表，只需执行以下操作即可对它们进行排序：

sorted_list = list(set(unsorted_list))

就我测试过的情况而言，似乎就是这种情况(用随机序列测试了1000次)。

我现在的问题是：这是否意味着可以在O(N)时间内对python中的整数进行排序？

对我来说，这是接缝的，因为构建集合需要O(N)，将集合转换回列表需要O(N)，还是我在这里遗漏了什么？

---

解决方案

否。设置不允许对整数进行排序。而hashes of integers are well-defined集合的顺序为任意。

集的顺序可能因实现、流程和实例而异。

# CPython 3.7.4
>>> list({1, 8})
[8, 1]
>>> list({8, 1})
[8, 1]
# PyPy 3.6.9 (PyPy 7.3.0)
>>> list({1, 8})
[1, 8]
>>> list({8, 1})
[8, 1]
# CPython 2.7.10
>>> list({1, 8})
[8, 1]
>>> list({8, 1})
[8, 1]
# Jython 2.7.1 (java13.0.2)
>>> list({1, 8})
[1, 8]
>>> list({8, 1})
[1, 8]

集的顺序还可能取决于实例的历史记录。

# CPython 3.7.4
>>> a = {1, 3, 4, 8}
>>> list(a)
[8, 1, 3, 4]
>>> a.add(2)
>>> list(a)
[1, 2, 3, 4, 8]
>>> a.discard(2)
>>> list(a)
[1, 3, 4, 8]