新排序算法——斯大林排序

如何给

n

个数排序？

一个朴素是想法是从头开始，把不符合顺序要求的元素都踢出去，最后就只剩下有序的元素了。但是这称不上一个排序算法，因为这个算法改变了原来的序列，不过我们可以把踢出去的元素记录下来，再递归进行排序，最后

O(n)

把两部分合并起来。

现在我们分析这个算法的复杂度，根据 P1943 中的分析，我们发现每次排序只会选出

O(\log n)

个元素，其他的都会进入到下一轮排序，所以总复杂度高达

O(\frac{n^2}{\log n})

，空间复杂度也相当高，喜提 MLE。

考虑如何优化这个算法使它能通过

10^5

的数据。

上面算法中一个显著的问题是每次保留的元素太少了，于是我们采用二分查找优化计算最长不下降子序列，并记录转移点，最后回溯找到最长的序列，把它拿出来，其他的部分递归进行排序，你发现它竟然过了！

分析这个算法的复杂度，由 https://arxiv.org/abs/math/9905032 上的结论得，一个随机序列的最长上升子序列（和最长不下降子序列期望相同）长度期望大约是

2\sqrt n

，于是只需要选

O(\sqrt n)

轮就可以把数都选完，每轮需要计算一次最长不下降子序列。总时间复杂度为

O(n\sqrt n\log n)

，并且越到后面序列长度越短，所以常数很小，可以通过。

参考实现：

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

mt19937 rnd(random_device{}());

int n;
int a[100001],f[100001],g[100001];

int max_stalin_split(int l){
	int cnt=0;
	f[++cnt]=a[l];
	g[1]=1;
	for (int i=l+1;i<=n;i++){
		if (f[cnt]<=a[i]){
			f[++cnt]=a[i];
			g[i]=cnt;
		}else{
			int j=upper_bound(f+1,f+cnt+1,a[i])-f;
			f[j]=a[i];
			g[i]=j;
		}
	}
	int i=n,j=cnt,idx=0;
	cnt=n;
	for (;i>=l;i--){
		if (j>=0 and g[i]==j){
			a[cnt--]=a[i];
			j--;
		}else f[++idx]=a[i];
	}
	int r=cnt;
	for (int i=idx;i>=1;i--) a[cnt--]=f[i];
	rotate(a+l,a+r+1,a+n+1);
	return n-r+l-1;
}

void stalin_sort_optimized(int l){
	if (l>=n) return;
	shuffle(a+l,a+n+1,rnd); // shuffle 一下，否则遇到一直降序的序列就完了
	int p=max_stalin_split(l);
	stalin_sort_optimized(p+1);
	inplace_merge(a+l,a+p+1,a+n+1);
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n;
	for (int i=1;i<=n;i++) cin>>a[i];
	stalin_sort_optimized(1);
	for (int i=1;i<=n;i++) cout<<a[i]<<" ";
	return 0;
}

新排序算法——斯大林排序

文章操作

相关推荐

评论

新排序算法——斯大林排序