python - 尽管不保留原始顺序，为什么 python 的排序称为稳定？

Question

总结

自 Python 2.2 以来，保证在 Python 中排序是稳定的，如文档中所述here和 here .

Wikipedia解释稳定的属性对算法的行为意味着什么:

A sorting algorithm is stable if whenever there are two records R and S with the same key, and R appears before S in the original list, then R will always appear before S in the sorted list.

但是，在对元组等对象进行排序时，排序似乎不稳定。

例如，

>>> a = [(1, 3), (3, 2), (2, 4), (1, 2)]
>>> sorted(a)
[(1, 2), (1, 3), (2, 4), (3, 2)]

然而，要被认为是稳定的，我认为新的序列应该是

[(1, 3), (1, 2), (2, 4), (3, 2)]

因为在原始序列中，元组 (1, 3) 出现在元组 (1, 2) 之前。当 1 元“键”相等时，sorted 函数依赖于 2 元“键”。 (澄清一下，一些元组 t 的 1 元键是 t[0] 和 2 元 t[1]。 )

要产生预期的结果，我们必须执行以下操作:

>>> sorted(a, key=lambda t: t[0])
[(1, 3), (1, 2), (2, 4), (3, 2)]

我猜我有一个错误的假设，关于 sorted 或者可能关于在比较期间如何处理元组和/或列表类型。

问题

1. 为什么说 sorted 函数是“稳定的”，即使它以这种方式改变了原始序列？
2. 将默认行为设置为 lambda 版本的行为不会更符合“稳定”的含义吗？为什么不这样设置？
3. 这种行为是否仅仅是元组和/或列表的固有比较方式(即错误假设)的副作用？

谢谢。

---

请注意，这不是关于默认行为是否有用、常见或其他。这是关于默认行为是否一致与稳定的定义(恕我直言，似乎并非如此)以及稳定性的保证文档中提到。

Answer 1

想一想 - (1, 2) 出现在 (1, 3) 之前，不是吗？默认情况下对列表进行排序并不意味着“仅根据第一个元素对其进行排序”。否则你可以说 apple 在字母表中出现在 aardvark 之前。换句话说，这与稳定性无关。

The docs关于如何按字典顺序对诸如 list 和 tuple 的数据结构进行排序也有很好的解释:

In particular, tuples and lists are compared lexicographically by comparing corresponding elements. This means that to compare equal, every element must compare equal and the two sequences must be of the same type and have the same length.