排序是一种简单算法，明明只用一个sort就可以解决，但我还是想和大家谈谈我内心的亿点点想法。

本文非专业，因为作者还是蒟蒻，不喜勿喷。

注：不是所有代码都能ACP1177之类的板子题，仅供参考。

常见排序（1~20）

1. 快速排序（系统）

在 C++ 的 stl 库里有这样一个函数：sort()。

我们简称快排，快速排序。

他的实现原理我们下一种方法会将，我们这里只需要知道它的实现方法：sort([数组名]+1,[数组名]+1+n);（省略中括号）。运行之后，数组就会变成从小到大的样子，你就会获得一个从小到大的数组了，他的时间复杂度是

n \log n

。

实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int a[20000005];
int main()
{
    int n,m;
    cin>>m;
    for(int i=1;i<=m;i++)
    {
    	cin>>a[i];//输入
	}
	sort(a+1,a+1+m);//stl排序
	for(int i=1;i<=m;i++)
	{
		cout<<a[i]<<" ";
	}
	return 0;
}

2. 快速排序（手写）

上个方法我们介绍了排序的 stl，这里我们来介绍的是他的实现方式。

想一想，我们有一个东西，比他小的数放左边，大的放右边，就可以把他们分类了。

我们可以每次选择一个基准数，当然，我们一般用随机数，那么我们以这个基准数为准，比他小的放左边，比他大的放右边，就会得到一个较为有序的数组。

但很明显，这不是完全从小到大的，所以我们又用到分治的思想：

我们生活中有一句话“大事化小，小事化了” 在程序设计中，这也同样可行。

比如一个数组求最大值的问题，给你一个长度为

4

的数组，让你求这个数组的最大值，我们可以换一种思路：

给你 1 5 2 6。

我们把 1 5 拿出来，再把 2 6 拿出来。

1 5 的最大值很明显我们用

\max

函数得出来是 5，2 6 是 6。

我们再把两个最大值 5 6 比大小，得出来 6。

这就是分治的典型案例，整个数组无法直接比大小，我们就把他分成小数组求，然后把小数组得来的答案往上传，和另一个小数组比较，循环往复，就得到了最终答案。

因为单纯一次基准数比较无法得出答案，我们就把基准数左边的数组再找一个基准数来排序，右边同理。

我们可以用函数递归的方法实现，那么最后，数组就排好序了，这样我们有

\log

次的排序，每次约等于

n

，那么总的时间复杂度大概是

n \log n

，同样优秀。

因为大家习惯用 stl，所以手写并不常用。

实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int n,m;
void qiuck_sort(int l,int r)
{
	if(l>=r) return;
	int mid=rand()%(r-l+1)+l; //随机基准数
	int t=a[mid];
	int q=l,h=r;
	a[mid]=a[l];
	while(q<h)
	{
		while(q<h&&a[h]>=t)//大的放右边
		{
			h--;
		}
		a[q]=a[h];
		while(q<h&&a[q]<=t)//小的放左边
		{
			q++;
		}
		a[h]=a[q];
	}
	qiuck_sort(l,q-1);//继续递归
	qiuck_sort(q+1,r);
	return;
}
int main()
{
	srand(time(0));//用随机数一定要加这句话
	cin>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	qiuck_sort(1,m);
	for(int i=1;i<=m;i++) cout<<a[i]<<" ";
	return 0;
}//此代码正确性无法保证，随机性强

3. 归并排序

快速排序用递归实现，我们也可以用递归分治的思想，创造另一种算法。

同样是排序，现在给你两个有序的数组，怎么把他们融合在一起，变成一个同样有序的数组？

这里可以用到指针，我们从左到右，如果当前第一个数组的第一个数，比第二个数组的第一个数小，就先把前者放入一个新数组里，然后把原数组里的这个数删除，这样，我们就能得到新数组了。

我们来模拟一下这个过程：

1 4 5 和 2 3 6。

首先，两个数组的第一个数分别是

1

和

2

，

1

更小，优先加入

1

。

接着，两个数组的第一个数分别是

4

和

2

，

2

更小，优先加入

2

。

接着，两个数组的第一个数分别是

4

和

3

，

3

更小，优先加入

3

。

接着，两个数组的第一个数分别是

4

和

6

，

6

更小，优先加入

6

。

接着，两个数组的第一个数分别是

5

和

6

，

5

更小，优先加入

5

。

最后只剩下了

6

，我们把

6

，放在最后，就得到了 1 2 3 4 5 6 这样的一个有序数组。

那么我们怎么得到两个有序的数组呢？

这就是递归的事了。

我们每次递归先直接调用函数，等着他把两个有序的数组传上来，我们再履行自己的职责，把这两个有序数组合并。

归并排序很明显比其他排序复杂，所以他一般被用来求逆序对（我们到时候再说）。

