Tim 排序

Harshit Jindal 2023年10月12日
  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
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