quickmerge.cpp

在对本程序的快速排序和归并排序这两种算法的正确与否进行验证时

// QuickMerge.cpp: implementation of the CQuickMerge class.

//本程序实现快速和归并排序算法

//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "CompareSort.h"
#include "QuickMerge.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////


CQuickMerge::CQuickMerge()
{
	QTime=0;
	MTime=0;
	A=NULL;
	B=NULL;
	C=NULL;
}

CQuickMerge::~CQuickMerge()
{
	delete [] A;
	delete [] B;
	delete [] C;
	
}

void CQuickMerge::QuickSort()
{
	QuickSort(1,Size);        //调用快速排序函数
}

void CQuickMerge::QuickSort(int low,int high)
{
	if(low<high)
	{
		int mid;
		mid=Split(low,high);
		QuickSort(low,mid-1);
		QuickSort(mid+1,high);
	}
}

int CQuickMerge::Split(int low,int high)
{
	int m1,m2,mid;
	int i=low;
	int x;
	mid=(low+high)/2;
	m1=A[low];
//---------求出中间值---------------
	if(A[mid]<m1)
	{ 
		m2=m1;
		m1=A[mid];
	}
	else
		m2=A[mid];
	if(A[high]<m1)
	{
		m2=m1;m1=A[high];
	}
	else if(A[high]<m2)
		m2=A[high];
//--------------------------------
	//交换---------------
	if(m2==A[mid])
	{
		m1=A[low];
		A[low]=A[mid];
		A[mid]=m1;
	}
	else if(m2==A[high])
	{
		m1=A[low];
		A[low]=A[high];
		A[high]=m1;
	}
	//--------------
	A[0]=A[low];
	for(int j=low+1;j<=high;j++)   //划分数组
	{
		if(A[j]<=A[0])
		{
			i++;
			if(i!=j)
			{
				x=A[i];
				A[i]=A[j];
				A[j]=x;
			}
		}
	}
	x=A[low];
	A[low]=A[i];
	A[i]=x;
	x=i;
	return x;
}

void CQuickMerge::MergeSort()
{
	MergeSort(1,Size); //调用归并排序函数
}

void CQuickMerge::MergeSort(int low,int high)
{
	if(low<high)
	{
		int mid=(low+high)/2;
		MergeSort(low,mid);
		MergeSort(mid+1,high);
		Merge(low,mid,high);
	}
}

void CQuickMerge::Merge(int low,int mid ,int high)
{
	int i=low;
	int j=mid+1;
	int k=low;
	while((i<=mid)&&(j<=high))
	{
		if(B[i]<=B[j])
			C[k++]=B[i++];
		else
			C[k++]=B[j++];
	}
	while(i<=mid)
		C[k++]=B[i++];
	while(j<=high)
		C[k++]=B[j++];
	for(i=low;i<=high;i++)
		B[i]=C[i];
}