Tim sort

众所周知，现在主流的排序算法有快速排序和归并排序，但是各有缺点，比如快排的基准值如果每次都是数组中最小的那一个，就会退化成

O(n^2)

真的有这么做数据的。。。而归并排序则是非常难写，怎么办呢？着就用到了Tim sort(Tim排序)，大家来看一下他们的对比：

	快速排序	归并排序	Tim排序
最好时间	$O(n·logn)$	$O(n·logn)$	$O(1)$
最坏时间	$O(n^2)$	$O(n·logn)$	$O(n)$
最好空间	$O(n)$	$O(n)$	$O( \frac{n}{2} )$
最坏空间	$O(n)$	$O(n)$	$O(n)$
是否稳定	否	是	是

所以 Tim 排序也算得上比较强大了，在写代码之前，我们不妨先来了解一下它，首先看看它的工作原理：

Step1: 对数组进行区间划分，我们认为一个连续上升的或者连续下降的区间就是一个合法的区间，但是区间不能太长也不能太短，再 Java 中 Tim sort 是系统的默认排序， Jave 定义区间长度必须在 16~32 之间，否则调整。

例如: 2 5 6 | 3 1 | 7 8 9 | 4

由于数据较小，所以我们先把区间定义为：3

分割后发现 |3 1| |4| 不满足条件，则合并为 |4 3 1|

Step2:对于连续下降的区间，进行翻转，来保证程序的效率

例如：|2 5 6| |4 3 1| |7 8 9|

反转后：|2 5 6| |1 3 4| |7 8 9|

Step3:让所有区间进入栈，如果第2，3区间的长度之和小区等于区间1，则利用归并排序合并他们，否则选择较小2，3较小的一项与1合并

例如：stack:{|2 5 6|, |4 3 1|, |7 8 9|}

3 + 3 > 6，合并1，2

stack:{|1 2 3 4 5 6|, |7 8 9|}

Step4:重复操作3直到栈中只剩下2个区间，最后合并剩余的两个区间，并返回结果

由于我一个菜鸟(废物)并不强，所以只能写出一部份，而且 Tim sort 中也有很多优化，所以我的代码并不是很完整，不喜勿喷，也希望哪位大佬可以实现一下

可以看到，效率很快(DEV有延迟，所以用了0.3s)

Code by xpg007:

CPP

#include <bits/stdc++.h>
using namespace std;
int minrun(int n){
    int r = 0;
    while (n >= 32){
        r |= (n & 1);
        n >>= 1;
    }
    return n + r;
}
void merge(vector<int> &arr, int l, int m, int r){
    vector<int> temp(r - l + 1);
    int i = l, j = m + 1, k = 0;
    while (i <= m && j <= r)
        temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    while (i <= m)
        temp[k++] = arr[i++];
    while (j <= r)
        temp[k++] = arr[j++];
    for (k = 0, i = l; i <= r; ++i, ++k)
        arr[i] = temp[k];
}
void timSort(vector<int> &arr, int l, int r) {
    vector<int> temp(r - l + 1);
    int i, j, len, k;
    for (i = l; i <= r; i += len) {
        len = min(32 - 1, r - i + 1);
        if (len <= 32 - 1) {
            for (j = i; j < i + len; j++)
                for (k = j; k > i && arr[k] < arr[k - 1]; k--)
                    swap(arr[k], arr[k - 1]);
        } else {
            merge(arr, i, i + len / 2 - 1, i + len - 1);
        }
    }
}
 
int main(){
    vector<int> data = {};
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
    	int k;
    	cin >> k;
    	data.push_back(k);
	}
    timSort(data, 0, data.size() - 1);
    for (int num : data)
        cout << num << " ";
    cout << endl;
    return 0;
}

看到这里了，给个小小的关注吧，求求了~

讨论操作

回复

相关推荐

Tim sort