merge sort.cpp

经典算法实现

#include "Sort.h"

/*extern int  *arr;
extern int num;*/

void Madjust(int start,int end,int media){//media 是第二组的第一个

	if (start>=media)
	{	return;
	}

	if (end==start+1)
	{
		if (arr[start]>arr[end])
		{
			swap(arr[start],arr[end]);
			return;
		}
	}

	int length1 = media -start;
	int length2 = end-media+1;
/*	int lengthM; 
	bool longM;
	longM=  length1>length2?0:1;

	if (longM)
	{
		lengthM =length2;
	}

	else lengthM =length1;*/

	//int* temp1 = new int [length1+1];
	//int*temp2 =new int[length2+1];
	int *temp1 =new int [length1];
	int *temp2 = new int [length2];

	for(int i=0;i<length1;i++){
		temp1[i] = arr[start+i];
	}
	//temp1[length1] =MAX;

	for(int i=0;i<length2;i++){
		temp2[i]=arr[media+i];
	}

	//temp2[length2] = MAX;

	int i=0 ,j=0;

	for (int index=0;index<length1+length2;index++)
	{
		if (i<length1 && j<length2)
		{
			if (temp2[j]<temp1[i])
			{
				arr[start+index] =temp2[j++];
			}

			else {
				
				arr[start+index] =  temp1[i++];
			}

		}

		else if (i<length1	)
		{
			for (;i<length1;i++,index++)
			{
				arr[start+index] = temp1[i];
			}

		} 
		else
		{
			for (;j<length2;j++,index++)
			{
				arr[start+	index] =temp2[j];
			}
		}

	}
	delete [] temp1;
	delete []temp2;
//	Madjust();
//	Madjust();

}

void MergeSort(int start ,int end){
	if (start >=end)
		return;

	int  part=(end+start+1)/2;

	MergeSort(start,part-1);
	MergeSort(part,end);
	Madjust(start,end,part);
}

/*void MergeSort(){


}*/