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