快速排序

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int n;
int q[N];

void QuickSort(int q[], int l, int r)
{
	cout<<"l:"<<l<<"r:"<<r<<endl;
	if (l >= r) return; // 递归终止条件，一个或者0个数，不用排序 
	int x = q[(l + r) / 2];//选取分界线。这里选数组中间那个数
	int i = l-1, j = r+1; 
//划分成左右两个部分
	while (i < j)
	{
		// 这里写成do while 循环
		do i++; while (q[i] < x); 
		do j--; while (q[j] > x);
		if (i < j) swap(q[i], q[j]);
	}
//对左右部分排序
	QuickSort(q, l, j);
	QuickSort(q, j+1, r);
}
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%d", &q[i]);
	
	QuickSort(q, 0, n-1);
	
	for (int i = 0; i < n; i++) printf("%d ", q[i]);    
	return 0;
}

归并排序：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+10;
int n,m=0;
long long q[N];

void mt(long long q[],int l,int r){
	if(l>=r)return; 
	int mid = l+(r-l)/2;
	mt(q,l,mid);
	mt(q,mid+1,r);
	int k=0,i=l,j=mid+1,tmp[r-l+1];
	while(i<=mid&&j<=r)
		if(q[i]<q[j])tmp[k++]=q[i++];
		else {tmp[k++]=q[j++];m=m+(mid-i)+1;}
	while(i<=mid)tmp[k++]=q[i++];
	while(j<=r)tmp[k++]=q[j++];
	for(int k=0,i=l;i<=r;i++,k++)q[i]=tmp[k];
}

int main(){
	cin>>n;
	for(int i=0;i<n;i++)scanf("%lld",&q[i]);
	mt(q,0,n-1);
	printf("%d",m);
	return 0;
}