实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int a[1000005],b[1000005];
int n,m;
void merge_sort(int l,int r)
{
	int mid=(l+r)/2;
	int q=l,h=mid+1,cnt=0;//这里的数组是连在一起的有序数组，所以我们从中间断开
	while(q<=mid&&h<=r)
	{
		if(a[q]<=a[h])//如果第一个数小
		{
			cnt++;
			b[cnt]=a[q];
			q++;
		}
		else//第二个数小
		{
			cnt++;
			b[cnt]=a[h];
			h++;
		}
	}
	while(q<=mid)
	{
		cnt++;
		b[cnt]=a[q];
		q++;
	}
	while(h<=r)
	{
		cnt++;
		b[cnt]=a[h];
		h++;
	}
	for(int i=1,j=l;i<=cnt;i++,j++)
	{
		a[j]=b[i];
	}
	return;
}
void m_sort(int l,int r)
{
	if(l>=r) return;
	int mid=(l+r)/2;
	m_sort(l,mid);
	m_sort(mid+1,r);//先往下递归
	merge_sort(l,r);//再履行自己的职责
	return;
}
int main()
{
	cin>>m;
	for(int i=1;i<=m;i++) cin>>a[i];
	m_sort(1,m);
	for(int i=1;i<=m;i++) cout<<a[i]<<" ";
	return 0;
}

4. 桶排序

桶排序的时间复杂度取决于这个数的大小，在有些地方有奇效。

我们想，C++ 中有什么东西是有序的？

数组下标！

数组下标一般都是从

1

到

n

的，明显有序，所以我们就可以用这个性质来排序。

因为数字是可能重复的，所以我们拿一个数组来记录每个数字出现的数量。

最后，我们从

1

到极大值遍历这个记录数组，他出现了几次就输出几个他。

因为这个过程有点像往木桶里丢小球，所以我们简称桶排序。

实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int tong[10000005];
int n,m;
int main()
{
   cin>>n>>m;
   for(int i=1;i<=m;i++)
   {
   	int x;
   	cin>>x;
   	tong[x]++;//记录数出现的次数

   }
   for(int i=1;i<=n;i++)
   {
   	for(int j=1;j<=tong[i];j++) cout<<i<<" ";//
出现几次输出几次
   }
   return 0;
}

5. 堆排序

堆排序纯粹依靠另一种数据结构 - 堆，学名优先队列，但和队列没有关系。

堆，他的操作有以下几种：

priority_queue<int> q 定义一个叫做

q

，类型为

int

的堆。（默认是大根堆，就是返回最大值，如果要最小值，我们这样写：priority_queue<int,vector<int>,greater<int> >

q.push(x); 往名为

q

的堆里放入元素

x

。

q.pop(); 删除堆

q

中最大的元素。

q.top() 返回堆

q

中最大的元素是多少。

（注意以上两个操作不能在堆为空的时候使用）。

q.size() 返回堆

q

中的元素数量。

很明显，他可以把当前最大的元素告诉你，那我们就可以利用他排序。

一开始我们先把所有元素塞入这个堆，然后我们每次输出堆的最小值（所以我们要用上面的第二种定义），然后把最小值丢出去，再进行上面的操作，就可以排完序了。

因为堆单次操作的时间复杂度是

\log

，我们有

n

个元素，所以时间复杂度还是

n \log n

。

实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,m;
priority_queue<int,vector<int>,greater<int> > q;//定义小根堆
int main()
{
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int x;
		cin>>x;
		q.push(x);//把元素塞入数组
	}
	while(q.size()>0)
	{
		cout<<q.top()<<" ";//输出最小值
		q.pop();//弹出最小值
	}
	return 0;
}

6. 冒泡排序

上面我们都是从整体考虑问题，这里我们从个体来看待。

假如我们只用 x<y 这一个东西，能否完成一整个数组的排序呢？当然可以！

想想，我们是不是可以每次加入一个数，然后把他放入我们的新数组中？

但我们该如何把这个新进来的元素归位呢？一个一个比大小！

首先保证我们是上个数已经正确归位了才来处理这个元素的，所以我们的新数组一定是有序的！

我们先把他放在数组最后面，然后我们把它和他前面的一个元素比大小，如果我们的新元素更小，就把他和前面的元素换个位置，然后到了下一个位置，继续和下一个元素比，重复操作，直到出现了比新元素更小的元素，或者已经到了第一个元素，就停止，然后处理下一个新进来的元素。

这样，旧数组里的所有数解决完，我们就排完序啦！

因为这种相邻元素比大小很像冒泡泡（我不觉得）所以叫冒泡排序。

总的下来时间复杂度是

n^2

，很不建议使用，但一定要知道。

实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int n,m;
bool cmp(int q,int h)
{
	return q<h;
} 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<i;j++)//往前移动
		{
			if(a[j]>a[i])//比大小
			{
				swap(a[i],a[j]);
			}
                        //这里可以选择跳出循环，但不跳出也不会出BUG，既然已经有比我小的了，前面的肯定更小
		}
	}
	for(int i=1;i<=m;i++) cout<<a[i]<<" ";
	return 0;
}

