Timsort：最快排序算法

Timsort（泰姆排序）是一种混合排序算法，结合了合并排序（Merge Sort）和插入排序（Insertion Sort）的特性。它由Tim Peters在2002年为Python的排序算法而设计，并在Python 2.3版本中首次实现。

Tim Sort 是Python 的sorted()和list.sort()函数使用的默认排序算法。

自从该算法被发明以来，它已被用作Python、Java、Android平台和GNU Octave中的默认排序算法。Java中使用Java的标准库（java.util.Arrays类）来使用Timsort。

import java.util.Arrays;

public class TimsortExample {
    public static void main(String[] args) {
        // 示例数据
        int[] array = {5, 2, 9, 1, 5, 6};
        
        // 使用Arrays.sort()方法，底层使用Timsort
        Arrays.sort(array);
        
        // 打印排序后的结果
        System.out.println("Sorted Array: " + Arrays.toString(array));
    }
}

这个简单的示例演示了如何使用Java的Arrays.sort()方法对一个整数数组进行排序。在实际应用中，你可以用类似的方式对其他类型的数组或对象数组进行排序。

请注意，Java的Arrays.sort()方法使用了Timsort的实现，因此你不需要自己实现Timsort算法，除非你有特殊的需求。

Timsort：一种非常快速、O(n log n)、稳定的排序算法，专为现实世界构建，而不是在学术界构建。

Timsort的设计目的是克服其他排序算法在特定情况下的性能缺陷。它在实际应用中表现良好，尤其在处理有序数据或包含小规模子数组的数据时效果显著。

Timsort的主要思想是利用现实世界数据的一些特性，例如数据通常部分有序。它采用分而治之的策略，首先将数据分割成小的块，然后对这些块进行排序，最后再将这些有序块合并起来。该算法具有线性对数时间复杂度（O(n log n)），并且在最坏情况下的性能也比较好。

蒂姆排序算法
Tim Sort 背后的主要思想是利用数据中现有的顺序来最大限度地减少比较和交换的次数。它通过将数组划分为已排序的称为运行的小子数组，然后使用修改后的合并排序算法合并这些运行来实现此目的。

以下面的数组为例：arr[] = {4, 2, 8, 6, 1, 5, 9, 3, 7}。

步骤 1：定义运行的大小

最小运行规模：32（由于我们的数组较小，因此忽略这一步）

步骤 2：将阵列划分为运行

在这一步中，我们将使用插入排序对数组中的小子序列（运行）进行排序。
初始数组[4, 2, 8, 6, 1, 5, 9, 3, 7]
没有初始运行，因此我们将使用插入排序创建运行。
排序后的运行[2, 4], [6, 8], [1, 5, 9], [3, 7]
更新数组：[2, 4, 6, 8, 1, 5, 9, 3, 7]

步骤 3：合并运行

在这一步中，我们将使用修改后的合并排序算法合并已排序的运行。
合并运行，直到整个数组排序完毕。
合并运行[2, 4, 6, 8], [1, 3, 5, 7, 9]
更新后的数组：[2, 4, 6, 8, 1, 3, 5, 7, 9]

步骤 4：调整运行规模

每次合并操作后，我们都会将运行的大小加倍，直到超过数组的长度。
运行大小加倍：32、64、128（因为我们的数组很小，所以忽略这一步）

第 5 步：继续合并

重复合并过程，直到整个数组排序完毕。
最终合并的运行结果[1, 2, 3, 4, 5, 6, 7, 8, 9]
最终排序后的数组为 [1，2，3，4，5，6，7，8，9]。

下面是 TimSort 的实现：

// C++ program to perform TimSort. 
include <bits/stdc++.h> 
using namespace std; 
const int RUN = 32; 

// 该函数对数组进行排序，从左索引
// 索引排序到右索引，右索引是
// 最大的 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; 
    } 
} 

// 合并函数合并已排序的运行结果
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++; 
    } 

    // Copy remaining element of 
    // right, if any 
    while (j < len2) { 
        arr[k] = right[j]; 
        k++; 
        j++; 
    } 
} 

