Tim 排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. Tim 排序演算法
  2. Tim 排序例項
  3. Tim 排序演算法的實現
  4. Tim 排序演算法複雜度
Tim 排序
注意
如果你不知道什麼是插入排序和合並排序,請先看插入排序合併排序兩篇教程。

Tim 排序是一種混合穩定排序演算法。它是由插入排序和合並排序衍生出來的混合演算法。它首先使用插入排序進行子陣列,這些小的排序子陣列被稱為自然執行。然後使用合併排序對這些執行進行合併子陣列,產生最終的排序陣列。它的設計考慮到演算法在真實世界資料上的最佳效能。它利用了插入排序在小尺寸子陣列上表現非常好的事實。它是 Java 的 Array.sort() 和 Python 的 sorted()sort() 使用的標準排序演算法。

Tim 排序演算法

假設我們有一個包含 n 元素的無序陣列 A[]。我們將考慮執行的大小為 32。它可以是 2 的任何冪數,因為當數字是 2 的冪數時,合併更有效。

TimSort()

  • 將陣列劃分為 n/32 執行。
  • 使用插入排序函式對各個執行逐一進行排序。
  • 使用合併排序的 merge 函式將排序後的執行逐一合併。

Merge()

  • 初始化輔助陣列 output 來儲存排序後的輸出。
  • 初始化 3 個指標 ijk

    i 指向第一個子陣列 beg 的開始。
    j 指向第二個子陣列 mid+1 的開始。
    kbeg 初始化,保持排序陣列 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 avatar Harshit Jindal avatar

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

相關文章 - Sort Algorithm