洛谷P1177 【模板】快速排序 (归并排序）

题目描述
利用快速排序算法将读入的N个数从小到大排序后输出。

快速排序是信息学竞赛的必备算法之一。对于快速排序不是很了解的同学可以自行上网查询相关资料，掌握后独立完成。（C++C++选手请不要试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。）

输入输出格式
输入格式：
第11行为一个正整数N，第2行包含N个空格隔开的正整数a i ，为你需要进行排序的数，数据保证了Ai不超过10000000001000000000。
输出格式：
将给定的N个数从小到大输出，数之间空格隔开，行末换行且无空格。

输入输出样例
输入样例#1：
5
4 2 4 5 1
输出样例#1：
1 2 4 4 5

归并排序视频讲解：
http://www.bilibili.com/video/av9982752?share_medium=android&share_source=qq&bbid=NgZgUGVXYVluVmVWKlYqinfoc&ts=1562894986507

参考代码：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
void merge(int arr[],int L,int M,int R)
{
	int left_size=M-L;
	int right_size=R-M+1;
	int left[50000];
	int right[50000];
	int i,j,k;
	for(int i=L;i<M;i++)
		left[i-L]=arr[i];
	for(int i=M;i<=R;i++)
		right[i-M]=arr[i];
	i=0;j=0;k=L;
	while(i<left_size&&j<right_size)
	{
		if(left[i]<right[j])
			arr[k++]=left[i++];
		else
			arr[k++]=right[j++];
	}
	while(i<left_size)
		arr[k++]=left[i++];
	while(j<right_size)
		arr[k++]=right[j++];
}
void mergesort(int arr[],int L,int R)
{
	if(L==R)
		return;
	else{
		int M=(L+R)/2;
		mergesort(arr,L,M);
		mergesort(arr,M+1,R);
		merge(arr,L,M+1,R);
	}
}
int main()
{
	int n,arr[100001];
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>arr[i];
	int L=0,R=n-1;
	mergesort(arr,L,R);
	for(int i=0;i<=R;i++)
		cout<<arr[i]<<" ";
	cout<<endl;
	return 0;
}

参考代码2：

#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
void merge(int *arr, int L, int M, int R){
	int left_size = M-L;
	int right_size = R-M+1;
	int *L_arr = new int[left_size];
	int *R_arr = new int[right_size];

	for(int i=L; i<M; i++)
		L_arr[i-L] = arr[i];
	for(int i=M; i<=R; i++)
		R_arr[i-M] = arr[i];

	int i = 0, j = 0, k = L;
	while(i < left_size && j < right_size)
		if(L_arr[i]<R_arr[j])
			arr[k++]= L_arr[i++];
		else
			arr[k++] = R_arr[j++];

	while(i < left_size)
		arr[k++] = L_arr[i++];
	while(j < right_size)
		arr[k++] = R_arr[j++];
}

void merge_sort(int *arr, int L, int R)
{
	if(L == R)
		return;
	else
	{
		int M = (L+R)/2;
		merge_sort(arr, L, M);
		merge_sort(arr, M+1, R);
		merge(arr, L, M+1, R);
	}
}
void print_sort(int *arr, int num)
{
	for(int i=0; i < num; i++)
		cout << arr[i] <<" ";
	cout << endl;
}
int main()
{
	int arr[10]={6, 3, 2, 7, 5, 1, 4, 0, 8, 9};
	merge_sort(arr, 0, 9);
	print_sort(arr, 10);
	return 0;
}