Tim排序算法实现

本文概述

• 技术
• 复杂

Tim-sort是一种从插入排序和合并排序派生的排序算法。它旨在以最佳方式对不同种类的现实世界数据执行。这是一种自适应排序算法, 需要O（n log n）比较才能对n个元素的数组进行排序。它是由Tim Peters在2002年以python编程语言设计和实现的。自2.3版以来, 它一直是python的标准排序算法。

技术

考虑需要排序的n个元素的数组。在Tim排序中, 数组分为几个部分, 每个部分称为运行。这些运行通过使用插入排序一一进行排序, 然后使用合并功能对已排序的运行进行合并。 Tim排序的思想源于以下事实：插入排序在短列表上比在较大列表上更有效地工作。

复杂

脚步 ：

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

C program

#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; }

Output:

Printing Array elements 
12  1  20  2  3  123  54  332
  
Printing sorted array elements 
1  2  3  12  20  54  123  332  



Next Topic



← prev next →