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 原理TimSort 详解小数组用插入排序Run 块归并
算法实现总结
TimSort 简介
TimSort 算法是 Tim Peters （就是写 Python 之禅 的那个大神） 于 2001 年为 Python 语言创建的。该算法建立在插入排序和归并排序的基础之上，兼具插入排序和归并排序的优点。
图1. Tim Peters，就是这位大神开创了 TimSort
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 会直接采用插入排序对数组进行排序。
这是因为插入排序作为一种简单的排序算法，对小列表最有效。它在较大的列表中非常慢，但在小列表中非常快。 插入排序的思想如下：
逐个扫一遍数组元素通过在正确位置插入元素来构建排序数组
插入排序相信大家都学过，原理也比较简单，这里不做过多赘述。下面这一张动图很好的演示了插入排序的过程。
图2. 插入排序过程演示
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 的工作原理，我强烈建议你尝试自己实现一遍！
文章来源
发表评论