tim 排序-ag捕鱼王app官网

tim 排序是一种混合稳定排序算法。它是由插入排序和衍生出来的混合算法。它首先使用插入排序进行子数组，这些小的排序子数组被称为自然运行。然后使用合并排序对这些运行进行合并子数组，产生最终的排序数组。它的设计考虑到算法在真实世界数据上的最佳性能。它利用了插入排序在小尺寸子数组上表现非常好的事实。它是 java 的 array.sort() 和 python 的 sorted() 和 sort() 使用的标准排序算法。

tim 排序算法

假设我们有一个包含 n 元素的无序数组 a[]。我们将考虑运行的大小为 32。它可以是 2 的任何幂数，因为当数字是 2 的幂数时，合并更有效。

timsort()

1. 将数组划分为 n/32 运行。
2. 使用插入排序函数对各个运行逐一进行排序。
3. 使用合并排序的 merge 函数将排序后的运行逐一合并。

merge()

• 初始化辅助数组 output 来存储排序后的输出。
• 初始化 3 个指针 i、j 和 k。
  • i 指向第一个子数组 beg 的开始。
  • j 指向第二个子数组 mid 1 的开始。
  • k 用 beg 初始化，保持排序数组 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)

• 第一次迭代

键：a[1]=5

• 第二次迭代

键：a[2]=4

• 第三次迭代

键：a[3]=2

第二个子数组：(1,7,6,4)。

• 第一次迭代

键：a[1]=7

• 第二次迭代

键：a[2]=6

• 第三次迭代

键：a[3]=4

合并两个排序的子数组，得到最终的子数组为：(1, 2, 3, 4, 5, 6, 7, 8)。

tim 排序算法的实现

#includeusing 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)。