7. 选择排序

其实选择排序就是不用堆的堆排序。

听起来很神奇的样子。

堆排序是每次拿出最小值，是

\log

的时间，但我们可以直接循环找最小值啊！不要忘本！

我们先在旧的数组中循环，找到一个最小的值，然后把他放到新数组里，接着再找最小值，循环往复，最后结束。

n^2

不建议使用。实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int a[1000005];
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int minn=2e9,ans=0;//准备找最小值
		for(int j=i;j<=m;j++)
		{
			if(a[j]<minn)//比较
			{
				minn=a[j];//找到最小值
				ans=j;//更新答案位置
			}
		}
		swap(a[i],a[ans]);//放入新数组，这样也没问题
	}
	for(int i=1;i<=m;i++) cout<<a[i]<<" ";
	return 0;
}

8. 插入排序

插入是什么意思？在一个位置插入一个元素。

那我们也是从旧数组中拿出新元素，塞入新数组里。

怎么塞？我们找到合适的位置就行了。

其实插入就是冒泡的改版，我们找到第一个比他小的数，然后把新的元素插在他前面就好啦！

所以插的时候我们要把他后面的数往后挪一格，给他腾出位置。

n^2

不建议用。

实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int a[1000005],ans[1000005];
int n,m;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=m;i++)
	{
		int id=0;
		for(int j=1;j<=i;j++)
		{
			id=j;
			if(a[i]<ans[j])//找到第一个比他小的
			{
				break;
			}
		}
		for(int j=i;j>=id;j--)
		{
			ans[j+1]=ans[j];//把其他数往后移动一格
		}
		ans[id]=a[i];//最后把数放进去
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<" ";
	return 0;
}

9.线段树排序

没学过线段树的不建议食用。

众所周知线段树是可以求区间最大值的，那我们就利用他求解整个数组的排序数组。

每次，我们查询到整个数组的最小值及他的编号（该一点点即可），然后把最小值放入答案数组，再把它在线段树里加上一个极大值，然后再重复上面的操作就行啦！

也是

n\log n

的时间复杂度。

CPP

#include<bits/stdc++.h>
#define int long long
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
using namespace std;
int n;
int a[1000005];
int minn[4000005],id[4000005];
void push_up(int k)
{
	if(minn[lson(k)]<minn[rson(k)]) minn[k]=minn[lson(k)],id[k]=id[lson(k)];
	else minn[k]=minn[rson(k)],id[k]=id[rson(k)];
	return;
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		minn[k]=a[l];
		id[k]=l;//再维护区间最小值的下标
		return;
	}
	int mid=(l+r)/2;
	build(lson(k),l,mid);
	build(rson(k),mid+1,r);
	push_up(k);
	return;
}//模板
void modify(int p,int val,int k,int l,int r)
{
	if(l==r)
	{
		minn[k]=val;
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid) modify(p,val,lson(k),l,mid);
	if(p>mid) modify(p,val,rson(k),mid+1,r);
	push_up(k);
	return;
}//模板
struct node
{
    int x,id;
};
node query(int L,int R,int k,int l,int r)
{
	if(L<=l&&r<=R) return {minn[k],id[k]};
	int ans=1e18,id=0;
	int mid=(l+r)/2;
	if(L<=mid)
    {
        node x=query(L,R,lson(k),l,mid);
        if(x.x<ans)
        {
            ans=x.x;
            id=x.id;
        }
    }
	if(R>mid)
	{
        node x=query(L,R,rson(k),mid+1,r);
        if(x.x<ans)
        {
            ans=x.x;
            id=x.id;
        }
	}
	return {ans,id};//要返回下标
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=n;i++)
	{
	    node x=query(1,n,1,1,n);//找到最小值
	    cout<<x.x<<" ";
	    modify(x.id,1e18,1,1,n);//给最小值+无穷大，让他不再参与最小值
	}
	return 0;
}

10.平衡树排序

没学过平衡树的又可以走了。

平衡树有一个操作，查询第

k

大的树，那么我们可以利用这个函数，每次查完再把他删了。

但删除一般删的是所有相同的数，所以我们

map

记录一下每个数的出现次数，每次输出对应次数就行了。

同样也是

n\log n

