JZTXT

归并排序

发布时间 2023-09-07 10:24:09作者: _满堂花醉三千客

模板

#include<iostream>

using namespace std;

const int N =1e6+10;
int q[N],tem[N];
void merge_sort(int q[],int l,int r){
	if(l>=r) return;
	int mid = (l+r) >>1;
	merge_sort(q,l,mid);
	merge_sort(q,mid+1,r);
	int k=0,i=l,j=mid+1;
	while(i<=mid&&j<=r){
		if(q[i]<q[j]){
			tem[k++]=q[i++];
		}else{
			tem[k++]=q[j++];
		}
	}
	while(i<=mid) tem[k++]=q[i++];
	while(j<=r) tem[k++]=q[j++];
	for(int i=l,j=0;i<=r;++i,++j){
		q[i]=tem[j];
	}
}
int main(){
	
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;++i){
		scanf("%d",&q[i]);
	}
	
	merge_sort(q,0,n-1);
	
	for(int i=0;i<n;++i){
		printf("%d ",q[i]);
	}
	
	return 0;
}

merge_sort(q,l,mid);和merge_sort(q,mid+1,r);递归到边界的时候相当于把数组每个值单独拿出，归的时候就进行排序

for(int i=l,j=0;i<=r;++i,++j){q[i]=tem[j];}递归成后面的小段q数组从l开始，而tem记录的各个值是从0开始传递值