选择排序 冒泡排序 快速排序 归并排序模板 逆序对

快排和归并排序可以记一下

#include 
#include 

using namespace std;

int n,a[100005],tmp[100005];

//稳定的排序：直接插入排序、冒泡排序、归并排序、桶排序 
//不稳定的排序：希尔排序、直接选择排序、堆排序、快速排序

//简单选择排序，最好O(n2),不稳定：比如：5 5 1 
void selsort()
{
	for(int i=0;i=1;--i)//终点 
	{
		bool ok=true;
		for(int j=0;ja[j+1])
			{
				swap(a[j],a[j+1]);
				ok=false;
			}
		}
		if(ok)break;
	} 
}
//快速排序 递归 
void quick_sort(int l,int r)
{
	if(l>=r)return;
    int i=l-1,j=r+1,x=a[l+r>>1];
    while(ix);
        if(i=r)return;
	int mid=l+r>>1;
	merge_sort(l,mid);
	merge_sort(mid+1,r);
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r)
	{
		if(a[i]<=a[j])tmp[k++]=a[i++];
		else tmp[k++]=a[j++];
	}
	while(i<=mid)tmp[k++]=a[i++];
	while(j<=r)tmp[k++]=a[j++];
	for(int i=l,j=0;i<=r;++i,++j)a[i]=tmp[j];
}
int main()
{
	cin>>n;
	for(int i=0;i>a[i];
	//quick_sort(0,n-1);
	maosort(); 
	//selsort();
	//merge_sort(0,n-1);
	for(int i=0;i