的时间复杂度。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct fhq
{
	int ls,rs,id,val,siz;
}fhq[1000005];
int cnt,root;
map<int,int> vis;
void push_up(int k)
{
	fhq[k].siz=fhq[fhq[k].ls].siz+fhq[fhq[k].rs].siz+1;
	return;
}
int build(int val)
{
	fhq[++cnt].val=val;
	fhq[cnt].ls=fhq[cnt].rs=0;
	fhq[cnt].siz=1;
	fhq[cnt].id=rand();
	return cnt;
}//板子
void split(int k,int &x,int &y,int val)
{
	if(k==0)
	{
		x=y=0;
		return;
	}
	if(fhq[k].val<=val)
	{
		x=k;
		split(fhq[k].rs,fhq[k].rs,y,val);
	}
	else
	{
		y=k;
		split(fhq[k].ls,x,fhq[y].ls,val);
	}
	push_up(k);
	return;
}//板子
void merge(int &k,int x,int y)
{
	if(x==0||y==0)
	{
		k=x+y;
		return;
	}
	if(fhq[x].id<fhq[y].id)
	{
		k=x;
		merge(fhq[k].rs,fhq[x].rs,y);
	}
	else
	{
		k=y;
		merge(fhq[k].ls,x,fhq[y].ls);
	}
	push_up(k);
	return;
}//板子
void Delete(int val)
{
	int r1=0,r2=0,r3=0;
	split(root,r1,r2,val);
	split(r1,r1,r3,val-1);
	merge(r3,fhq[r3].ls,fhq[r3].rs);
	merge(r1,r1,r3);
	merge(root,r1,r2);
	return;
}//板子
void insert(int val)
{
	int r1=0,r2=0,r3=build(val);
	split(root,r1,r2,val);
	merge(r1,r1,r3);
	merge(root,r1,r2);
	return;
}//板子
int kth(int p,int k)
{
	while(fhq[fhq[p].ls].siz+1!=k)
	{
		if(fhq[fhq[p].ls].siz>=k)
		{
			p=fhq[p].ls;
		}
		else
		{
			k-=fhq[fhq[p].ls].siz+1;
			p=fhq[p].rs;
		}
	}
	return fhq[p].val;
}//板子
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        if(vis[x]==0) insert(x);//加入平衡树
        vis[x]++;
    }
    for(int i=1;i<=n;i++)
    {
        int x=kth(root,1);//找到第一小
        for(int j=1;j<=vis[x];j++) cout<<x<<" ";//出现几次输出几次
        Delete(x);//删除
    }
    return 0;
}

11.map排序

众所周知，map是一个好用的stl，而map又是有序的，所以我们也可以通过他排序。

我们记录每个数出现的次数，然后使用auto来输出map里所有的数。

有的小竹子问：为什么不用桶排序了呢？

你猜我给你一个

10^{18}

你又该如何呢？

不过用map要注意空间，不然会直接炸掉。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
map<int,int> vis;
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        vis[x]++;
    }
    for(auto &i:vis)
    {
        for(int j=1;j<=i.second;j++) cout<<i.first<<" ";
    }
    return 0;
}

12.拓扑排序

拓扑这个算法想必大家都有所耳闻，那么通过他的性质，我们也可以排序。

我们先

n^2

的时间，来比较任意两个数的大小，然后小的一方给另一个连边（注意：要严格大于，不然会出现环）然后边拓扑边输出数。

这个时间复杂度是

n^2

的，空间也是，不建议使用。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> op[100005];
int in[100005];
int n,m;
int q[100005],a[100005];
int head=0,tail=1;
void topo()
{
    for(int i=1;i<=n;i++)
    {
        if(in[i]==0)
        {
            q[++head]=i;
        }
    }
    while(head-tail+1>0)
    {
        int x=q[tail];
        tail++;
        for(int i=0;i<op[x].size();i++)
        {
            in[op[x][i]]--;
            if(in[op[x][i]]==0)
            {
                q[++head]=op[x][i];
            }
        }//拓扑板子
        cout<<a[x]<<" ";//输出
    }
    return;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i]<a[j])
            {
                in[j]++;
                op[i].push_back(j);//建边
            }
        }
    }
    topo();
    return 0;
}

13.手写堆排序

就是把堆排序中的系统堆改成手写堆。

手写堆就是维护一棵树，每次我们删除，就把他的子树找人来顶替这个根，加入的话，就是让这个数往下走，找到一个合适的位置。

原理大家可以找其他地方讲解。

时间复杂度也是

n\log n

。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int m,a[100005],n=0;
void sift_up(int x)
{
	while(x/2>=1)
	{
		if(a[x]<a[x/2])
		{
			swap(a[x],a[x/2]);//往下走
			x/=2;
		}
		else return;
	}
}
void sift_down(int x)
{
	while(2*x<=n)
	{
		int t=x;
		if(a[t]>a[t*2]) t=x*2;
		if(a[t]>a[t*2+1]&&t*2+1<=n) t=2*x+1;
		if(t==x) return;
		swap(a[t],a[x]);
		x=t;//板子
	}
}
signed main()
{
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        n++;
        a[n]=x;
        sift_up(n);//塞进堆
    }
    for(int i=1;i<=m;i++)
    {
        cout<<a[1]<<" ";//取出堆顶
        swap(a[1],a[n]);
        n--;
        sift_down(1);
    }
    return 0;
}//这份代码可能有问题，我自己也没调出来，望各位看看

14.二叉搜索树排序

