Tim 排序
Tim 排序是一种混合稳定排序算法。它是由插入排序和合并排序衍生出来的混合算法。它首先使用插入排序进行子数组，这些小的排序子数组被称为自然运行。然后使用合并排序对这些运行进行合并子数组，产生最终的排序数组。它的设计考虑到算法在真实世界数据上的最佳性能。它利用了插入排序在小尺寸子数组上表现非常好的事实。它是 Java 的 Array.sort() 和 Python 的 sorted() 和 sort() 使用的标准排序算法。
Tim 排序算法
假设我们有一个包含 n 元素的无序数组 A[]。我们将考虑运行的大小为 32。它可以是 2 的任何幂数，因为当数字是 2 的幂数时，合并更有效。
TimSort()
-
将数组划分为
n/32运行。 -
使用插入排序函数对各个运行逐一进行排序。
-
使用合并排序的
merge函数将排序后的运行逐一合并。
Merge()
-
初始化辅助数组
output来存储排序后的输出。 -
初始化 3 个指针
i、j和k。i指向第一个子数组beg的开始。
j指向第二个子数组mid+1的开始。
k用beg初始化，保持排序数组output的当前索引。 -
直到到达
arr[beg, .... ,mid]或arr[mid+1, .... ,end]子数组的末尾，我们在索引i&j的元素中挑出一个较小的值，插入到output中。 -
当其中一个数组用完后，挑选剩余的元素插入
output中。 -
将
output复制到arr[beg, ... , end]中。
Tim 排序实例
假设我们有数组：(3, 5, 2, 8, 1, 7, 6, 4)。我们将使用 Tim 排序算法对其进行排序。为了保持说明的简单性，让我们考虑运行的大小为 4。
将数组划分为两个子数组。(3, 5, 2, 8) 和 (1, 7, 6, 4)。
第一个子数组：(3, 5, 2, 8)
| 排序子数组 | 未排序子数组 | 数组 |
|---|---|---|
| (3) | (5, 2, 8) | (3,5,2,8) |
- 第一次迭代
键：A[1]=5
| 排序子数组 | 未排序子数组 | 数组 |
|---|---|---|
| ( 3 , 5) | (2, 8) | (3, 5, 2, 8) |
- 第二次迭代
键：A[2]=4
| 排序子数组 | 未排序子数组 | 数组 |
|---|---|---|
| ( 2, 3, 5) | (8) | (2, 3, 5, 8) |
- 第三次迭代
键：A[3]=2
| 排序子数组 | 未排序子数组 | 数组 |
|---|---|---|
| ( 2, 3, 5, 8) | () | (2, 3, 5, 8) |
第二个子数组：(1,7,6,4)。
| 排序子数组 | 未排序子数组 | 数组 |
|---|---|---|
| (1) | (7, 6, 4) | (1, 7, 6, 4) |
- 第一次迭代
键：A[1]=7
| 排序子数组 | 未排序子数组 | 数组 |
|---|---|---|
| ( 1 , 7) | (6, 4) | (1, 7, 6, 4) |
- 第二次迭代
键：A[2]=6
| 排序子数组 | 未排序子数组 | 数组 |
|---|---|---|
| ( 1, 6, 7) | (4) | (1, 6, 7, 4) |
- 第三次迭代
键：A[3]=4
| 排序子数组 | 未排序子数组 | 数组 |
|---|---|---|
| ( 1, 4, 6, 7) | () | (1, 4, 6, 7) |
合并两个排序的子数组，得到最终的子数组为：(1, 2, 3, 4, 5, 6, 7, 8)。
Tim 排序算法的实现
#include <bits/stdc++.h>
using namespace std;
const int RUN = 32;
void insertionSort(int arr[], int left, int right) {
for (int i = left + 1; i <= right; i++) {
int temp = arr[i];
int j = i - 1;
while (j >= left && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
void merge(int arr[], int beg, int mid, int end) {
int output[end - beg + 1];
int i = beg, j = mid + 1, k = 0;
// add smaller of both elements to the output
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
output[k] = arr[i];
k += 1;
i += 1;
} else {
output[k] = arr[j];
k += 1;
j += 1;
}
}
// remaining elements from first array
while (i <= mid) {
output[k] = arr[i];
k += 1;
i += 1;
}
// remaining elements from the second array
while (j <= end) {
output[k] = arr[j];
k += 1;
j += 1;
}
// copy output to the original array
for (i = beg; i <= end; i += 1) {
arr[i] = output[i - beg];
}
}
void timSort(int arr[], int n) {
for (int i = 0; i < n; i += RUN)
insertionSort(arr, i, min((i + 31), (n - 1)));
for (int size = RUN; size < n; size = 2 * size) {
for (int left = 0; left < n; left += 2 * size) {
int mid = left + size - 1;
int right = min((left + 2 * size - 1), (n - 1));
merge(arr, left, mid, right);
}
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
timSort(arr, n); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
Tim 排序算法复杂度
时间复杂度
- 平均情况
该算法需要进行 O(nlogn) 比较，以对 n 元素的数组进行排序。因此，时间复杂度为 [Big Theta]：O(nlogn)。
- 最坏情况
在最坏的情况下，需要进行 nlogn 比较。最坏情况下的时间复杂度为 [Big O]：O(nlogn). 它与平均情况下的时间复杂度相同。
- 最佳情况
最好的情况是数组已经排序，不需要交换。最佳情况下的时间复杂度是 [Big Omega]：O(n)。
空间复杂度
该算法的空间复杂度为 O(n)，因为合并排序算法需要额外的辅助空间 O(n)。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn