// Sort.h:interface for the CSort class.
//
/////////////////////////////////////////////////////////////////////////////

#if !defined(AFX_SORT_H__A188801C_AC96_4A65A800_119AE5E5C08F__INCLUDED_)
#define AFX_SORT_H__A188801C_AC96_4A65A800_119AE5E5C08F__INCLUDED_

#IF _MSC_VER > 1000

#pragma once
#endif // _MSC_VER > 1000

template <class T>
class CSort
{
	public:
		CSort(int nArraySize);
		virtual ~CSort();

		void Bubble(T array[]);              //冒泡排序
		void Insertion(T array[]);
		void Quick(T array[],int nLeftLimit,int nRightLimit);
		void Selection(T array[]);
	private:
		int m_nArraySize;
};

template <class T>
CSort<T>::CSort(int nArraySize)
{
	if(nArraySize<0)
		m_nArraySize=0;
	else
		m_nArraySize=nArraySize;
}

template <class T>
CSort<T>~CSort()
{
}
template <class T>
CSort<T>::Bubble(T array[])
{
	T temp;
	int nLast=m_nArraySize-1;
	BOOL bSorted=TRUE;

	do {
		bSorted=TRUE;
		for(int i=0;i<nLast;i++)
		{
			//如果前一个元素比后一个元素大，则交换两个元素
			if (array[i]>array[i+1]) {
				temp=array[i];
				array[i]=array[i+1];
				array[i+1]=temp;
				bSorted=FALSE;
			}
		}
		nLast--;
	} while(!bSorted);
}

template <class T>
void CSort<T>::Insertion(T array[])
{
	T cVal;   //current value being examined

	for(int i=1;i<m_nArraySize;i++)
	{
		cVal=array[i];
		for(int n=i-1;n>0&&cVal<array[n];n--)
		{
			array[n+1]=array[n];
		}
		array[n+1]=cVal;
	}
}

template <class T>
void CSort<T>::Quick(T array[],int llimit,int rlimit)
{
	T temp;
	int nLeft=llimit;
	int nRight=rlimit;
	int pivot=(nLeft+nRight)/2;
	T nMedian=array[pivot];

	do {
		while ((array[nLeft]<nMedian)&&(nLeft<rlimit)) {
			nLeft++;
		}
		while ((nMedian<array[nRight])&&(nRight>llimit)) {
			nRight--;
		}
		if (nLeft<=nRight) {
			//交换元素
			temp=array[nRight];
			array[nLeft]=array[nRight];
			array[nRight]=temp;
			nLeft++;
			nRight--;
		}
	} while(nLeft<=nRight);
	if (llimit<nRight) {
		CSort<T>::Quick(array,llimit,nRight);
	}
	if (nLeft<rlimit) {
		CSort<T>::Quick(array,nLeft,rlimit);
	}
}

template <class T>
void CSort<T>::Selection(T array[])
{
	T temp;
	int min;
	for(int i=0;i<m_nArraySize-1;i++)
	{
		min=i;
		for(int n=i-1;n<m_nArraySize;n++)
		{
			if (array[n]<array[min]) {
				min=n;
			}
		}
		temp=array[min];
		array[min]=array[i];
		array[i]=temp;		
	}
}

#endif   //!defined(AFX_SORT_H__A188801C_AC96_4A65A800_119AE5E5C08F__INCLUDED_)