跳转至

tim排序

tim 排序是归并排序和插入排序的结合,是一个 稳定 的排序算法,由 Tim Peters 于 2002 年用 Python 实现。现在,tim 排序是 Python 的标准排序算法,且被 Java SE7 用于对非原始类型的数组排序。

tim 排序在最好情况下的时间复杂度为 \(O(n)\),最差情况下的时间复杂度为 \(O(n \log n)\),期望时间复杂度为 \(O(n \log n)\)。tim 排序在最坏情况下的空间复杂度为 \(O(n)\)

算法

众所周知,归并排序是先将数组划分为两部分,然后递归地对两个子数组进行归并排序,最后合并两个子数组。这样一来,归并排序合并操作的最小单位就是单个元素。但是,数组中可能原本就存在连续且有序的子数组,归并排序无法利用这个特性。

tim 排序为了利用数组中本身就存在的连续且有序的子数组,以 RUN 作为合并操作的最小单位。其中,RUN 是一个满足以下性质的子数组:

  • 一个 RUN 要么是非降序的,要么是严格升序的。
  • 一个 RUN 存在一个长度的下限。

tim 排序的过程就是一个类似归并排序的过程,将数组划分为多个 RUN,然后以某种规则不断地合并两个 RUN,直到数组有序。具体过程如下:

\(nRemaining\) 初始化为数组的大小,\(minRun\) 初始化为 \(getMinRunLength(nRemaining)\)

\[ \begin{array}{ll} 1 & \textbf{do}\\ 2 & \qquad \text{确定} run \text{的起点}\\ 3 & \qquad \textbf{if} run \text{比} minRun \text{短}\\ 4 & \qquad \qquad \text{延长} run \text{直至} \min(minRun, nRemaining)\\ 5 & \qquad \textbf{push} run \text{放到} pending-run stack \text{上}\\ 6 & \qquad \textbf{if} pending-run stack \text{最顶上的 2 个} run \text{长度相近}\\ 7 & \qquad \qquad \text{合并} pending-run stack \text{最顶上的 2 个} run\\ 8 & \qquad \text{start index} \gets \text{start index} + run \text{的长度}\\ 9 & \qquad nRemaining \gets nRemaining - run \text{的长度}\\ 10 & \textbf{while} \text{ } nRemaining \ne 0\\ \end{array} \]

其中,\(getMinRunLength\) 函数是根据当前数组长度确定 \(minRun\) 具体值的函数,natural run 的意思是原本就非降序或者严格升序的 run,扩展长度不够的 run 就是用插入排序往 run 中添加元素。

复杂度证明

最好情况下,数组本身就有序,即数组本身就是一个 RUN,这个时候 tim 排序就遍历了一遍数组,找到了唯一的 RUN,就结束了。所以,最好的情况下,tim 排序的时间复杂度为 \(O(n)\)

写在后面

本文只是简单介绍了 tim 排序的原理,实际上 tim 排序在实现的时候还有一些其他的优化,这里不再一一列举。tim 排序在 java 中的实现写得非常好,要想知道真正的 tim 排序推荐去看 java 中 tim 排序的实现。

参考资料

  1. Timsort
  2. On the Worst-Case Complexity of TimSort
  3. original explanation by Tim Peters
  4. java 实现
  5. c 语言实现