二分归并排序

二分归并排序初见

问题：对n个不同的数构成的数组arr[n]进行排序，其中n=2^k。

分析

主要思想就是将一个大问题分成两个小问题，一直分一直分，分到你能将小问题解决后再把它们拼起来。可以说非常递归了。

解决方法

#include<stdio.h>
#include<stdlib.h>

void Merge(int *array,int start,int mid,int end){
	int *Left=new int[mid-start+1];
	int *Right=new int[end-mid];
	
	int l=0,r=0;
	for(int i=start;i<=mid;i++){
		Left[l++]=array[i];
	}
	
	for(int i=mid+1;i<=end;i++){
		Right[r++]=array[i];
	}
	
	int i=0,j=0;
	int flag=start;
	while(i<sizeof(Left)&&j<sizeof(Right)){
		if(Left[i]<Right[j]){
			array[flag++]=Left[i++];
		}else{
			array[flag++]=Right[i++];
		}
	}
	
	while(i<sizeof(Left)){
		array[flag++]=Left[i++];
	}
	
	while(j<sizeof(Right)){
		array[flag++]=Right[i++];
	}
}

int MergeSort(int *array,int start,int end){
	
	if(sizeof(array)<=0){
		return 0;
	}
	
	if(start<end){
		int mid=start+(end-start)/2;
		MergeSort(array,start,mid);
		MergeSort(array,mid+1,end);
		Merge(array,start,mid,end);
	}
	
	return *array;
}

int main(){
	int n=0;
	int i;
	scanf("%d",&i);
	int *arr=(int*)malloc(sizeof(int)*i);
	while(scanf("%d",&arr[n])!=EOF){
		n++;
	}
	MergeSort(arr,0,n-1);
	for(int i=0;i<=n;i++){
		printf("%d",arr[i]);
	}
}
           

vector也就图一乐，真要分配动态内存还得用malloc。

时间复杂度分析

总时间=分解时间+解决问题时间+合并时间。第一层时间代价为n，第二层时间代价为n/2+n/2=n……每一层代价都是cn，总共有logn+1层。所以总的时间代价为n*(logn+1).时间复杂度是O(nlogn)。