C++ Timsort算法的实现

Timsort算法采用了两种著名的排序技术，插入排序和归并排序算法。

Timsort的实现非常简单，我们将整个输入数组分割成我们称之为“runs”的块。这些runs的创建是为了更容易实现这两种排序技术。使用插入排序算法对runs进行排序。排序后，使用归并排序中可用的组合函数将它们合并起来。

C++代码

//Here, we are writing down the C++ programming language code to demonstrate
//the concept of Timsort Implementation Using C++ with its output
#include
using namespace std;
const int RUN = 32;

// This function sorts the array from the left index to
// to the right index, which is of size almost RUN
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;
    }
}


// this is the function we are writing to merge the sorted RUNS
void merge(int arr[], int l, int m, int r)
{


    // the original array, which is like the input to our code
// is broken into left and right arrays (two parts easy for comparison)
    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;



    // once the comparison part is done, we have to merge the two arrays
    // into a single large sub-array
    while (i < len1 && j < len2)
    {
        if (left[i] <= right[j])
        {
            arr[k] = left[i];
            i++;
        }
        else
        {
            arr[k] = right[j];
            j++;
        }
        k++;
    }


    // the below while loop copies the elements which are present to the 
    // left (if any)
    while (i < len1)
    {
        arr[k] = left[i];
        k++;
        i++;
    }

    // the below while loop copies the elements which are present to the 
    // right (if any)
    while (j < len2)
    {
        arr[k] = right[j];
        k++;
        j++;
    }
}


// below function code snippet implements the timsort algorithm
//, a combination of both insertion and merge sort algos.
void tim_Sort_(int arr[], int n)
{

    // Sort individual subarrays of size RUN
    // below for loop which we have created sorts the sub-arrays which are
    // made individually of the size RUN
    for (int i = 0; i < n; i+=RUN)
        insertionSort(arr, i, min((i+RUN-1),
                                    (n-1)));



    // the runs which we have created from size 32 will merge to form
    // the size of nearly 64 to 128 and 256, and it goes on ...
    for (int size = RUN; size < n;
                            size = 2*size)
    {

        // picking the starting of the left sub-array
        // then it will be increased by two (*2)
        for (int left = 0; left < n;
                            left += 2*size)
        {


            // below are small code snippets to help us with 
            // rearrangement of the left and right sub-array indices from 
            // starting and ending
            int mid = left + size - 1;
            int right = min((left + 2*size - 1),
                                            (n-1));


            // below code helps us with the recombining of the runs using
            // the merge sort functionality
            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