//迭代 Timsort 函数，用于对
// 数组[0...n-1]排序（类似于合并排序）
void timSort(int arr[], int n) 
{ 

    // 对大小为 RUN 的单个子数组进行排序
    for (int i = 0; i < n; i += RUN) 
        insertionSort(arr, i, min((i + RUN - 1), (n - 1))); 

    // 从 RUN（或 32）开始合并。
    // 它将合并
    // 形成大小为 64，然后是 128、256
    // 以此类推 ....
    for (int size = RUN; size < n; size = 2 * size) { 

        // 选择
        // 左侧子数组的起点。我们
        // 合并
        // arr[left...left+size-1] 和 arr[left+size, left+2*size-1] 合并。
        // 和 arr[left+size, left+2*size-1] 进行合并。
        // 每次合并后，我们
        // 将 left 增加 2*size
        for (int left = 0; left < n; left += 2 * size) { 

            //查找
            // 左侧子数组
            // mid+1 是右子数组的起点
            //右子数组的起点
            int mid = left + size - 1; 
            int right = min((left + 2 * size - 1), (n - 1)); 

            //合并子数组 arr[left.....mid] &
            // arr[mid+1....right]
            if (mid < right) 
                merge(arr, left, mid, right); 
        } 
    } 
} 

// Utility function to print the Array 
void printArray(int arr[], int n) 
{ 
    for (int i = 0; i < n; i++) 
        printf("%d ", arr[i]); 
    printf("\n"); 
} 

