题解 | 排序

#include<iostream>
#include<vector>
using namespace std;

//合并操作(合并两个有序的数组并组成一个新的有序数组)
void merge(vector<int>& arr,int l,int m,int r){
	int n1 = m - l + 1;
	int n2 = r - m;

	//创建一个临时的数组
	vector<int> L,R;

	//初始化两个临时数组
	for(int i = 0;i<n1;i++){
		L.push_back(arr[l+i]);
	}
	for(int i = 0;i<n2;i++){
		R.push_back(arr[i + m + 1]);
	}

	int temp = l;
	int i = 0;
	int j = 0;
	while(i<n1&&j<n2){
		if(L[i]<=R[j]){
			arr[temp] = L[i];
			i++;			
		}else{
			arr[temp] = R[j];
			j++;
		}
		temp++;
	}
	
	//如果L数组中还有剩余元素
	while(i<n1){
		arr[temp] = L[i];
		i++;
		temp++;
	}

	//如果R数组中还有剩余的元素
	while(j<n2){
		arr[temp] = R[j];
		j++;
		temp++;
	}
}


//分治操作
void mergeSort(vector<int>& arr,int l,int r){
	if(l<r){
		int m = (l+r)/2;
		//左半部分的排序
		mergeSort(arr,l,m);
		//右半部分的排序
		mergeSort(arr,m+1,r);
		//合并已排序的左半部分和右半部分
		merge(arr,l,m,r);
	}
}

/*
 *归并排序
 * */
int main(){
	int n = 0;
	cin>>n;
	vector<int> arr;
	for(int i = 0;i<n;i++){
		int a = 0;
		cin>>a;
		arr.push_back(a);
	}
	//分治操作
	mergeSort(arr,0,arr.size()-1);

	//将排序好的数组按照顺序输出
	for(int i = 0;i<arr.size();i++){
		cout<<arr[i]<<" ";
	}	
}