写点什么

Timsort - 混合、稳定、高效的排序算法

作者:kenny
  • 2021 年 12 月 26 日
  • 本文字数:2142 字

    阅读完需:约 7 分钟

Timsort - 混合、稳定、高效的排序算法

2002 年,Tim Peters 开发了 Timsort 排序算法。它巧妙地结合了合并排序和插入排序的思想,并且设计得能很好地处理现实世界中的数据。TimSort 最初在 Python 开发的,但后来移植到了 Java (在 Java 中它以 java.util.Collections.sort 和 java.util.Arrays.sort 的形式出现) ,现在已经成为 Android SDK、 Sun 的 JDK 和 OpenJDK 的默认排序算法。


它是一种自适应、混合的、稳定 排序算法


Timsort 基于

  • 插入排序(折半插入)

  • 归并排序(分治思想, 分治法将问题(divide)成一些小的问题然后递归求解,而(conquer)的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)


Timsort 定义

  • N : 数组长度。

  • run:将数组通过一个算法划分成一个个子数组 (切割出来的 run 是严格升序或严格降序的)。

  • minrun: 子数组最小的长度。


Timsort 原理

它的整体思路是这样的:

  1. 遍历数组,将数组分为若干个升序或降序的片段,(如果是降序片段,反转降序的片段使其变为升序),每个片段称为一个 Run

  2. 从数组中取一个 Run,将这个 Run 压栈。

  3. 取出栈中相邻两个的 Run,做归并排序,并将结果重新压栈。

  4. 重复(2),(3)过程,直到所有数据处理完毕。


时间复杂度和空间复杂度


Timsort 的平均排序时间与 MergeSort 相同,因此它比大多数的算法都要快。

Timsort 的作者 Tim Peters 认为在大多数情况下,我们给定的数组通常都是部分已经排好序的(严格单调递增或严格单调递减)。


Timsort 执行条件?

在 Python 中,如果待排序元素的个数少于 64 个,则 Timsort 将执行插入排序。而在 JDK 的版本中则是 32 个。


JDK1.8


步骤一:切割 Run

  1. 根据 N 计算 MinRun 的长度



private static int minRunLength(int n) { assert n >= 0; int r = 0; // Becomes 1 if any 1 bits are shifted off while (n >= MIN_MERGE) { r |= (n & 1); // n >>= 1; } return n + r;}
复制代码


让我们来看看 minrun 是如何选择的,通过代码我们可以看出,

1) n & 1 判断 n 是否为偶数,返回 0 则是偶数,返回 1 则是奇数。

2) r = 0, 当偶数的情况下,0 = (n & 1) , 奇数时,1 = (n & 1)。 |运算保证只要其中一个的某一位 3)为 1,则结果的该位就为 1。

4) n >> 1 效果等同于 n / 2

n = 奇数,return (n-1) / 2 + 1。n = 偶数,return n / 2

假设 n 是 32,所以 minrun 的长度则是 16,而如果 n<32,则根本不会使用 Timsort。


通常,minrun 的取值不适合太长(影响插入排序效率),也不适合太小(归并排序的次数增多), 在理想的情况,2 的幂次方或者接近 2 的幂次方在归并排序时的效率是最好的。(Timsort 作者通过实验认为 32 - 64 之间是最好的)


  1. 从 Array[i] 扫描到 Array[N - 1] , 将原本严格单调递减的序列反转为单调递增的序列。

[1, 10, 9, 8, 2, 2, 5, 3, 6, 4, 7]

[1, 10, 2, 8, 9, 2, 3, 5, 4, 6, 7] 第六个 2 并没有翻转,因为它没有序列


此时,假设 minrun 的长度为 4

[1, 10] 还差两个元素,所以通过插入排序(折半)将后面的 2,8 插入进来,所以 run 1 就变成了

[1, 2, 8, 10]


run 2 还剩下一个 9, 长度也不满足 4, 所以,将后面 2,3,5 的插入进来,变成了

[2, 3, 5, 9]


还剩下一个 run 3

[4, 5, 7]


最终 run1、run2、run3 成了这个样子

[1, 2, 8, 10] [2, 3, 5, 9] [4, 5, 7]


不断重复步骤并将 run push 到栈中。

步骤二:合并

在这一步,我们将合并两个连续的 run。这个合并操作需要有一个临时数组来完成操作。


比方说 [1, 2, 2, 3, 5, 8, 9, 10] 和 [4, 5, 7, 11, 20, 35]这个例子。(run1 and run2)

  1. 两个 run 中长度最小作为临时数组的长度,并将这个较小的 run 复制到临时数组里(后续操作中 run2 的数组会被覆盖)。

取 run1 的第一个元素 run1[base1],剩余元素数量为 len1, 和 run2 的第一个元素下标 run2[base2]

将 run2[base2]的元素 4 在 run1 数组中做二分查找,将 run1 数组中小于等于 run2[base2]的元素作为起始点,也就是 3。将 run1[base1 + len1 – 1]的元素 9,在 run2 中进行二分查找,大于等于 run1[base1 + len1 – 1]值的段作为结果的结束部分。

该例子中为元素 11 所在的下标。目的是为了[1, 2, 2, 3, 5, 8, 9, 10], [4, 5, 7, 11, 20, 35]之间的元素。

  1. 创建一个临时数组,将 run2 剩余的数组拷贝进去。

  2. 将临时 run 和较大的 run 的标记段元素标记为起始位置。

  3. 比较两个起始位置的元素的大小,将较小的一个移到目标数组,然后将起始位置移回。

  4. 重复步骤 4,直到其中一个数组的元素全部取完。

  5. 将未取完的 run 中剩余的所有元素添加到目标数组的末尾。


Timsort 的合并平衡性

为了保证 Timsort 的合并平衡性,Tim 制定一个合并规则,对于在栈顶的三个run,用XYZ分别表示他们的长度,其中X在栈顶,必须始终维持一下的两个规则:


  • Z >Y + X

  • Y > X


一旦有其中的一个条件不被满足,Y这个子序列就会和XZ中较小的元素合并形成一个新run,然后会再次检查栈顶的三个run看看是否仍然满足条件。如果不满足则会继续进行合并,直至栈顶的三个元素(如果只有两个run就只需要满足第二个条件)满足这两个条件。




感兴趣可以进一步了解

galloping mode


如果本文有错误的地方,欢迎指出!

https://dev.to/brandonskerritt/timsort-the-fastest-sorting-algorithm-you-ve-never-heard-of-2ake

https://awdesh.medium.com/timsort-fastest-sorting-algorithm-for-real-world-problems-1d194f36170e

https://cloud.tencent.com/developer/article/1518016

发布于: 3 小时前
用户头像

kenny

关注

还未添加个人签名 2020.08.26 加入

还未添加个人简介

评论

发布
暂无评论
Timsort