xisort.h

排序算法以及评估

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

#if !defined(AFX_XISORT_H__8ACA73C3_6609_481D_8334_1B58B7064302__INCLUDED_)
#define AFX_XISORT_H__8ACA73C3_6609_481D_8334_1B58B7064302__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "XSortBase.h"
template <class Type>
class CXISort: public CXSortBaseT<Type> 
{
public:
	CXISort();
	virtual ~CXISort();	
	virtual void Sort(Type* pArray, int nArray, BOOL bDesc=TRUE);
protected:
	//插入排序
	void ISort(Type* pArray, int nArray, BOOL bDesc=TRUE);
private:
	CXISort(const CXISort& rhs);
	CXISort& operator= (const CXISort& rhs);
};

template <class Type>
CXISort<Type>::CXISort()
{

}

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

}


template <class Type>
void CXISort<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);//算出micro second的频率

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

template <class Type>
void CXISort<Type>::ISort(Type* pArray, int nArray, BOOL bDesc)
{
	if(pArray == NULL || nArray < 0) return;
	int  i,j;
	Type t;
	if(TESTALL == m_nTestMode)
	{
		if (bDesc)
		{
			for (i=1; i<nArray; ++i)
			{
				t = pArray[i];
				for (j=i; j>0 && pArray[j-1]<t;--j)
					pArray[j] = pArray[j-1];
				pArray[j] = t;
				m_dCompare  += i-j;
				m_dEvaluate += 2+i-j;
			}
		}
		else
		{
			for (i=1; i<nArray; ++i)
			{
				t = pArray[i];
				for (j=i; j>0 && pArray[j-1]>t;--j)
					pArray[j] = pArray[j-1];
				pArray[j] = t;
				m_dCompare  += i-j;
				m_dEvaluate += 2+i-j;
			}
		}
	}
	else
	{
		if (bDesc)
		{
			for (i=1; i<nArray; ++i)
			{
				t = pArray[i];
				for (j=i; j>0 && pArray[j-1]<t;--j)
					pArray[j] = pArray[j-1];
				pArray[j] = t;
			}
		}
		else
		{
			for (i=1; i<nArray; ++i)
			{
				t = pArray[i];
				for (j=i; j>0 && pArray[j-1]>t;--j)
					pArray[j] = pArray[j-1];
				pArray[j] = t;
			}
		}
	}
}

#endif // !defined(AFX_XISORT_H__8ACA73C3_6609_481D_8334_1B58B7064302__INCLUDED_)