Timsort
Timsort 是一种混合稳定的排序算法,源自合并排序和插入排序,旨在较好地处理真实世界中各种各样的数据。它使用了 Peter Mcllroy 的”乐观排序和信息理论上复杂性”中的技术,参见 第四届年度ACM-SIAM离散算法研讨会论文集,第467-474页,1993年。 它由 Tim Peters 在2002年实现,并应用于 Python编程语言。该算法通过查找已经排好序的数据子序列,在此基础上对剩余部分更有效地排序。 该算法通过不断地将特定子序列(称为一个 run )与现有的 run 合并,直到满足某些条件为止来达成的更有效的排序。 从 2.3 版本起,Timsort 一直是 Python 的标准排序算法。 它还被 Java SE7 Android platform, GNU Octave, 谷歌浏览器, 和 Swift 用于对非原始类型的数组排序。
原文地址:https://zh.wikipedia.org/wiki/Timsort
在知识共享 署名-相同方式共享 3.0协议之条款下提供
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 张拓的博客!