資料結構
網路
關係資料庫管理系統 (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+
廣告