// Driver program to test above function 
int main() 
{ 
    int arr[] = { -2, 7, 15, -14, 0, 15, 0, 7, 
                -7, -4, -13, 5, 8, -14, 12 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    printf("Given Array is\n"); 
    printArray(arr, n); 

    // Function Call 
    timSort(arr, n); 

    printf("After Sorting Array is\n"); 
    printArray(arr, n); 
    return 0; 
}

Java程序：

// Java program to perform TimSort. 
class GFG { 

    static int MIN_MERGE = 32; 

    public static int minRunLength(int n) 
    { 
        assert n >= 0; 

        // Becomes 1 if any 1 bits are shifted off 
        int r = 0; 
        while (n >= MIN_MERGE) { 
            r |= (n & 1); 
            n >>= 1; 
        } 
        return n + r; 
    } 

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

    // Merge function merges the sorted runs 
    public static void merge(int[] arr, int l, int m, int r) 
    { 
        // Original array is broken in two parts 
        // left and right array 
        int len1 = m - l + 1, len2 = r - m; 
        int[] left = new int[len1]; 
        int[] right = new int[len2]; 
        for (int x = 0; x < len1; x++) { 
            left[x] = arr[l + x]; 
        } 
        for (int x = 0; x < len2; x++) { 
            right[x] = arr[m + 1 + x]; 
        } 

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

        // After comparing, we merge those two array 
        // in larger sub array 
        while (i < len1 && j < len2) { 
            if (left[i] <= right[j]) { 
                arr[k] = left[i]; 
                i++; 
            } 
            else { 
                arr[k] = right[j]; 
                j++; 
            } 
            k++; 
        } 

        // Copy remaining elements 
        // of left, if any 
        while (i < len1) { 
            arr[k] = left[i]; 
            k++; 
            i++; 
        } 

        // Copy remaining element 
        // of right, if any 
        while (j < len2) { 
            arr[k] = right[j]; 
            k++; 
            j++; 
        } 
    } 

    // Iterative Timsort function to sort the 
    // array[0...n-1] (similar to merge sort) 
    public static void timSort(int[] arr, int n) 
    { 
        int minRun = minRunLength(MIN_MERGE); 

        // Sort individual subarrays of size RUN 
        for (int i = 0; i < n; i += minRun) { 
            insertionSort( 
                arr, i, 
                Math.min((i + MIN_MERGE - 1), (n - 1))); 
        } 

        // Start merging from size 
        // RUN (or 32). It will 
        // merge to form size 64, 
        // then 128, 256 and so on 
        // .... 
        for (int size = minRun; size < n; size = 2 * size) { 

            // Pick starting point 
            // of left sub array. We 
            // are going to merge 
            // arr[left..left+size-1] 
            // and arr[left+size, left+2*size-1] 
            // After every merge, we 
            // increase left by 2*size 
            for (int left = 0; left < n; left += 2 * size) { 

                // Find ending point of left sub array 
                // mid+1 is starting point of right sub 
                // array 
                int mid = left + size - 1; 
                int right = Math.min((left + 2 * size - 1), 
                                    (n - 1)); 

                // Merge sub array arr[left.....mid] & 
                // arr[mid+1....right] 
                if (mid < right) 
                    merge(arr, left, mid, right); 
            } 
        } 
    } 

    // Utility function to print the Array 
    public static void printArray(int[] arr, int n) 
    { 
        for (int i = 0; i < n; i++) { 
            System.out.print(arr[i] + " "); 
        } 
        System.out.print("\n"); 
    } 

    // Driver code 
    public static void main(String[] args) 
    { 
        int[] arr = { -2, 7, 15, -14, 0, 15, 0, 7, 
                    -7, -4, -13, 5, 8, -14, 12 }; 
        int n = arr.length; 
        System.out.println("Given Array is"); 
        printArray(arr, n); 

        timSort(arr, n); 

        System.out.println("After Sorting Array is"); 
        printArray(arr, n); 
    } 
}

Python3

# Python3 program to perform basic timSort 
MIN_MERGE = 32


def calcMinRun(n): 
    """Returns the minimum length of a 
    run from 23 - 64 so that 
    the len(array)/minrun is less than or 
    equal to a power of 2. 

    e.g. 1=>1, ..., 63=>63, 64=>32, 65=>33, 
    ..., 127=>64, 128=>32, ... 
    """
    r = 0
    while n >= MIN_MERGE: 
        r |= n & 1
        n >>= 1
    return n + r 


# This function sorts array from left index to 
# to right index which is of size atmost RUN 
def insertionSort(arr, left, right): 
    for i in range(left + 1, right + 1): 
        j = i 
        while j > left and arr[j] < arr[j - 1]: 
            arr[j], arr[j - 1] = arr[j - 1], arr[j] 
            j -= 1


# Merge function merges the sorted runs 
def merge(arr, l, m, r): 

    # original array is broken in two parts 
    # left and right array 
    len1, len2 = m - l + 1, r - m 
    left, right = [], [] 
    for i in range(0, len1): 
        left.append(arr[l + i]) 
    for i in range(0, len2): 
        right.append(arr[m + 1 + i]) 

    i, j, k = 0, 0, l 

    # after comparing, we merge those two array 
    # in larger sub array 
    while i < len1 and j < len2: 
        if left[i] <= right[j]: 
            arr[k] = left[i] 
            i += 1

        else: 
            arr[k] = right[j] 
            j += 1

        k += 1

    # Copy remaining elements of left, if any 
    while i < len1: 
        arr[k] = left[i] 
        k += 1
        i += 1

    # Copy remaining element of right, if any 
    while j < len2: 
        arr[k] = right[j] 
        k += 1
        j += 1


# Iterative Timsort function to sort the 
# array[0...n-1] (similar to merge sort) 
def timSort(arr): 
    n = len(arr) 
    minRun = calcMinRun(n) 

    # Sort individual subarrays of size RUN 
    for start in range(0, n, minRun): 
        end = min(start + minRun - 1, n - 1) 
        insertionSort(arr, start, end) 

    # Start merging from size RUN (or 32). It will merge 
    # to form size 64, then 128, 256 and so on .... 
    size = minRun 
    while size < n: 

        # Pick starting point of left sub array. We 
        # are going to merge arr[left..left+size-1] 
        # and arr[left+size, left+2*size-1] 
        # After every merge, we increase left by 2*size 
        for left in range(0, n, 2 * size): 

            # Find ending point of left sub array 
            # mid+1 is starting point of right sub array 
            mid = min(n - 1, left + size - 1) 
            right = min((left + 2 * size - 1), (n - 1)) 

            # Merge sub array arr[left.....mid] & 
            # arr[mid+1....right] 
            if mid < right: 
                merge(arr, left, mid, right) 

        size = 2 * size 


# Driver program to test above function 
if __name__ == "__main__": 

    arr = [-2, 7, 15, -14, 0, 15, 0, 
        7, -7, -4, -13, 5, 8, -14, 12] 

    print("Given Array is") 
    print(arr) 

    # Function Call 
    timSort(arr) 

    print("After Sorting Array is") 
    print(arr)

C代码

// C# program to perform TimSort. 
using System; 

class GFG { 
    public const int RUN = 32; 

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

    // merge function merges the sorted runs 
    public static void merge(int[] arr, int l, int m, int r) 
    { 
        // original array is broken in two parts 
        // left and right array 
        int len1 = m - l + 1, len2 = r - m; 
        int[] left = new int[len1]; 
        int[] right = new int[len2]; 
        for (int x = 0; x < len1; x++) 
            left[x] = arr[l + x]; 
        for (int x = 0; x < len2; x++) 
            right[x] = arr[m + 1 + x]; 

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

        // After comparing, we merge those two array 
        // in larger sub array 
        while (i < len1 && j < len2) { 
            if (left[i] <= right[j]) { 
                arr[k] = left[i]; 
                i++; 
            } 
            else { 
                arr[k] = right[j]; 
                j++; 
            } 
            k++; 
        } 

        // Copy remaining elements 
        // of left, if any 
        while (i < len1) { 
            arr[k] = left[i]; 
            k++; 
            i++; 
        } 

        // Copy remaining element 
        // of right, if any 
        while (j < len2) { 
            arr[k] = right[j]; 
            k++; 
            j++; 
        } 
    } 

    // Iterative Timsort function to sort the 
    // array[0...n-1] (similar to merge sort) 
    public static void timSort(int[] arr, int n) 
    { 

        // Sort individual subarrays of size RUN 
        for (int i = 0; i < n; i += RUN) 
            insertionSort(arr, i, 
                        Math.Min((i + RUN - 1), (n - 1))); 

        // Start merging from size RUN (or 32). 
        // It will merge 
        // to form size 64, then 
        // 128, 256 and so on .... 
        for (int size = RUN; size < n; size = 2 * size) { 

            // Pick starting point of 
            // left sub array. We 
            // are going to merge 
            // arr[left..left+size-1] 
            // and arr[left+size, left+2*size-1] 
            // After every merge, we increase 
            // left by 2*size 
            for (int left = 0; left < n; left += 2 * size) { 

                // Find ending point of left sub array 
                // mid+1 is starting point of 
                // right sub array 
                int mid = left + size - 1; 
                int right = Math.Min((left + 2 * size - 1), 
                                    (n - 1)); 

                // Merge sub array arr[left.....mid] & 
                // arr[mid+1....right] 
                if (mid < right) 
                    merge(arr, left, mid, right); 
            } 
        } 
    } 

    // Utility function to print the Array 
    public static void printArray(int[] arr, int n) 
    { 
        for (int i = 0; i < n; i++) 
            Console.Write(arr[i] + " "); 
        Console.Write("\n"); 
    } 

    // Driver program to test above function 
    public static void Main() 
    { 
        int[] arr = { -2, 7, 15, -14, 0, 15, 0, 7, 
                    -7, -4, -13, 5, 8, -14, 12 }; 
        int n = arr.Length; 
        Console.Write("Given Array is\n"); 
        printArray(arr, n); 

        // Function Call 
        timSort(arr, n); 

        Console.Write("After Sorting Array is\n"); 
        printArray(arr, n); 
    } 
}

Javascript

<script> 

// Javascript program to perform TimSort. 
let MIN_MERGE = 32; 

function minRunLength(n) 
{ 
    
    // Becomes 1 if any 1 bits are shifted off 
    let r = 0; 
    while (n >= MIN_MERGE) 
    { 
        r |= (n & 1); 
        n >>= 1; 
    } 
    return n + r; 
} 

// This function sorts array from left index to 
// to right index which is of size atmost RUN 
function insertionSort(arr,left,right) 
{ 
    for(let i = left + 1; i <= right; i++) 
    { 
        let temp = arr[i]; 
        let j = i - 1; 
        
        while (j >= left && arr[j] > temp) 
        { 
            arr[j + 1] = arr[j]; 
            j--; 
        } 
        arr[j + 1] = temp; 
    } 
} 

// Merge function merges the sorted runs 
function merge(arr, l, m, r) 
{ 
    
    // Original array is broken in two parts 
    // left and right array 
    let len1 = m - l + 1, len2 = r - m; 
    let left = new Array(len1); 
    let right = new Array(len2); 
    for(let x = 0; x < len1; x++) 
    { 
        left[x] = arr[l + x]; 
    } 
    for(let x = 0; x < len2; x++) 
    { 
        right[x] = arr[m + 1 + x]; 
    } 

    let i = 0; 
    let j = 0; 
    let k = l; 

    // After comparing, we merge those two 
    // array in larger sub array 
    while (i < len1 && j < len2) 
    { 
        if (left[i] <= right[j]) 
        { 
            arr[k] = left[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = right[j]; 
            j++; 
        } 
        k++; 
    } 

    // Copy remaining elements 
    // of left, if any 
    while (i < len1) 
    { 
        arr[k] = left[i]; 
        k++; 
        i++; 
    } 

    // Copy remaining element 
    // of right, if any 
    while (j < len2) 
    { 
        arr[k] = right[j]; 
        k++; 
        j++; 
    } 
} 

// Iterative Timsort function to sort the 
// array[0...n-1] (similar to merge sort) 
function timSort(arr, n) 
{ 
    let minRun = minRunLength(MIN_MERGE); 
        
    // Sort individual subarrays of size RUN 
    for(let i = 0; i < n; i += minRun) 
    { 
        insertionSort(arr, i, Math.min( 
            (i + MIN_MERGE - 1), (n - 1))); 
    } 

    // Start merging from size 
    // RUN (or 32). It will 
    // merge to form size 64, 
    // then 128, 256 and so on 
    // .... 
    for(let size = minRun; size < n; size = 2 * size) 
    { 
        
        // Pick starting point 
        // of left sub array. We 
        // are going to merge 
        // arr[left..left+size-1] 
        // and arr[left+size, left+2*size-1] 
        // After every merge, we 
        // increase left by 2*size 
        for(let left = 0; left < n; 
                        left += 2 * size) 
        { 

            // Find ending point of left sub array 
            // mid+1 is starting point of right sub 
            // array 
            let mid = left + size - 1; 
            let right = Math.min((left + 2 * size - 1), 
                                    (n - 1)); 

            // Merge sub array arr[left.....mid] & 
            // arr[mid+1....right] 
            if(mid < right) 
                merge(arr, left, mid, right); 
        } 
    } 
} 

// Utility function to print the Array 
function printArray(arr,n) 
{ 
    for(let i = 0; i < n; i++) 
    { 
        document.write(arr[i] + " "); 
    } 
    document.write("<br>"); 
} 

// Driver code 
let arr = [ -2, 7, 15, -14, 0, 15, 0, 7, 
            -7, -4, -13, 5, 8, -14, 12 ]; 
let n = arr.length; 
document.write("Given Array is<br>"); 
printArray(arr, n); 
timSort(arr, n); 

document.write("After Sorting Array is<br>"); 
printArray(arr, n); 



</script>

Output
Given Array is
-2 7 15 -14 0 15 0 7 -7 -4 -13 5 8 -14 12
After Sorting Array is
-14 -14 -13 -7 -4 -2 0 0 5 7 7 8 12 15 15