原文地址 https://www.cnblogs.com/brucecloud/p/6085703.html

Timsort 是一种混合稳定的排序算法,采用归并排序混合插入排序的设计,在多种真实数据上表现良好。

它基于一个简单的事实,实际中大部分数据都是部分有序(升序或降序)的。

它于 2002 年由 Tim Peters 在 Python 编程语言实现。

Timsort 排序算法中定义数组中的有序片段为 run,每个 run 都要求单调递增或严格单调递减(保证算法的稳定性),如下图:

文中图片都是我手绘的,字写的难看了点,将就看吧~

Timsort 排序算法可以概括成两步:

  1. 把待排序数组分成一个个的 run(即单调上升的数组), 并且 run 不能太短, 如果 run 的长度小于 minRun 这个阀值, 则使用插入排序进行填充

  2. 将上面的一个个 run 入栈, 当栈顶的 run 的长度不满足下列约束条件中的任意一个时,则使用归并排序将其中最短的 2 个 run 合并成一个新的 run,最终栈 = 1 的时候,排序完成。

  ① runLen[n-2] > runLen[n-1] + runLen[n]

  ② runLen[n-1] > runLen[n]

下面用一个例子进行说明,假设 minRun=5,也就是说 run 的最小长度不能小于 5,如果小于 5 则使用插入排序进行填充。每划分出一个 run 就将其入栈,如下图所示:

注意:此时栈顶的 run 是不满足约束条件的,因为此时 runLen[0] < runLen[1],所以要对这两个 run 进行归并,这个过程使用的是归并排序。

如果遇到 run 的长度小于 minRun 的情况,则需要进行填充,直到 run 的长度 = minRun 或者数组结束为止,如下图:

至此排序完成~~~ 有的同学可能会有疑问,为什么要有那个奇怪的约束条件呢?每次入栈的时候直接进行归并不行吗?这主要是考虑到归并排序的效率问题,

因为将一个长序列和一个短序列进行归并排序从效率和代价的角度来看是不划算的,而两个长度均衡的序列进行归并排序时才是比较合理的也比较高效的。

这里只是简单的阐述了一下 TimSort 的思想原理,具体实现还是有很多细节需要考虑的

Timsort排序图解


图片出处:https://www.sakuratears.top/blog/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%EF%BC%88%E5%85%AD%EF%BC%89-TimSort.html

最后来一张归并排序的动态图片: