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)
。
相关文章
将二叉树转换为二叉搜索树
发布时间:2023/03/20 浏览次数:159 分类:算法
-
本教程教大家如何将二叉树转换为二叉搜索树。二叉树是一种非线性数据结构。它被称为二叉树,因为每个节点最多有两个子节点。这些子节点被称为左子和右子。