跳到主要内容

TimSort

Tim排序​

代码​

C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define RUN 32

void insertion_sort(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)
        insertion_sort(arr, i, (i + RUN - 1) < (n - 1) ? (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) < (n - 1) ? (left + size - 1) : (n - 1);
            int right = (left + 2 * size - 1) < (n - 1) ? (left + 2 * size - 1) : (n - 1);

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

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Given array is \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");

    tim_sort(arr, n);

    printf("\nSorted array is \n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}

代码解释​

  1. 初始化：数组 arr 是待排序的数组，n 是数组的长度。
  2. 插入排序函数：
    • insertion_sort 函数用于对小块数组进行插入排序。
    • 从左到右遍历数组，将每个元素插入到已排序部分的正确位置。
  3. 合并函数：
    • merge 函数用于合并两个已排序的子数组。
    • 创建临时数组 left 和 right 存储两个子数组的元素。
    • 使用双指针法合并两个子数组到原数组中。
  4. TimSort函数：
    • tim_sort 首先对数组进行分块，每块大小为 RUN，并使用插入排序对每块进行排序。
    • 然后逐步合并这些已排序的块，合并的大小从 RUN 开始，每次翻倍，直到整个数组排序完成。

示例运行​

假设输入数组为 {12, 11, 13, 5, 6, 7}：

  1. 初始状态：{12, 11, 13, 5, 6, 7}
  2. 插入排序：
    • 对每个大小为 RUN 的块进行插入排序。
    • 由于 RUN 设置为 32，整个数组作为一个块进行插入排序。
    • 插入排序后数组：{5, 6, 7, 11, 12, 13}
  3. 合并：
    • 由于数组已经排序，无需进一步合并。

时间复杂度分析​

TimSort 的时间复杂度主要取决于插入排序和合并过程。

  • 最优时间复杂度：O(n)O(n)，当输入数组已经部分有序时。
  • 最坏时间复杂度：O(nlog⁡n)O(n \log n)，无论输入数组的初始顺序如何，执行的步骤基本一致。
  • 平均时间复杂度：O(nlog⁡n)O(n \log n)，对于大多数输入数组，TimSort 的性能都很稳定。

空间复杂度分析​

TimSort 使用了辅助数组来合并子数组，因此空间复杂度为 O(n)O(n)。

优缺点​

优点：

  • 时间复杂度稳定，适用于大规模数据排序。
  • 结合了插入排序和归并排序的优点，处理部分有序的数据时性能优异。
  • 稳定排序算法，不会改变相同元素的相对顺序。

缺点：

  • 实现复杂度较高，理解和编程上比简单排序算法复杂。
  • 辅助数组导致空间复杂度较高。

适用场景​

TimSort 适用于以下场景：

  • 数据量较大的排序。
  • 需要一个高效且稳定的排序算法时。
  • 数据部分有序时，TimSort 性能优异。

总结​

TimSort 是一种高效的排序算法，结合了插入排序和归并排序的优点。它通过对小块数组进行插入排序，然后逐步合并这些已排序的块，最终完成排序。尽管其实现复杂度较高，但在处理大规模数据和部分有序数据时表现优异，是一种时间复杂度稳定且空间复杂度较高的排序算法。

更深入理解Tim排序​

TimSort 的思想与实现​

TimSort 是一种混合排序算法，由 Tim Peters 于 2002 年为 Python 编程语言设计。它结合了插入排序和归并排序的优点，特别适合处理实际应用中的数据，因为这些数据往往部分有序。TimSort 主要思想是将数组分成多个小块（runs），对每个小块使用插入排序，然后使用归并排序合并这些小块。

TimSort 的基本思想​

  1. 分块：将数组分成多个小块（称为 runs），每个小块的大小为 RUN（通常为 32 或 64）。
  2. 插入排序：对每个小块使用插入排序进行排序。
  3. 合并：使用归并排序将这些已排序的小块逐步合并，直到整个数组排序完成。

TimSort 的过程​

  1. 分块与插入排序：

    • 将数组分成大小为 RUN 的小块。
    • 对每个小块进行插入排序，因为插入排序在处理小规模数据时效率较高。

  2. 合并小块：

    • 使用归并排序逐步合并这些已排序的小块。
    • 每次合并的块大小从 RUN 开始，每次翻倍，直到整个数组排序完成。

TimSort 的详细步骤​

  1. 定义 RUN 大小：

    • 通常设置 RUN 为 32 或 64，这是一个经验值，适用于大多数情况。

  2. 对每个块进行插入排序：

    • 从左到右遍历数组，每次处理一个大小为 RUN 的块。
    • 对每个块使用插入排序。

  3. 合并已排序的块：

    • 初始块大小为 RUN，逐步合并相邻的块。
    • 每次合并后块大小翻倍，直到整个数组排序完成。

TimSort 的伪代码​

def tim_sort(arr):
    RUN = 32
    n = len(arr)

    # 对每个块进行插入排序
    for i in range(0, n, RUN):
        insertion_sort(arr, i, min((i + RUN - 1), (n - 1)))

    # 合并已排序的块
    size = RUN
    while size < n:
        for left in range(0, n, 2 * size):
            mid = min((left + size - 1), (n - 1))
            right = min((left + 2 * size - 1), (n - 1))
            if mid < right:
                merge(arr, left, mid, right)
        size = 2 * size

插入排序和合并函数​

插入排序：

def insertion_sort(arr, left, right):
    for i in range(left + 1, right + 1):
        key = arr[i]
        j = i - 1
        while j >= left and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

合并函数：

def merge(arr, l, m, r):
    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

    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

    while i < len1:
        arr[k] = left[i]
        k += 1
        i += 1

    while j < len2:
        arr[k] = right[j]
        k += 1
        j += 1

TimSort 的实现细节​

  1. 分块大小：选择合适的 RUN 大小（通常为 32 或 64），以确保插入排序在每个小块内的效率。
  2. 插入排序：在每个小块内使用插入排序，因为插入排序对于小规模数据非常高效。
  3. 归并排序：逐步合并已排序的小块，合并时块大小逐次翻倍，最终将整个数组排序。

TimSort 的时间复杂度​

  • 最优时间复杂度：O(n)O(n)，当输入数组已经部分有序时。
  • 最坏时间复杂度：O(nlog⁡n)O(n \log n)，无论输入数组的初始顺序如何，执行的步骤基本一致。
  • 平均时间复杂度：O(nlog⁡n)O(n \log n)，对于大多数输入数组，TimSort 的性能都很稳定。

TimSort 的空间复杂度​

TimSort 使用了辅助数组来合并子数组，因此空间复杂度为 O(n)O(n)。

TimSort 的优缺点​

优点：

  • 时间复杂度稳定，适用于大规模数据排序。
  • 结合了插入排序和归并排序的优点，处理部分有序的数据时性能优异。
  • 稳定排序算法，不会改变相同元素的相对顺序。

缺点：

  • 实现复杂度较高，理解和编程上比简单排序算法复杂。
  • 辅助数组导致空间复杂度较高。

TimSort 的适用场景​

TimSort 适用于以下场景：

  • 数据量较大的排序。
  • 需要一个高效且稳定的排序算法时。
  • 数据部分有序时，TimSort 性能优异。

总结​

TimSort 是一种高效的排序算法，结合了插入排序和归并排序的优点。它通过对小块数组进行插入排序，然后逐步合并这些已排序的块，最终完成排序。尽管其实现复杂度较高，但在处理大规模数据和部分有序数据时表现优异，是一种时间复杂度稳定且空间复杂度较高的排序算法。