和平衡树排序很像，毕竟平衡树的原理就是二叉搜索树。

二叉搜索树是什么？

我们定义一个二叉树，给他每个点一个点权，再保证他的左子节点点权

\le

本身点权

<

右子节点点权。

那么不难发现，这棵二叉搜索树的中序遍历，便是一个从小到大的有序数组。

那我们现在解决二叉搜索树的构造。

每次把这个点从根节点开始遍历整棵二叉树，如果点权小于当前点的点权，若可能，往左子树走，否则自己成为左子节点。如果大于，若可能，往右子树走，否则自己成为右子树。

这样构建可以使这颗二叉树的层数分布较优，但仍然会被一些极端数据（比如从大到小的序列）卡掉，所以时间复杂度及不稳定。

中序遍历的实现方法不多说了。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int l[1000005],r[1000005];
int a[1000005];
int n,m;
void insert(int u,int x)
{
    if(a[x]<=a[u])//如果点权比当前点权小
    {
        if(l[u]>0) insert(l[u],x);//往左子树走
        else l[u]=x;//否则成为左子节点
    }
    else//大于同理
    {
        if(r[u]>0) insert(r[u],x);
        else r[u]=x;
    }
    return;
}
void dfs(int u)
{
    if(u==0) return;
    dfs(l[u]);
    cout<<a[u]<<" ";
    dfs(r[u]);//中序遍历
    return;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++)
    {
        insert(1,i);
    }
    dfs(1);
    return 0;
}

15.猴子排序

娱乐算法，人尽皆知。

每次随机交换任意数的位置，再判断这个数组是否有序。

娱乐算法，切勿在竞赛中使用。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000005];
int n;
signed main()
{
    srand(time(0));//核心
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(1)
    {
        for(int i=1;i<=n;i++)
        {
            int x=rand()%n+1;
            int y=rand()%n+1;
            if(a[x]>a[y]) swap(a[x],a[y]);//随机交换 
        }
        bool vis=true;
        for(int i=2;i<=n;i++) vis&=(a[i]>=a[i-1]);//是否有序
        if(vis)
        {
            for(int i=1;i<=n;i++) cout<<a[i]<<" ";
            cout<<endl;
            return 0;
        }
    }
    return 0;
}

16.ST表排序

ST表可以用来求解区间最大值，但这又有何用呢？

我们可以每次求出这个区间的最大值以及他的位置，然后以他为分割点，再比较两个子区间的最大值，再分割。。。

同时，我们还要把他们放在一个堆里，所以还带一个

log

。

那么这样就是一个不稳定算法，

n\log^2 n

n^2\log n

。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[100005][25],id[100005][25];
int a[100005];
int lg[100005];
int n;
void st_init()
{
	for(int j=1;j<=lg[n];j++)
	{
		for(int i=1;i<=n-(1<<j)+1;i++)
		{
			if(dp[i][j-1]<=dp[i+(1<<(j-1))][j-1])
			{
			    dp[i][j]=dp[i][j-1];
			    id[i][j]=id[i][j-1]; 
			}
			else
			{
			    dp[i][j]=dp[i+(1<<(j-1))][j-1];
			    id[i][j]=id[i+(1<<(j-1))][j-1];
			}
		}
	}
	return;
}
int get_ans(int l,int r)
{
	int k=lg[r-l+1];
	if(dp[l][k]<=dp[r-(1<<k)+1][k]) return id[l][k];
	return id[r-(1<<k)+1][k];
}
struct node
{
    int l,r;
    bool operator <(const node &f) const
    {
        return a[get_ans(l,r)]>a[get_ans(f.l,f.r)];
    }
};
priority_queue<node> q;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],dp[i][0]=a[i],id[i][0]=i;
    lg[0]=-1;
    for(int i=1;i<=n;i++) lg[i]=lg[i/2]+1;
    st_init();
    q.push({1,n});
    for(int i=1;i<=n;i++)
    {
        int l=q.top().l,r=q.top().r;
        q.pop();
        int id=get_ans(l,r);
        cout<<a[id]<<" ";
        if(l<=id-1) q.push({l,id-1});
        if(id+1<=r) q.push({id+1,r});
    }
    return 0;
}

17.单调栈排序

单调栈可以使栈里的数从上到下从小到大排序，但这个入栈的过程我们无法把握，我们只能说，如果这个数不在栈里，就把他丢进去。

所以这是一个时间复杂度随机的算法。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[100005];
int Stack[100005];
int n,top=0;
bool vis[100005];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(top<n)//如果不是全部入栈
    {
        for(int i=1;i<=n;i++)
        {
            if(vis[i]) continue;
            while(top>0&&a[i]>a[Stack[top]])
            {
                vis[Stack[top]]=false;
                top--;
            }//弹出
            vis[i]=true;
            Stack[++top]=i;
        }
    }
    for(int i=top;i>=1;i--) cout<<a[Stack[i]]<<" ";//输出
    return 0;
}

