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