Python中stable_sort的实现及是否存在类似C++ stable_sort的函数问询

1. 是否存在类似C++ stable_sort()的函数？ #

当然有。Python内置的两个排序工具都是稳定排序，完全可以替代C++的stable_sort()：

• sorted()：全局函数，返回一个新的排序后的列表，原列表不变
• list.sort()：列表的内置方法，直接在原列表上进行排序，无返回值

两者的核心特性是：当多个元素的排序键值相等时，会严格保留它们在原始序列中的相对顺序，和C++ stable_sort()的行为完全一致。

2. Python稳定排序的实现方法 #

Python的排序算法采用Timsort，这是一种专门为实际场景优化的混合排序算法，天生支持稳定排序，具体实现逻辑如下：

• 分割为有序子序列（Run）：先遍历原列表，将其分割成多个长度在32到64之间的有序子序列（称为Run）。如果遇到无序的短序列，会用插入排序将其整理为有序Run。
• 归并有序子序列：按照特定规则对这些有序Run进行归并操作，归并过程中会严格比较元素，当元素相等时，始终优先保留来自原序列中靠前的元素，以此保证排序的稳定性。
• 效率优化：Timsort结合了插入排序（小数据量高效）和归并排序（大数据量稳定高效）的优势，在保证稳定性的同时，也拥有出色的平均和最坏时间复杂度（均为O(n log n)）。

示例验证 #

下面的例子可以直观展示稳定排序的特性：

# 包含重复键值的元组列表
items = [(3, "apple"), (1, "banana"), (3, "cherry"), (2, "date"), (3, "elderberry")]
# 按元组的第一个元素排序
sorted_items = sorted(items, key=lambda x: x[0])
print(sorted_items)

输出结果：

[(1, 'banana'), (2, 'date'), (3, 'apple'), (3, 'cherry'), (3, 'elderberry')]

可以看到，所有键值为3的元素完全保留了它们在原列表中的相对顺序，证明排序是稳定的。

内容的提问来源于stack exchange，提问作者Vivek Maddeshiya