main.cpp

包括快速排序

#include <iostream>
using namespace std;

int* QuickSort(int *p,int start,int end){
		cout<<"input array:"<<endl;
		int i;
		for(i=start;i<=end;i++)
		cout<<p[i]<<endl;

	int head=p[start],first=start+1,last=end;
	if(start>=end){
		return p;
	}else if((end-start)==1){
		if(p[start]>p[end])
			swap(p[start],p[end]);
		return p;
	}else{
		while(first<last){
			while(p[first]<head) first++;
			while(p[last]>head) last--;
			swap(p[first],p[last]);   //swap p[first] p[last]

		}
		swap(p[first],p[last]);
		swap(p[start],p[last]);
		QuickSort(p,start,last-1);
		QuickSort(p,last+1,end);
	}
	return p;

}

int* MergeSort(int* p ,int start,int end){
		cout<<"input array:"<<endl;
		int i;
		for(i=start;i<=end;i++)
		cout<<p[i]<<endl;
		
		if(end<=start){
			return p;
		}else if((end-start)==1){
			if(p[start]>p[end])
				swap(p[start],p[end]);
			return p;
		}else{
			int *backarr=new int[end+1];
			int i=0;
			for(i=0;i<=end;i++){      //paste array
				backarr[i]=p[i];
			}
			int mid=(start+end)/2;
		
			int *result1=MergeSort(p,start,mid);
			int *result2=MergeSort(p,mid+1,end);

			int p1=start,p2=mid+1,tmp=start;
			while((p1<=mid)&&(p2<=end)){
				if(result1[p1]<=result2[p2]){
					backarr[tmp++]=result1[p1];
					p1++;
				}else{
					backarr[tmp++]=result2[p2];
					p2++;
				}
			}
		


			cout<<"procedure:"<<endl;
				for(i=start;i<=end;i++)
					cout<<p[i]<<endl;
			if(p1>mid){
				for(i=p2;i<=end;i++){
					backarr[tmp++]=result2[i];
				}
			}else if(p2>end){
				for(i=p1;i<=mid;i++){
					backarr[tmp++]=result1[i];
				}
			}
				return backarr;

		}
		/*	cout<<endl;
			cout<<"output array:"<<endl;
			for(i=0;i<10;i++)
			cout<<p[i]<<endl;*/




}


int *HeapSort(int *p,int start,int end){
	int boundry=end-start+2;
	int i=0,j=0;
	int *backarr=new int[boundry];

//	cout<<"input data:"<<endl;
	for(i=start,j=1;i<=end;i++,j++){
	//	cout<<p[i]<<endl;
		backarr[j]=p[i];
	}

	if(end<=start){
		return backarr;
	}else if((end-start)==1){
		if(backarr[1]>backarr[2])
			swap(backarr[1],backarr[2]);
		return backarr;
	}else{


	int mid=(boundry)/2;
	int i=0,j=0;
	i=mid;
	while(i!=0){
		j=i;
		while(j<=mid){
			int dleft=2*j,dright=2*j+1;
			if(dright<boundry){
				if(backarr[dright]<backarr[dleft])
					swap(backarr[dright],backarr[dleft]);
			}
			if(dleft<boundry){                    //这里要小心，我开始时候发现有－318220233类似的数据，
												 //原来是这里当循环的时候要判断是否越界，免得把界限以外的数据换进来。
				if(backarr[j]>backarr[dleft]){
					swap(backarr[j],backarr[dleft]);
					j=dleft;
				}else{
					break;
				}
			}else{
				break;
			}

		}

		i--;
	}
	cout<<"select minimum data:"<<backarr[1]<<endl;

	int *tmp=HeapSort(backarr,2,boundry-1);

	for(i=2,j=1;i<boundry;i++,j++)
		backarr[i]=tmp[j];

/*	cout<<"after buildheap:"<<endl;

	for(i=1;i<boundry;i++)
		cout<<backarr[i]<<endl;*/
	return backarr;
	}

}




void swap(int i,int j){
	int tmp;
	tmp=i;
	i=j;
	j=tmp;
	return;
}

void main(){
	int a[10]={33,81,92,43,31,65,57,26,75,10};

	//int *b=QuickSort(a,0,9);      //快速排序
	//int *b=MergeSort(a,0,9);		//归并排序
	int *b=HeapSort(a,0,9);			//堆排序
	cout<<endl;
	cout<<"output array:"<<endl;
	int i=1;
	for(i=1;i<11;i++)
		cout<<b[i]<<endl;

}