最快排序算法TimSort—各编程语言内置排序(JS/Java/Python/GO等)
Author：zhoulujun Date：
Timsort是一个自适应的、混合的、稳定的排序算法，融合了归并算法和二分插入排序算法的精髓，在现实世界的数据中有着特别优秀的表现。它是由Tim Peter于2002年发明的，用在Python这个编程语言里面。论文：https://svn.python.org/projects/python/trunk/Objects/listsort.txt
在Python 2.3版本中，Tim Peters提出了TimSort算法，并在Python 2.4版本中正式成为Python的排序算法。
在Java 7 Update 6版本中，TimSort算法被引入到Java中，并在Java 8中成为了默认的排序算法。
在ECMAScript 2015（ES6）规范中，TimSort算法被引入到JavaScript中，并在许多现代浏览器中实现。
在Ruby 1.9及更高版本中，Enumerable#sort和Enumerable#sort_by方法使用了TimSort算法。
在.NET Framework 4.5及更高版本中，Array.Sort()和List<T>.Sort()方法使用了TimSort算法。
像Go、Rust、Swift等新语言，都是将TimSort算法作为其默认的排序算法。
在 《排序算法图文讲解（php，javascript，java）》种，插入排序最优时间复杂度也需要 O(n) ，所以可以使用二分查找来减少插入时元素的比较次数，将时间复杂度降为 O(log n)。关于二分查找，推荐阅读 《数组二分查找到二分法的感悟笔记》
二分查找与归并的分两堆（治之策略的算法，包含两个主要的操作：分割与合并）还是不同的。
二分插入排序主要优点是在小数据集场景下排序效率很高
归并排序主要为大数据集场景设计的排序算法。
Timsort 执行过程
算法大体过程是，如果数组长度小于指定阀值（MIN_MERGE）直接使用二分插入算法完成排序，否则执行下面步骤：
先从数组左边开始，执行升序运行得到一个子序列。
将这个子序列放入运行堆栈里，等待执行合并。
检查运行堆栈里的子序列，如果满足合并条件则执行合并。
重复第一个步骤，执行下一个升序运行。
算法实现细节，推荐阅读：
https://www.cnblogs.com/sunshuyi/p/12680918.html
编程码农的回答 https://www.zhihu.com/question/23928138/answer/2553774323
总结：
TimSort这个算法之所以快，是因为它充分利用了现实世界的待排序数据里面，有很多子串是已经排好序的不需要再重新排序，利用这个特性并且加上合适的合并规则可以更加高效的排序剩下的待排序序列。
当Timsort运行在部分排序好的数组里面的时候，需要的比较次数要远小于n㏒n，也是远小于相同情况下的归并排序算法需要的比较次数。但是和其他的归并排序算法一样，最坏情况下的时间复杂度是O(n㏒n)的水平。但是在最坏的情况下，Timsort需要的临时存储空间只有n/2，在最好的情况下，需要的额外空间是常数级别的。从各个方面都能够击败需要O(n)空间和稳定O(n㏒n)时间的归并算法。
转载本站文章《最快排序算法TimSort—各编程语言内置排序(JS/Java/Python/GO等)》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/SortingAlgorithms/9095.html