tim排序


Author

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

tim 排序在最好情况下的时间复杂度为 ,最差情况下的时间复杂度为 ,期望时间复杂度为 。tim 排序在最坏情况下的空间复杂度为

算法

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

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

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

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

初始化为数组的大小, 初始化为

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

复杂度证明

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

写在后面

本文只是简单介绍了 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 语言实现

贡献者:@Great-designer

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组