Timsort 是一种自适应的、稳定的、自然的归并排序。它在多种部分有序数组上具有超自然的性能（少于所需的 lg(N!) 比较，并且少至 N-1），但速度与 Python 之前在随机数组上高度调整的采样排序混合一样快。
你见过在 CPython 之外使用timsort吗？是否有意义？
Constantin
问问题
8229 次
7 回答
31
是的，在特定的 CPython 或 Python 之外使用 timsort 是很有意义的。
目前正在努力用 timsort 代替 Java 的“修改归并排序”，初步结果相当积极。
于 2009-06-29T20:09:52.003 回答
23
该算法非常通用，但好处是特定于 Python 的。与大多数排序例程不同，Python 的 list.sort（使用 timsort）关心的是避免不必要的比较，因为通常比较比交换项目（总是只是一组指针副本）甚至分配一些更昂贵额外的内存（因为它始终只是一个指针数组，与任何 Python 操作的平均开销相比，开销很小。）
如果您受到类似的限制，那么它可能是合适的。不过，我还没有看到任何其他比较真的那么昂贵的情况:-)
于 2008-09-30T20:14:57.063 回答
6
它看起来并不特别熟悉，但“智能”合并排序在广泛的软件世界中非常普遍。
至于它是否有意义，这取决于您要排序的内容，以及比较与内存分配的相对成本。在内存受限的环境中，需要多达 2*N 字节额外内存的排序不会是一个好的选择。
于 2008-09-30T20:02:01.023 回答
4
现在在Wikipedia上回答： timsort 将用于从 Android 复制它的 Java 7。
于 2010-10-29T07:36:01.403 回答
3
Timsort 现在也在 Android 中：http ://www.kiwidoc.com/java/l/x/android/android/5/p/java.util/c/TimSort
于 2011-06-09T06:53:42.433 回答
0
您链接的描述看起来很笼统。
于 2008-09-30T19:21:28.017 回答
0
Timsort不是特定于 Python 的。在 Python 中使用 Timsort 对对象引用列表进行排序的好处存在于任何具有指针或对象引用的编程语言中。例如，Java SE 7+、Android 和 Swift 使用 Timsort 对对象进行排序。
另一方面，由于缓存一致性，快速排序的某些变体（例如 introsort、dual-pivot 快速排序）通常会更快地对原始类型进行排序，因此通常选择它来执行此任务。
于 2019-11-29T18:20:01.127 回答