18.字典树排序

字典树大家想必有所耳闻。

我们可以贪心的思想，每次从字典树上找到最小的数，然后再删除，再找。

删除也不难，我们把当前点的前缀数量-1，然后每次找字典树的时候判断一下前缀是否为正数就行了。

那么我们设数的最大值为

10^{k+1}

，那么时间复杂度就达到了

O(nk^2)

！

但同时，空间复杂度也达到了惊人的

nk^2

.....

实现：

CPP

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],id=1;
int dis[1000005][10];
int siz[1000005];
void modify(string s)
{
    int x=1;
    for(int i=0;i<s.size();i++)
    {
        if(dis[x][s[i]-'0']==0) dis[x][s[i]-'0']=++id;
        x=dis[x][s[i]-'0'];
        siz[x]++;
    }
    return;
}
void query()
{
    int x=1;
    int cnt=0,sum=0;
    while(cnt<=10)
    {
        for(int i=0;i<=9;i++)
        {
            if(dis[x][i]!=0&&siz[dis[x][i]]>0)
            {
                x=dis[x][i];
                sum=sum*10+i;
                break;
            }
        }
        cnt++;
    }
    int size=siz[x];
    x=1,cnt=1;
    while(cnt<=10)
    {
        for(int i=0;i<=9;i++)
        {
            if(dis[x][i]!=0&&siz[dis[x][i]]>0)
            {
                x=dis[x][i];
                siz[x]-=size;
                break;
            }
        }
        cnt++;
    }
    for(int i=1;i<=size;i++) cout<<sum<<" ";
    return;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        string s="";
        int q=a[i];
        while(q)
        {
            s=char('0'+q%10)+s;
            q/=10;
        }
        while(s.size()<10) s="0"+s;
        modify(s);
    }
    for(int i=1;i<=n;i++) query();
    return 0;
}

19.全排列排序

嗯对没什么好讲的。

枚举这个数组如何排列，最后验证。

时间复杂度：

n!\times n

。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005];
int ans[1000005];
bool vis[1000005];
void dfs(int step)
{
    if(step>n)
    {
        bool vis=true;
        for(int i=2;i<=n;i++)
        {
            if(ans[i]<ans[i-1])
            {
                vis=false;
                break;
            }
        }
        if(vis)
        {
            for(int i=1;i<=n;i++) cout<<ans[i]<<" ";
            exit(0);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==false)
        {
            ans[step]=a[i];
            vis[i]=true;
            dfs(step+1);
            vis[i]=false;
        }
    }
    return;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    dfs(1);
    return 0;
}

20.希尔排序

冷门排序（21~50)

21.相对排序

貌似可以理解为优化版拓扑。

我们可以先

n^2

求出每个数比他大的最小值，接着找出数组最小值，然后开始递归，每次递归到比他大的最小值，然后输出再递归。

时间复杂度

n^2

。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100005];
map<int,int> vis,minn;
void print(int x)
{
    if(x==1e18) return;
    for(int i=1;i<=vis[x];i++) cout<<x<<" ";
    print(minn[x]);
    return;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],vis[a[i]]++;
    for(int i=1;i<=n;i++)
    {
        int minx=1e18;
        for(int j=1;j<=n;j++)
        {
            if(a[j]>a[i]) minx=min(minx,a[j]);
        }
        minn[a[i]]=minx;
    }
    int minx=1e18;
    for(int i=1;i<=n;i++) minx=min(minx,a[i]);
    print(minx);
    return 0;
}

优化排序（51~）

51.最长上升子序列优化堆排序

堆排序大家都记得吧，我们这里联合最长上升子序列再改造一下。

众所周知上升子序列是有序的，那么我们将多个最长上升子序列融合起来，会怎样？

没错，有点像归并，但我们的最长上升子序列可不止

2

个，所以我们用堆，其他的就和归并差不多了，但我们不需要递归。

至于求最长上升子序列都会吧，我们再用线段树优化，就可以做到不错的时间复杂度。

我们再把最长上升子序列分离就可以了。但这个算法需要线段树维护，所以值域要小。

至于怎么让最长上升子序列长度最平均，飞竹还没想到，交给你们。

实现（不优）：

CPP

