快速排序+歸并排序模闆

快速排序

void quickSort(int left,int right)
{
	if(left>=right)
		return ;
	int i=left,j=right;
	int mark=a[i];
	while(i<j)
	{
		while(a[j]>=mark&&i<j)
		{
			j--;
		}
		a[i]=a[j];
		while(a[i]<=mark&&i<j)
		{
			i++;
		}
		a[j]=a[i];
	}
	a[i]=mark;
	quickSort(left,i-1);
	quickSort(i+1,right);
}
           

歸并排序

#include<stdio.h>
int a[500010];
int b[500010];
long long res=0;
void merge(int l1,int r1,int l2,int r2)
{
	int begin=l1,end=r2,low=l1;
	while(l1<=r1&&l2<=r2)
	{
		if(a[l1]<a[l2])
		{
			b[begin++]=a[l1++];
		}
		else
		{
			b[begin++]=a[l2++];
			res+=(r1-l1+1);
		}
	}
	while(l1<=r1)	b[begin++]=a[l1++];
	while(l2<=r2)	b[begin++]=a[l2++];
	while(low<begin)
	{
		a[low]=b[low];
		low++;
	}
}
void mSort(int left,int right)
{
	if(left==right)
		return ;
	int mid=(left+right)/2;
	mSort(left,mid);
	mSort(mid+1,right);
	merge(left,mid,mid+1,right);
}
int main()
{
	int n,i;
	while(scanf("%d",&n)&&n)
	{
		res=0;
		for(i=0;i<n;i++)
		{
			scanf("%d",&a[i]);
		}
		mSort(0,n-1);
		printf("%lld\n",res);
	}
	return 0;
}