在本文中，术语 python 和 cpython（该语言的参考实现）可以互换使用。本文专门讨论 cpython，不涉及 python 的任何其他实现。
python 是一种美丽的语言，它允许程序员用简单的术语表达他们的想法，而将实际实现的复杂性抛在脑后。
它抽象出来的东西之一就是排序。
你可以轻松找到“python中排序是如何实现的？”这个问题的答案。这几乎总是回答另一个问题：“python 使用什么排序算法？”。
然而，这常常会留下一些有趣的实现细节。
有一个实现细节我认为讨论得还不够，尽管它是七年前在 python 3.7 中引入的：
立即学习“Python免费学习笔记（深入）”；
sorted() 和 list.sort() 已针对常见情况进行了优化，速度提高了 40-75%。 （由 elliot gorokhovsky 在 bpo-28685 中贡献。）
但是在我们开始之前...
简要重新介绍 python 中的排序
当你需要在python中对列表进行排序时，你有两种选择：
- 列表方法：list.sort（*，key=none，reverse=false），它对给定列表进行就地排序
- 内置函数：sorted(iterable, /, *, key=none, reverse=false)，它返回一个排序列表而不修改其参数
如果需要对任何其他内置可迭代对象进行排序，则无论作为参数传递的可迭代对象或生成器的类型如何，都只能使用已排序。
sorted 总是返回一个列表，因为它内部使用了 list.sort。
这是用纯 python 重写的 cpython 排序 c 实现的大致等效项：
def sorted(iterable: iterable[any], key=none, reverse=false):
new_list = list(iterable)
new_list.sort(key=key, reverse=reverse)
return new_list
是的，就这么简单。
python 如何使排序更快
正如 python 内部排序文档所说：
有时可以用更快的特定类型比较来代替较慢的通用 pyobject_richcomparebool
简而言之，这个优化可以描述如下：
当列表是同质的时，python 使用特定于类型的比较函数
什么是同质列表？
同构列表是仅包含一种类型的元素的列表。
例如：
homogeneous = [1, 2, 3, 4]
另一方面，这不是一个同质列表：
heterogeneous = [1, "2", (3, ), {'4': 4}]
有趣的是，python 官方教程指出：
列表是可变的，并且它们的元素通常是同质的并且可以通过迭代列表来访问
关于元组的旁注
同一个教程指出：
元组是不可变的，并且通常包含异构序列元素
因此，如果您想知道何时使用元组或列表，这里有一条经验法则：
如果元素类型相同，则使用列表，否则使用元组
等等，那么数组呢？
python 为数值实现了同构数组容器对象。
但是，从 python 3.12 开始，数组没有实现自己的排序方法。
对它们进行排序的唯一方法是使用排序，它在内部从数组中创建一个列表，并在此过程中删除任何与类型相关的信息。
为什么使用特定于类型的比较函数有帮助？
python 中的比较成本很高，因为 python 在进行任何实际比较之前会执行各种检查。
以下是在 python 中比较两个值时在幕后发生的情况的简化解释：
- python 检查传递给比较函数的值不为 null
- 如果值的类型不同，但右操作数是左操作数的子类型，python 使用右操作数的比较函数，但相反（例如，它将使用 ）
- 如果值属于相同类型或不同类型但都不是另一个的子类型：
- python 将首先尝试左操作数的比较函数
- 如果失败，它将尝试右操作数的比较函数，但相反。
- 如果也失败，并且比较是相等或不等，它将返回身份比较（对于引用内存中同一对象的值，则为 true）
- 否则，它会引发 typeerror
除此之外，每种类型自己的比较函数都会实现额外的检查。
例如，在比较字符串时，python 会检查字符串字符是否占用超过一个字节的内存，而 float 比较会以不同的方式比较一对 float 和一个 float 与一个 int 。
更详细的解释和图表可以在这里找到：adding data-aware sort optimizations to cpython
在引入此优化之前，每次在排序过程中比较两个值时，python 都必须执行所有这些各种特定类型和非特定类型的检查。
提前检查列表元素的类型
除了迭代列表并检查每个元素之外，没有什么神奇的方法可以知道列表中的所有元素是否属于同一类型。
自定义设置的程度更高可以满足大部分中小型企业的建站需求，同时修正了上一版中发现的BUG，优化了核心的代码占用的服务器资源更少，执行速度比上一版更快 主要的特色功能如下： 1）特色的菜单设置功能，菜单设置分为顶部菜单和底部菜单，每一项都可以进行更名、选择是否隐 藏，排序等。 2）增加企业基本信息设置功能，输入的企业信息可以在网页底部的醒目位置看到。 3）增加了在线编辑功能，输入产品信息，企业介绍等栏
python 几乎完全做到了这一点 - 检查传递给 list.sort 或作为参数排序的 key 函数生成的排序键的类型
构建键列表
如果提供了 key 函数，python 使用它来构造键列表，否则它使用列表自己的值作为排序键。
以一种过于简单的方式，键的构造可以表示为以下python代码。
if key is none:
keys = list_items
else:
keys = [key(list_item) for list_item in list_item]
注意，cpython 内部使用的键是 cpython 对象引用的 c 数组，而不是 python 列表
一旦构造了键，python 就会检查它们的类型。
检查密钥类型
在检查键的类型时，python 的排序算法会尝试确定键数组中的所有元素是否都是 str、int、float 或 tuple，或者只是同一类型，但对基本类型有一些限制。
值得注意的是，检查键的类型会预先增加一些额外的工作。 python 这样做是因为它通常可以通过加快实际排序速度来获得回报，特别是对于较长的列表。
整型约束
int 应该不是bignum
实际上，这意味着要使此优化发挥作用，整数应小于 2^30 - 1（这可能因平台而异）
顺便说一句，这里有一篇很棒的文章，解释了 python 如何处理大整数：# how python implements super long integers?
强度约束
字符串中的所有字符应占用小于 1 个字节的内存，这意味着它们应由 0-255 范围内的整数值表示
实际上，这意味着字符串应该只包含拉丁字符、空格和 ascii 表中的一些特殊字符。
浮动约束
为了使此优化发挥作用，浮动没有任何限制。
元组约束
- 仅检查第一个元素的类型
- 这个元素本身不应该是一个元组
- 如果所有元组的第一个元素共享相同的类型，则比较优化将应用于它们
- 所有其他元素都照常进行比较
我如何应用这些知识？
首先，知道是不是很有趣？
其次，在 python 开发者面试中提及这些知识可能是一个很好的接触。
对于实际的代码开发来说，了解这个优化可以帮助你提高排序性能。
通过明智地选择值类型进行优化
根据引入此优化的 pr 中的基准，对仅包含浮点数的列表进行排序，而不是对末尾带有单个整数的浮点数列表进行排序，速度几乎是前者的两倍。
所以当需要优化时，像这样转换列表
floats_and_int = [1.0, -1.0, -0.5, 3]
进入看起来像这样的列表
just_floats = [1.0, -1.0, -0.5, 3.0] # note that 3.0 is a float now
可能会提高性能。
使用对象列表的键进行优化
虽然 python 的排序优化适用于内置类型，但了解它如何与自定义类交互也很重要。
在对自定义类的对象进行排序时，python 依赖于您定义的比较方法，例如 __lt__（小于）或 __gt__（大于）。
但是，特定于类型的优化不适用于自定义类。
python 将始终使用这些对象的通用比较方法。
这是一个例子：
class myclass:
def __init__(self, value):
self.value = value
def __lt__(self, other):
return self.value < other.value
my_list = [myclass(3), myclass(1), myclass(2)]
sorted_list = sorted(my_list)
在这种情况下，python 将使用 __lt__ 方法进行比较，但它不会从特定于类型的优化中受益。排序仍然可以正常工作，但可能不如排序内置类型那么快。
如果在对自定义对象进行排序时性能至关重要，请考虑使用返回内置类型的关键函数：
sorted_list = sorted(my_list, key=lambda x: x.value)
后记
过早的优化，尤其是在 python 中，是邪恶的。
您不应该围绕 cpython 中的特定优化来设计整个应用程序，但了解这些优化是有好处的：充分了解您的工具是成为更熟练的开发人员的一种方式。
留意此类优化可以让您在情况需要时利用它们，特别是当性能变得至关重要时：
考虑一个场景，您的排序基于时间戳：使用同质整数列表（unix 时间戳）而不是日期时间对象可以有效地利用此优化。
但是，重要的是要记住，代码的可读性和可维护性应该优先于此类优化。
虽然了解这些低级细节很重要，但欣赏 python 的高级抽象也同样重要，正是这些抽象使其成为一种高效的语言。
python 是一门令人惊叹的语言，深入探索它可以帮助您更好地理解它并成为一名更好的 python 程序员。