#include<bits/stdc++.h>
#define lson(x) (x<<1)
#define rson(x) ((x<<1)|1)
#define int long long
using namespace std;
int dp[1000005],pre[1000005];
int a[4000005],n;
int maxn[4000005];
int vis[1000005];
void push_up(int k)
{
	maxn[k]=max(maxn[lson(k)],maxn[rson(k)]);
	return;
}
void build(int k,int l,int r)
{
	if(l==r)
	{
		maxn[k]=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(lson(k),l,mid);
	build(rson(k),mid+1,r);
	push_up(k);
	return;
}
void modify(int p,int val,int k,int l,int r)
{
	if(l==r)
	{
		maxn[k]=max(maxn[k],val);
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid) modify(p,val,lson(k),l,mid);
	if(p>mid) modify(p,val,rson(k),mid+1,r);
	push_up(k);
	return;
}
int query(int L,int R,int k,int l,int r)
{
	if(L<=l&&r<=R)
    {
        return maxn[k];
    }
	int ans=-1e18;
	int mid=(l+r)/2;
	if(L<=mid) ans=max(ans,query(L,R,lson(k),l,mid));
	if(R>mid) ans=max(ans,query(L,R,rson(k),mid+1,r));
	return ans;
}//线段树板子
int idd=0;
vector<int> op[1000005];
void print(int x)
{
    if(x==0||vis[x]) return;
    vis[x]=1;
    print(pre[x]);
    op[idd].push_back(x);
    return;
}//分离子序列
struct node
{
    int x,id,siz;
    bool operator <(const node &f) const
    {
        return x>f.x;//重载运算符
    }
};
priority_queue<node> q;
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        int x=query(1,a[i],1,1,1000000);
        dp[i]=x+1;
        pre[i]=vis[x];
        modify(a[i],dp[i],1,1,1000000);
        vis[dp[i]]=i;//线段树优化最长上升子序列
    }
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=n;i>=1;i--)
    {
        if(vis[i]==0)
        {
            idd++;
            print(i);
        }
    }
    for(int i=1;i<=idd;i++)
    {
        q.push({a[op[i][0]],i,0});//入堆
    }
    for(int i=1;i<=n;i++)
    {
        node x=q.top();
        q.pop();
        cout<<x.x<<" ";
        if(x.siz+1<op[x.id].size())
        {
            q.push({a[op[x.id][x.siz+1]],x.id,x.siz+1});//找下一个顶替
        }
    }
    return 0;
}

52.偏移量优化桶排序

很多情况下，需要排序的数组里会含着负数，众所周知，数组是不能访问负数下标的。

但我们是否可以把这些数都加上一个特定值？

加上一个特定值，他们的相对关系是不变的，而又让这些下标可以访问，是一个不错的选择。

最后输出时，减去这个特定值就行啦。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[1000005];
int vis[2000005];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],vis[a[i]+1000000]++;/偏移
    for(int i=0;i<=2000000;i++)
    {
        for(int j=1;j<=vis[i];j++) cout<<i-1000000<<" ";//还原输出
    }
    return 0;
}

53.链表+平衡树优化插入排序

插入排序的时间复杂度就在于寻找和插入。

插入是最好优化的，用链表就可以了。

但查找呢？链表上可以二分，但这里每次带修改，很难实现。

没事，我们可以平衡树求出这个树的前驱和后继就可以了。

时间复杂度就被优化到了

n\log n

。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int root=0,cnt=0,head=0,add=0,maxn=0,minn=1e18;
struct node
{
    int l,x,r;
}s[1000005];
struct fhq
{
	int ls,rs,id,val,siz;
}fhq[1000005];
int build(int val)
{
	fhq[++cnt].val=val;
	fhq[cnt].ls=fhq[cnt].rs=0;
	fhq[cnt].siz=1;
	fhq[cnt].id=rand();
	return cnt;
}
void push_up(int k)
{
	fhq[k].siz=fhq[fhq[k].ls].siz+fhq[fhq[k].rs].siz+1;
	return;
}
void split(int k,int &x,int &y,int val)
{
	if(k==0)
	{
		x=y=0;
		return;
	}
	if(fhq[k].val<=val)
	{
		x=k;
		split(fhq[k].rs,fhq[k].rs,y,val);
	}
	else
	{
		y=k;
		split(fhq[k].ls,x,fhq[y].ls,val);
	}
	push_up(k);
	return;
}
int kth(int p,int k)
{
	while(fhq[fhq[p].ls].siz+1!=k)
	{
		if(fhq[fhq[p].ls].siz>=k)
		{
			p=fhq[p].ls;
		}
		else
		{
			k-=fhq[fhq[p].ls].siz+1;
			p=fhq[p].rs;
		}
	}
	return fhq[p].val;
}
void merge(int &k,int x,int y)
{
	if(x==0||y==0)
	{
		k=x+y;
		return;
	}
	if(fhq[x].id<fhq[y].id)
	{
		k=x;
		merge(fhq[k].rs,fhq[x].rs,y);
	}
	else
	{
		k=y;
		merge(fhq[k].ls,x,fhq[y].ls);
	}
	push_up(k);
	return;
}
void insert(int val)
{
	int r1=0,r2=0,r3=build(val);
	split(root,r1,r2,val);
	merge(r1,r1,r3);
	merge(root,r1,r2);
	return;
}
int pre(int val)
{
	int r1=0,r2=0;
	split(root,r1,r2,val-1);
	int res=kth(r1,fhq[r1].siz);
	merge(root,r1,r2);
	return res;
}
int suc(int val)
{
	int r1=0,r2=0;
	split(root,r1,r2,val);
	int res=kth(r2,1);
	merge(root,r1,r2);
	return res;
}//板子
int a[100005],n;
map<int,int> vis,id;
void print(int x)
{
    if(x==0) return;
    for(int i=1;i<=vis[s[x].x];i++) cout<<s[x].x<<" ";
    print(s[x].r);//递归输出
    return;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,a[i]),minn=min(minn,a[i]);
        if(vis[a[i]]>0)
        {
            vis[a[i]]++;
            continue;
        }
        vis[a[i]]++; 
        int p=0,c=0;
        if(minn!=a[i]) p=pre(a[i]);
        if(maxn!=a[i]) c=suc(a[i]);//求前驱和后继
        p=id[p],c=id[c];
        add++;
        s[p].r=add;
        s[c].l=add;
        s[add].l=p;
        s[add].r=c;
        s[add].x=a[i];//链表基操
        id[a[i]]=add;
        insert(a[i]);//要插入
        if(p==0) head=add;
    }
    print(head);
    return 0;
}

