通过将列表转换为集合并返回到列表来排序列表的时间复杂性

Question

我最近看了Raymond Hettingers talk about python dictionaries（以及扩展集…），他提到整数散列到自身，向dict（或集…）添加整数将按顺序插入它们，只要不删除项，顺序将保留在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），还是我在这里遗漏了什么

Answer 1

否。集合不允许对整数进行排序。而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]

Answer 2

一般来说，O(n)排序可以用于整数、字符串和许多其他类型的数据。O（n log n）是使用排序算法所能做的最好的方法，这种算法只使用比较（>，<，==）来确定项目的顺序，但是对于许多类型，您并不局限于这样的算法。具体而言，请参见Radix sort了解整数排序

Answer 3

不，不是一般的。您一定在特殊情况下尝试过，例如，未排序的输入列表包含从0到n的所有数字，每次一次

以下是一个失败的简单案例：

>>> list(set([8, 1]))
[8, 1]

使用CPython 3.8.1 32位完成