洛谷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;
}