查看“︁Timsort”︁的源代码

{{算法信息框|class=[[排序算法]]|image=|caption=A visual representation of Timsort|data=[[数组]]|time=<math>O(n\log n)</math><ref>{{cite web |title=[Python-Dev] Sorting |url=http://mail.python.org/pipermail/python-dev/2002-July/026837.html |last=Peters |first=Tim |work=Python Developers Mailinglist |accessdate=24 February 2011 |quote=[Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best). |archive-date=2018-07-17 |archive-url=https://web.archive.org/web/20180717055327/https://mail.python.org/pipermail/python-dev/2002-July/026837.html |dead-url=no }}</ref><ref>{{cite web|title=[DROPS]|url=http://drops.dagstuhl.de/opus/volltexte/2018/9467/|accessdate=1 September 2018|quote=TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint.|archive-date=2019-09-19|archive-url=https://web.archive.org/web/20190919191540/http://drops.dagstuhl.de/opus/volltexte/2018/9467/|dead-url=no}}</ref>|best-time=<math>O(n)</math><ref name="Chandramouli">{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014}}</ref>|average-time=<math>O(n\log n)</math>|space=<math>O(n)</math>}}'''Timsort''' 是一种混合稳定的[[排序算法]]，源自[[归并排序|合并排序]]和[[插入排序]]，旨在较好地处理真实世界中各种各样的数据。它使用了 [[彼得*麦克罗伊|Peter Mcllroy]] 的"乐观排序和信息理论上复杂性"中的技术，参见 ''第四届年度ACM-SIAM离散算法研讨会论文集''，第467-474页，1993年。 它由 Tim Peters 在2002年实现，并应用于 [[Python|Python编程语言]]。该算法通过查找已经排好序的数据子序列，在此基础上对剩余部分更有效地排序。 该算法通过不断地将特定子序列（称为一个 run ）与现有的 run 合并，直到满足某些条件为止来达成的更有效的排序。 从 2.3 版本起，Timsort 一直是 Python 的标准排序算法。 它还被 [[Java版本歷史|Java SE7]]<ref>{{Cite web|title=[#JDK-6804124] (coll) Replace &quot;modified mergesort&quot; in java.util.Arrays.sort with timsort|url=https://bugs.openjdk.java.net/browse/JDK-6804124|accessdate=11 June 2014|work=JDK Bug System|archive-date=2020-01-11|archive-url=https://web.archive.org/web/20200111192314/https://bugs.openjdk.java.net/browse/JDK-6804124|dead-url=no}}</ref>, [[Android|Android platform]]<ref>{{cite web|title=Class: java.util.TimSort<T>|url=https://android.googlesource.com/platform/libcore/+/gingerbread/luni/src/main/java/java/util/TimSort.java|accessdate=24 February 2011|work=Android Gingerbread Documentation|dead-url=yes|archive-url=https://web.archive.org/web/20150716000631/https://android.googlesource.com/platform/libcore/+/gingerbread/luni/src/main/java/java/util/TimSort.java|archive-date=2015-07-16}}</ref>, [[GNU Octave]],<ref>{{Cite web|title=liboctave/util/oct-sort.cc|url=http://hg.savannah.gnu.org/hgweb/octave/file/0486a29d780f/liboctave/util/oct-sort.cc|accessdate=18 February 2013|work=Mercurial repository of Octave source code|quote=Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.|archive-date=2019-02-06|archive-url=https://web.archive.org/web/20190206060506/http://hg.savannah.gnu.org/hgweb/octave/file/0486a29d780f/liboctave/util/oct-sort.cc|dead-url=no}}</ref> [[Google Chrome|谷歌浏览器]],<ref>{{Cite web|title=Getting things sorted in V8 · V8|url=https://v8.dev/blog/array-sort|accessdate=2018-12-21|work=v8.dev|archive-date=2018-12-21|archive-url=https://web.archive.org/web/20181221090529/https://v8.dev/blog/array-sort|dead-url=no}}</ref> 和 [[Swift (程式語言)|Swift]]<ref>{{Cite web|title=Is sort() stable in Swift 5?|url=https://forums.swift.org/t/is-sort-stable-in-swift-5/21297/9|accessdate=2019-07-04|date=2019-07-04|work=Swift Forums|language=en-US|archive-date=2019-07-04|archive-url=https://web.archive.org/web/20190704174800/https://forums.swift.org/t/is-sort-stable-in-swift-5/21297/9|dead-url=no}}</ref> 用于对非原始类型的数组排序。


==参考文献==
{{reflist}}

==外部链接==
{{排序算法表}}

[[Category:排序算法]]
[[Category:稳定排序]]
[[Category:比较排序]]