![cover](https://img-blog.csdnimg.cn/2d44299b0d184012a92473e2fbf0bae3.png)
TimSort——最快的排序算法
TimSort 算法是 Tim Peters 于 2001 年为 Python 语言创建的。该算法建立在插入排序和归并排序的基础之上,兼具插入排序和归并排序的优点。TimSort 的平均时间复杂度为 O(nlog(n)) ,最好情况 O(n) ,最差情况 O(nlog(n)) 。空间复杂度 O(n) ,是一个稳定的排序算法。
TimSort——最快的排序算法
排序算法是每个程序员绕不开的课题,无论是大学课程还是日常工作,都离不开排序算法。常见的排序算法有:冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、基数排序等。下面是这些算法性能的概览:
算法 | 平均时间复杂度 | 最好情况 | 最差情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
冒泡排序 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | in-place | 稳定 |
选择排序 | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | in-place | 不稳定 |
插入排序 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | in-place | 稳定 |
希尔排序 | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | in-place | 不稳定 |
归并排序 | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( n ) O(n) O(n) | out-place | 稳定 |
快速排序 | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | in-place | 不稳定 |
堆排序 | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( 1 ) O(1) O(1) | in-place | 不稳定 |
计数排序 | O ( n + k ) O(n+k) O(n+k) | O ( n + k ) O(n+k) O(n+k) | O ( n + k ) O(n+k) O(n+k) | O ( k ) O(k) O(k) | out-place | 稳定 |
桶排序 | O ( n + k ) O(n+k) O(n+k) | O ( n + k ) O(n+k) O(n+k) | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | out-place | 稳定 |
基数排序 | O ( n k ) O(nk) O(nk) | O ( n k ) O(nk) O(nk) | O ( n k ) O(nk) O(nk) | O ( n + k ) O(n+k) O(n+k) | out-place | 稳定 |
上述算法中,我们日常用的最多的可能是快速排序和堆排序,这两个算法都是性能很高的排序算法,缺点是不稳定。今天要介绍的 TimSort 算法性能比快速排序和堆排序还高,且是稳定排序算法。
TimSort 简介
TimSort 算法是 Tim Peters (就是写 Python 之禅 的那个大神) 于 2001 年为 Python 语言创建的。该算法建立在插入排序和归并排序的基础之上,兼具插入排序和归并排序的优点。
TimSort 的平均时间复杂度为 O ( n log n ) O(n\log n) O(nlogn) ,最好情况 O ( n ) O(n) O(n) ,最差情况 O ( n log n ) O(n\log n) O(nlogn) 。空间复杂度 O ( n ) O(n) O(n) ,是一个稳定的排序算法。
算法 | 平均时间复杂度 | 最好情况 | 最差情况 | 空间复杂度 | 排序方式 | 稳定性 |
---|---|---|---|---|---|---|
快速排序 | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) | in-place | 不稳定 |
堆排序 | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( 1 ) O(1) O(1) | in-place | 不稳定 |
归并排序 | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( n log n ) O(n\log n) O(nlogn) | O ( n ) O(n) O(n) | out-place | 稳定 |
TimSort | O ( n log n ) O(n\log n) O(nlogn) | O ( n ) O(n) O(n) | O ( n log n ) O(n\log n) O(nlogn) | O ( n ) O(n) O(n) | out-place | 稳定 |
自该算法被发明以来,已被 Python、Java、Android 平台和 GNU Octave 用作默认排序算法。Java 中的 Arrays.sort()
,Python 中的 sort()
和 sorted()
背后用的都是 TimSort。
TimSort 原理
TimSort 的排序思想并不复杂,首先使用插入排序对小块进行排序,然后使用归并排序合并这些块。
TimSort 会将数组(列表)分成名为 Run 的小块。首先使用插入排序对这些 run 块进行排序,然后使用归并排序中的 combine
函数合并这些 run 块。如果数组的大小小于 run 块的大小,则仅使用插入排序对数组进行排序。run 块的大小可能从 32 到 64 不等,具体取决于数组的大小。请注意,子数组的大小尽量是 2 的幂,这样 merge
函数性能表现会更好。
以下是对 TimSort 算法的逐步解释:
- 使用插入排序将输入数组分成小的 run块。每个 run 块都为递增顺序。
- 然后使用改进的归并排序算法合并 run 块。合并步骤的工作原理是比较 每个run 块的第一个元素,并将最小的元素添加到输出数组。该过程一直持续到所有元素都添加到输出数组。
- 如果 run 块不是良构的,即有些不是按升序排列的,那么它们将合并在一起直到它们为良构的。
- run 块的大小在每次迭代中增加两倍,直到整个数组排序完成。
TimSort 的想法是基于插入排序对小数组表现良好的事实,因此在最好情况下可以获得插入排序 O ( n ) O(n) O(n) 的最好性能。同时又能获得归并排序最差 O ( n log n ) O(n\log n) O(nlogn) 的性能表现。
TimSort 详解
小数组用插入排序
正如前面 TimSort 算法原理讲到的,如果数组比较小(通常是小于 2 6 = 64 2^6=64 26=64),那么 TimSort 会直接采用插入排序对数组进行排序。
这是因为插入排序作为一种简单的排序算法,对小列表最有效。它在较大的列表中非常慢,但在小列表中非常快。 插入排序的思想如下:
- 逐个扫一遍数组元素
- 通过在正确位置插入元素来构建排序数组
插入排序相信大家都学过,原理也比较简单,这里不做过多赘述。下面这一张动图很好的演示了插入排序的过程。
Run 块
如果列表比较大,则算法会先遍历列表,查找严格递增或递减的部分。如果该部分是递减的,则将其反转成递增的。
举个例子,假如数组元素是 [ 3 , 2 , 1 , 9 , 17 , 34 ] [3, 2, 1, 9, 17, 34] [3,2,1,9,17,34],遍历发现前3个元素是递减的,则 run 块会将其变为递增的,即 [ 1 , 2 , 3 , 9 , 17 , 34 ] [\bold{1,2,3},9,17,34] [1,2,3,9,17,34]。
当 run 块的数量等于或略小于 2 的幂时,合并 2 个数组的效率会更高。Timsort 通过确保 minrun
等于或小于 2 的幂来保证合并的效率。 minrun
的取值范围一般在 32 到 64 之间(含)。选定的 minrun
值要确保原始数组的长度除以 minrun
后等于或略小于 2 的幂。
如果 run 块的长度小于 minrun
,则计算该 run 块长度与 minrun
的偏离,看看 run 块还差多少元素并执行插入排序以创建新 run 块。
这部分完成后,我们得到一堆排序好的 run 块。
归并
这一步,Timsort 执行归并排序将 run 块合并在一起。这里,Timsort 需要确保在归并排序时保持稳定性和合并平衡。
为了保持稳定性,算法就不应该交换 2 个等值的数。这不仅保留了它们在列表中的原始位置,而且使算法更快。
当 Timsort 发现 run 块时,会将它们添加到栈中。栈是先进后出的。
Timsort 试图在归并排序 run 块时平衡两种相互竞争的需求。一方面,我们希望尽可能地延迟合并,以便利用稍后可能出现的模式。但我们更希望尽快进行合并,以利用刚刚发现的处于栈顶的 run 块,因此我们也不能将合并延迟“太久”,因为它会消耗更多内存来记住仍未合并的 run 块,并且栈的大小是有限的。
为了找到最优折中方案,Timsort 会跟踪栈中最近的三个项并规定如下 2 个法则:
- A > B + C A \gt B+C A>B+C
- B > C B \gt C B>C
其中 A , B , C A,B,C A,B,C 是栈中最近的三个项。用 Tim Peters 的原话说:
结果证明这是一个很好的折衷方案,在栈顶维护两个不变量,其中 A、B 和 C 是三个最右边尚未合并的切片的长度。
通常,将不同长度的相邻 run 块合并到位是很困难的。更难的是我们必须保持稳定。为了解决这个问题,Timsort 预留了临时内存。它将两个 run 块中较小的(同时调用 run A 和 run B)放入该临时内存中。
算法实现
下面给出 TimSort 的 Python 实现。
TimSort 依赖于插入排序和归并排序,我们首先实现这 2 种排序。
# insertionSort函数用插入排序从left到right排序数组arr
def insertionSort(arr, left, right):
for i in range(left + 1, right + 1):
j = i
while j > left and arr[j] < arr[j - 1]:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
j -= 1
# merge函数合并排序好的run块
def merge(arr, l, m, r):
# 原数组一分为二:左数组和右数组
len1, len2 = m - l + 1, r - m
left, right = [], []
for i in range(0, len1):
left.append(arr[l + i])
for i in range(0, len2):
right.append(arr[m + 1 + i])
i, j, k = 0, 0, l
# 比较后将两个数组合并成一个更大的数组
while i < len1 and j < len2:
if left[i] <= right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
# 复制左数组遗留元素
while i < len1:
arr[k] = left[i]
k += 1
i += 1
# 复制右数组遗留元素
while j < len2:
arr[k] = right[j]
k += 1
j += 1
计算 run 块的最小值,确保归并可以高效运行
MIN_MERGE = 32
# 计算run块的最小长度
def calcMinRun(n):
r = 0
while n >= MIN_MERGE:
r |= n & 1
n >>= 1
return n + r
TimSort过程
# TimSort排序
def timSort(arr):
n = len(arr)
minRun = calcMinRun(n)
# 对大小为 RUN 的单个子数组进行排序
for start in range(0, n, minRun):
end = min(start + minRun - 1, n - 1)
insertionSort(arr, start, end)
# 从大小 RUN(或 32)开始合并。最终合并形成大小为2^n
size = minRun
while size < n:
# 选择左子数组的起点。
# 合并 arr[left..left+size-1] 和 arr[left+size, left+2*size-1]
# 每次合并后,left 增加 2*size
for left in range(0, n, 2 * size):
# 查找左子数组的终点
# mid+1 为右子数组的起点
mid = min(n - 1, left + size - 1)
right = min((left + 2 * size - 1), (n - 1))
# 合并子数组 arr[left.....mid] & arr[mid+1....right]
if mid < right:
merge(arr, left, mid, right)
size = 2 * size
if __name__ == "__main__":
arr = [-2, 7, 15, -14, 0, 15, 0,
7, -7, -4, -13, 5, 8, -14, 12]
print("排序前")
print(arr)
timSort(arr)
print("排序后")
print(arr)
输出:
排序前
-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12
排序后
-14 -14 -13 -7 -4 -2 0 0 5 7 7 8 12 15 15
总结
Timsort 实际上已经内置于 Python 中,上面给出的代码实现仅作为演示用。
在 Python 要使用 Timsort,只需 list.sort()
或 sorted(list)
即可。
如果你想掌握 Timsort 的工作原理,我强烈建议你尝试自己实现一遍!
![Logo](https://devpress.csdnimg.cn/79de2bf0b7994defa4242ef90d5513fa.jpg)
开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!
更多推荐
所有评论(0)