xqsort.h

排序算法以及评估

//////////////////////////////////////////////////////////////////////
// 版权所有(C)  1994-2004											//
// 工程名称:	TestBed
// 文件名： 	XQSort.h
// 声明类:		CQSort<TYPE>
// 说明：    	快速排序类
//	                                                                //
// 创建日期：	2004.8.8
// 创建人：  	邓辉
// 修改记录                                                         //
// 修改日期     修改人     说明                                     //
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_XQSORT_H__5971E919_E22A_4FDA_ABA1_1EFD02A5195E__INCLUDED_)
#define AFX_XQSORT_H__5971E919_E22A_4FDA_ABA1_1EFD02A5195E__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "XISort.h"
template <class Type>
class CXQSort: public CXISort<Type> 
{
public:
	CXQSort();
	virtual ~CXQSort();
	virtual void Sort(Type* pArray, int nArray, BOOL bDesc=TRUE);
private:
	//快速排序
	void QSort(Type* pArray, int nArray, BOOL bDesc=TRUE, int nCutOff=50);
	CXQSort(const CXQSort& rhs);
	CXQSort& operator= (const CXQSort& rhs);
};

template <class Type>
CXQSort<Type>::CXQSort()
{
	
}

template <class Type>
CXQSort<Type>::~CXQSort()
{

}

template <class Type>
void CXQSort<Type>::Sort(Type* pArray, int nArray, BOOL bDesc)
{
	Reset();
	if(m_nTestMode != TESTNONE)
	{
		LARGE_INTEGER s,e,l;
		int Freq;
		QueryPerformanceFrequency (&l);
		Freq = (int) (l.QuadPart/1000000);

		QueryPerformanceCounter(&s);
		
		QSort(pArray, nArray, bDesc);
		
		QueryPerformanceCounter(&e);
		m_dTime = (double)((e.QuadPart - s.QuadPart)/Freq);
	}
	else
	{
		QSort(pArray, nArray, bDesc);
	}
}

template <class Type>
void CXQSort<Type>::QSort(Type* pArray, int nArray, BOOL bDesc, int nCutOff)
{
	if (nArray <= nCutOff)
	{
		if (nCutOff > 1) ISort(pArray, nArray, bDesc);
	}
	else
	{
		int		i=0,j=nArray;
		Type	t;
		t = *pArray; *pArray = *(pArray+(j>>1)); *(pArray+(j>>1)) = t;
		if(TESTALL == m_nTestMode)
		{
			int n;
			if (bDesc)
			{
				while (1)
				{
					n = i;
					while ((++i) < nArray  && pArray[i]>pArray[0]);
					m_dCompare  += i-n;

					n = j;
					while ((--j) > 0	   && pArray[j]<pArray[0]);

					m_dCompare  += n-j;
					if (i>=j) break;

					t = pArray[i]; pArray[i] = pArray[j]; pArray[j] = t; 
					m_dEvaluate += 3;
				}
			}
			else
			{
				while (1)
				{
					n = i;
					while ((++i) < nArray  && pArray[i]<pArray[0]);
					m_dCompare  += i-n;

					n = j;
					while ((--j) > 0	   && pArray[j]>pArray[0]);
					if (i>=j) break;
					m_dCompare  += n-j;

					t = pArray[i]; pArray[i] = pArray[j]; pArray[j] = t; 
					m_dEvaluate += 3;
				}
			}
		}
		else
		{
			if (bDesc)
			{
				while (1)
				{
					while ((++i) < nArray  && pArray[i]>pArray[0]);
					while ((--j) > 0	   && pArray[j]<pArray[0]);
					if (i>=j) break;
					t = pArray[i]; pArray[i] = pArray[j]; pArray[j] = t; 
				}
			}
			else
			{
				while (1)
				{
					while ((++i) < nArray  && pArray[i]<pArray[0]);
					while ((--j) > 0	   && pArray[j]>pArray[0]);
					if (i>=j) break;
					t = pArray[i]; pArray[i] = pArray[j]; pArray[j] = t; 
				}
			}
		}
		t = pArray[0]; pArray[0] = pArray[j]; pArray[j] = t; 
		QSort(pArray, j, bDesc, nCutOff);
		QSort(pArray+j+1, nArray-j-1, bDesc, nCutOff);
	}
}
#endif // !defined(AFX_XQSORT_H__5971E919_E22A_4FDA_ABA1_1EFD02A5195E__INCLUDED_)