快读

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

Copy

快写

inline void write(int x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

Copy

插入排序

#include<iostream>
#include<cmath>
using namespace std;
int n,a[100005];
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)
	{
		int j=i-1;
		while(j>=1&&a[j]>a[j+1])
		{
			swap(a[j],a[j+1]);
			j--;
		}
	}
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
}

Copy

堆排序

#include<iostream>
#include<cmath> 
using namespace std;
int t,p[1000005],len;
void push_up(int id)
{
	if(id/2==0)return;
	if(p[id/2]>p[id])
	{
		swap(p[id/2],p[id]);
		push_up(id/2);
	}
}
void push_down(int id)
{
	int k=id;
	if(id*2<=len&&p[id*2]<p[k])
		k=id*2;
	if(id*2+1<=len&&p[id*2+1]<p[k])
		k=id*2+1;
	if(id!=k)
	{
		swap(p[id],p[k]);
		push_down(k);
	}
}
int main()
{
	cin>>t;
	while(t--)
	{
		int opt,x;
		cin>>opt;
		if(opt==1)
		{
			cin>>x;
			p[++len]=x;
			push_up(len);
		}
		else if(opt==2)
		{
			cout<<p[1]<<endl;
		}
		else
		{
			p[1]=p[len--];
			push_down(1);
		}
	}
	return 0;
}

Copy

归并排序

#include<iostream>
using namespace std;
int n,a[100005],b[100005];
void merger_sort(int l,int r)
{
	if(l>=r)return;
	int mid=l+r>>1;
	merger_sort(l,mid);
	merger_sort(mid+1,r);
	int x=l,L=l,y=mid+1;
	while(x<=mid&&y<=r)
	{
		if(a[x]<=a[y])
			b[l++]=a[x++];
		else
			b[l++]=a[y++];
	}
	while(x<=mid)
		b[l++]=a[x++];
	while(y<=r)
		b[l++]=a[y++];
	for(int i=L;i<=r;i++)
		a[i]=b[i];
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	merger_sort(1,n);
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
}

Copy

快速排序

#include<iostream>
using namespace std;
int n,a[100005];
int check(int l,int r)
{
	int k=l;
	while(l<=r)
	{
		while(l<=r&&a[l]<=a[k])
			l++;
		while(l<=r&&a[r]>=a[k])
			r--;
		if(l<=r)
			swap(a[l],a[r]);
	}
	swap(a[k],a[r]);
	return r;
}
void quickly_sort(int l,int r)
{
	if(l>=r)return;
	int mid=check(l,r);
	quickly_sort(l,mid-1);
	quickly_sort(mid+1,r);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	quickly_sort(1,n);
	for(int i=1;i<=n;i++)cout<<a[i]<<" ";
	return 0;
}