54.三分优化归并排序

我们是否可以在分治的时候分成三份呢？

可以的，这样时间复杂度就是

O(n\log_3 n\times 3)

。

那么相同的快速排序我们就不说了。

实现：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000005],b[1000005];
int n;
void merge_sort(int l,int r)
{
  int q1=l,q2=l+(r-l+1)/3+1,q3=l+(r-l+1)*2/3+1;
  int cnt=0;//这里的数组是连在一起的有序数组，所以我们从两个三等分点断开
  while((q1<=l+(r-l+1)/3)&&(q2<=l+(r-l+1)*2/3)&&(q3<=r))
  {
  	if(a[q1]<=a[q2]&&a[q1]<=a[q3])//如果第一个数小
  	{
  		cnt++;
  		b[cnt]=a[q1];
  		q1++;
  	}
  	else if(a[q2]<=a[q1]&&a[q2]<=a[q3])
  	{
  		cnt++;
  		b[cnt]=a[q2];
  		q2++;
  	}
  	else
  	{
  	    cnt++;
  	    b[cnt]=a[q3];
  	    q3++;
  	}
  }
  while((q1<=l+(r-l+1)/3)&&(q2<=l+(r-l+1)*2/3))
  {
      if(a[q1]<=a[q2])
      {
          cnt++;
          b[cnt]=a[q1];
          q1++;
      }
      else
      {
          cnt++;
          b[cnt]=a[q2];
          q2++;
      }
  }
  while((q1<=l+(r-l+1)/3)&&(q3<=r))
  {
      if(a[q1]<=a[q3])
      {
          cnt++;
          b[cnt]=a[q1];
          q1++;
      }
      else
      {
          cnt++;
          b[cnt]=a[q3];
          q3++;
      }
  }
  while((q2<=l+(r-l+1)*2/3)&&(q3<=r))
  {
      if(a[q2]<=a[q3])
      {
          cnt++;
          b[cnt]=a[q2];
          q2++;
      }
      else
      {
          cnt++;
          b[cnt]=a[q3];
          q3++;
      }
  }
  while(q1<=l+(r-l+1)/3)
  {
  	cnt++;
  	b[cnt]=a[q1];
  	q1++;
  }
  while(q2<=l+(r-l+1)*2/3)
  {
  	cnt++;
  	b[cnt]=a[q2];
  	q2++;
  }
  while(q3<=r)
  {
  	cnt++;
  	b[cnt]=a[q3];
  	q3++;
  }
  for(int i=1,j=l;i<=cnt;i++,j++)
  {
  	a[j]=b[i];
  }
  return;
}
void m_sort(int l,int r)
{
  if(l>=r) return;
  int mid1=l+(r-l+1)/3,mid2=l+(r-l+1)*2/3;
  m_sort(l,mid1);
  m_sort(mid1+1,mid2);
  m_sort(mid2+1,r);
  merge_sort(l,r);
  return;
}
signed main()
{
  cin>>n;
  for(int i=1;i<=n;i++) cin>>a[i];
  m_sort(1,n);
  for(int i=1;i<=n;i++) cout<<a[i]<<" ";
  return 0;
}

论排序的100种方法

文章操作

常见排序（1~20）

1. 快速排序（系统）

2. 快速排序（手写）

3. 归并排序

4. 桶排序

5. 堆排序

6. 冒泡排序

7. 选择排序

8. 插入排序

9.线段树排序

10.平衡树排序

11.map排序

12.拓扑排序

13.手写堆排序

14.二叉搜索树排序

15.猴子排序

16.ST表排序

17.单调栈排序

18.字典树排序

19.全排列排序

20.希尔排序

冷门排序（21~50)

21.相对排序

优化排序（51~）

51.最长上升子序列优化堆排序

52.偏移量优化桶排序

53.链表+平衡树优化插入排序

54.三分优化归并排序

55.

相关推荐

评论

论排序的100种方法