二分歸并排序

二分歸并排序初見

問題：對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)。