归并排序——分治法 —排序

归并排序
时间复杂度：O（ n log2 n）

#include<stdio.h>
#include <iostream>
#include<iomanip>
using namespace std;
int r[10];
void Merge(int r[],int r1[],int s,int m,int t){
	int i=s,j=m+1,k=s;
	while(i<=m&&j<=t){
		if(r[i]<=r[j])
			r1[k++]=r[i++];
		else
            r1[k++]=r[j++];
	}
	while(i<=m)
		r1[k++]=r[i++];
	while(j<=t)
		r1[k++]=r[j++];
}
void MergeSort(int r[],int s,int t){
	int m,r1[1000];
	if(s==t)
		return;
	else
	{
		m=(s+t)/2;
		MergeSort(r,s,m);
		MergeSort(r,m+1,t);
		Merge(r,r1,s,m,t);
		for(int i=s;i<=t;i++)
			r[i]=r1[i];
	}

}

void main(){
	int data[10]={50,30,23,46,59,16,2,56,48,28};
    MergeSort(data,0,9);
	
	
	for(int j=0;j<10;j++)
		
		cout<<setw(3)<<data[j];
	cout<<endl;
}

运行结果: