数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++ Tim排序算法
Timsort 是一种稳定的排序算法，它结合了归并排序和插入排序的思想。它也可以被称为插入排序和归并排序的混合算法。它广泛用于 Java、Python、C 和 C++ 的内置排序算法中。该算法背后的思想是使用插入排序对小块进行排序，然后使用归并排序的合并函数合并所有大块。
工作原理
在这个算法中，数组被分成小的块。这些块被称为 RUN。每个 RUN 都使用插入排序技术进行排序。在所有 RUN 排序后，它们使用合并函数进行合并。
可能存在数组大小小于 RUN 的情况。在这种情况下，数组将通过插入排序技术进行排序。通常，RUN 块的大小根据数组的大小而变化，从 32 到 64 不等。合并函数只有在子数组块的大小为 2 的幂时才会进行合并。
使用插入排序的优势在于，插入排序对于小尺寸数组的排序效果很好。
时间复杂度 −
最佳情况 - Ω(n)
平均情况 - O(nlogn)
最坏情况 - O(nlogn)
Timsort 算法步骤
初始化 RUN 的大小为 32。
对 RUN 大小的块实现插入排序。
函数 merge(int arr[], int l, int m, int r) 以数组、左元素、数组中间元素和右元素作为输入。该函数返回大小为 32 的已合并排序块。
初始化包含所有左元素的数组的长度和包含所有右元素的数组的长度。
填充左数组和右数组后，迭代左数组和右数组。
如果左数组中的元素小于右数组中的元素，则将元素推入较大的数组。
否则，根据情况将元素推入较小的数组。
将左数组和右数组中剩余的元素复制到较大的数组中。
函数 timSortAlgo(int arr[], int n) 以数组及其大小作为输入。它最初调用插入排序并合并数组元素。
使用 Timsort 返回数组的最终元素作为输出。
示例 (C++)
#include<bits/stdc++.h>
using namespace std;
const int RUN = 32; // Initialising the RUN to get chunks
void insertionSort(int arr[], int left, int right) // Implementing insertion
sort for RUN size chunks{
for (int i = left + 1; i <= right; i++){
int t = arr[i];
int j = i - 1;
while (j >= left && t < arr[j]){
arr[j+1] = arr[j--];
}
arr[j+1] = t;
}
}
void merge(int arr[], int l, int m, int r) // using the merge function the
sorted chunks of size 32 are merged into one{
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]; // Filling left array
for (int i = 0; i < len2; i++)
right[i] = arr[m + 1 + i]; // Filling right array
int i = 0;
int j = 0;
int k = l;
while (i < len1 && j < len2) // Iterate into both arrays left and right{
if (left[i] <= right[j]) // IF element in left is less then increment i by pushing into larger array{
arr[k] = left[i];
i++;
} else {
arr[k] = right[j]; // Element in right array is greater
increment j
j++;
}
k++;
}
while (i < len1) // This loop copies remaining element in left array{
arr[k] = left[i];
k++;
i++;
}
while (j < len2) // This loop copies remaining element in right array{
arr[k] = right[j];
k++;
j++;
}
}
void timSortAlgo(int arr[], int n){
for (int i = 0; i < n; i+=RUN) insertionSort(arr, i, min((i+31), (n-1))); //Call insertionSort()
for (int s = RUN; s < n; s = 2*s) // Start merging from size RUN (or 32). It will continue upto 2*RUN{
// pick starting point of left sub array. We are going to merge
arr[left..left+size-1]
// and arr[left+size, left+2*size-1]
// After every merge, we
// increase left by 2*size
for (int left = 0; left < n;left += 2*s){
int mid = left + s - 1; // find ending point of left sub
array mid+1 is starting point of right sub array
int right = min((left + 2*s - 1), (n-1));
merge(arr, left, mid, right); // merge sub array
arr[left.....mid] & arr[mid+1....right]
}
}
}
void printArray(int arr[], int n){
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
}
// Main function to implement timsort algorithm
int main(){
int arr[] = {-2, 7, 15, -14, 0, 15, 0, 7, -7, -4, -13, 5, 8, -14, 12};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "The Original array- ";
printArray(arr, n);
// calling the timsortAlgo function to sort array
timSortAlgo(arr, n);
cout<<"After Sorting Array Using TimSort Algorithm- ";
printArray(arr, n); // Calling print function
return 0;
}
更新于：2021年2月5日
浏览量 1K+
广告