Tim排序算法实现 Tim排序算法|数据结构

本文概述

技术
复杂

Tim-sort是一种从插入排序和合并排序派生的排序算法。它旨在以最佳方式对不同种类的现实世界数据执行。这是一种自适应排序算法, 需要O（n log n）比较才能对n个元素的数组进行排序。它是由Tim Peters在2002年以python编程语言设计和实现的。自2.3版以来, 它一直是python的标准排序算法。
技术考虑需要排序的n个元素的数组。在Tim排序中, 数组分为几个部分, 每个部分称为运行。这些运行通过使用插入排序一一进行排序, 然后使用合并功能对已排序的运行进行合并。 Tim排序的思想源于以下事实：插入排序在短列表上比在较大列表上更有效地工作。

文章图片
复杂

复杂	最好的情况	平均情况	最差的情况
时间复杂度	O(n)	O（n log n）	O（n log n）
Space Complexity			n

脚步：

将数组划分为称为运行的块数。
考虑运行大小为32或64（在以下实现中, 运行大小为32。）
使用插入排序将每个运行的单个元素一一排序。
使用合并排序的合并功能将已排序的运行逐一合并。
每次迭代后, 合并子数组的大小加倍。

#include<
stdio.h>
const int run = 32;
int minimum(int a, int b){	if(a<
b)	return a;
 	else 	return b;
 }void insertionSort(int a[], int beg, int end){int temp, i, j;
 for (i = beg + 1;
 i <
= end;
 i++){temp = a[i];
j = i –
 1;
while (a[j] >
 temp &
&
 j >
= beg){a[j+1] = a[j];
j–
;
}a[j+1] = temp;
}} void merge(int a[], int left, int mid, int right){int len1 = mid –
 left + 1, len2 = right –
 mid;
int beg[len1], end[len2];
int i, j, k;
for (i = 0;
 i <
 len1;
 i++)beg[i] = a[left + i];
for (i = 0;
 i <
 len2;
 i++)end[i] = a[mid + 1 + i];
 i = 0;
j = 0;
k = left;
 while (i <
 len1 &
&
 j <
 len2){if (beg[i] <
= end[j]){a[k] = beg[i];
i++;
}else{a[k] = end[j];
j++;
}k++;
}while (i <
 len1){a[k] = beg[i];
k++;
i++;
} while (j <
 len2){a[k] = end[j];
k++;
j++;
}}void timSort(int a[], int n){int i, size, beg, mid, end;
for (i = 0;
 i <
 n;
 i+=run)insertionSort(a, i, minimum((i+31), (n-1)));
for (size = run;
 size <
 n;
 size = 2*size){for (beg = 0;
 beg <
 n;
 beg += 2*size){mid = beg + size –
 1;
end = minimum((beg + 2*size –
 1), (n-1));
 merge(a, beg, mid, end);
}}}int main(){int a[] = {12, 1, 20, 2, 3, 123, 54, 332}, i;
int n = sizeof(a)/sizeof(a[0]);
printf(“
Printing Array elements \n”
);
for (i = 0;
 i <
 n;
 i++)printf(“
%d“
, a[i]);
printf(“
\n”
);
timSort(a, n);
 printf(“
Printing sorted array elements \n”
);
for (i = 0;
 i <
 n;
 i++)printf(“
%d“
, a[i]);
printf(“
\n”
);
return 0;
}

【Tim排序算法实现】