Timsort 算法是使用两种著名的排序技术(插入和合并排序算法)实现的。

Timsort 的实现非常简单，我们将作为输入提供给数组划分为 run 的块块。创建这些运行是为了实现这两种排序技术变得更加容易。使用插入排序算法对运行进行排序。排序后，使用合并排序中可用的组合功能将它们组合在一起。

C++示例代码：

#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 l, int m, int r)  
{  

    int len1 = m - l + 1, len2 = r - m;  
    int left[len1], right[len2];  
    for (int i = 0; i < len1; i++)  
        left[i] = arr[l + i];  
    for (int i = 0; i < len2; i++)  
        right[i] = arr[m + 1 + i];  

    int i = 0;  
    int j = 0;  
    int k = l;  

    while (i < len1 && j < len2)  
    {  
        if (left[i] <= right[j])  
        {  
            arr[k] = left[i];  
            i++;  
        }  
        else  
        {  
            arr[k] = right[j];  
            j++;  
        }  
        k++;  
    }  

    while (i < len1)  
    {  
        arr[k] = left[i];  
        k++;  
        i++;  
    }  

    while (j < len2)  
    {  
        arr[k] = right[j];  
        k++;  
        j++;  
    }  
}  

void tim_Sort_(int arr[], int n)  
{  

    for (int i = 0; i < n; i+=RUN)  
        insertionSort(arr, i, min((i+RUN-1),(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));  

            if(mid < right)  
                merge(arr, left, mid, right);  
        }  
    }  
}  

// below function prints the array created  
void print_Array_(int arr[], int n)  
{  
    for (int i = 0; i < n; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
}  

// below, we are writing down the drive code for timsort  
int main()  
{  
    int arr[] = {-12, 17, 15, -14, 0, 15, 0, 17, -17,  
                    -14, -13, 15, 18, -14, 12};  
    int n = sizeof(arr)/sizeof(arr[0]);  
    printf("the given array as input is : \n");  
    print_Array_(arr, n);  

    // calling the timsort function to perform its task  
    tim_Sort_(arr, n);  

    printf("Array after implementing the sorting : \n");  
    print_Array_(arr, n);  
    return 0;  
}

运行结果：

the given array as input is : 
-12 17 15 -14 0 15 0 17 -17 -14 -13 15 18 -14 12 
Array after implementing the sorting : 
-17 -14 -14 -14 -13 -12 0 0 12 15 15 15 17 17 18

纠错/补充 收藏