#ifndef SORT_STRATEGY_H
#define SORT_STRATEGY_H

template<class T>
class SortStrategy
{
public:
	//virtual void sort(T& container)=0;
	void swap(T& x,T& y) 
	{
		T temp=x;
		x=y;
		y=temp;
	}

	virtual void sort(T* container,int length)=0;
};

template<class T>
class SimpleSortStrategy:public SortStrategy<T>
{
public:
	//virtual void sort(T& container)=0;
	virtual void sort(T* container,int length)=0;
};

template<class T>
class QuickSortStrategy:public SortStrategy<T>
{
public:
	//virtual void sort(T& container)=0;
	virtual void sort(T* container,int length)=0;
};


template<class T>
class BubbleSort:public SimpleSortStrategy<T>
{
public:
	//void sort(T& container);
	void sort(T* container,int length);
};

template<class T>
class InsertSort:public SimpleSortStrategy<T>
{
public:
	//void sort(T& container);
	void sort(T* container,int length);
};

template<class T>
class SelectSort:public SimpleSortStrategy<T>
{
public:
	//void sort(T& container);
	void sort(T* container,int length);
};

template<class T>
class QuickSort:public QuickSortStrategy<T>
{
public:
	static const int insertum=10;
public:
	//void sort(T& container);
	void sort(T* container,int length);
private:
	void quickSort(T* container,int low,int high);
};

template<class T>
class ShellSort:public QuickSortStrategy<T>
{
public:
	//void sort(T& container);
	void sort(T* container,int length);
};

template<class T>
class HeapSort:public QuickSortStrategy<T>
{
public:
	//void sort(T& container);
	void sort(T* container,int length);
private:
	int  leftChild(const int i) { return (2 * i + 1); }
	void percDown(T x[], int i, const int n);
};

template<class T>
class MergeSort:public QuickSortStrategy<T>
{
public:
	//void sort(T& container);
	void sort(T* container,int length);
private:
	void msort(T x[], T tmp[], int left, int right);
    void merge(T x[], T tmp[], int lpos, int rpos, int rightend);
};


template<class T>
void BubbleSort<T>::sort(T* container,int length)
{
	T temp;
	for(int i=1;i<length;i++) 
		for (int j=length-1;j>=i;j--) 
			if(container[j]<container[j-1]) 
			{
				temp = container[j-1];
				container[j-1] = container[j];
				container[j] = temp; 
			} 
}


template<class T>
void InsertSort<T>::sort(T* container,int length)
{
	int i;
	int j;
	T tmp;

	for (i = 0; i < length; ++i)
	{
		tmp = container[i];            
		for (j = i; j > 0; --j)
			if (container[j - 1] > tmp)
				container[j] = container[j - 1];
			else
				break;          
		container[j] = tmp;
	}

}


template<class T>
void SelectSort<T>::sort(T* container,int length)
{
	int i,j;
	int min;
	T tmp;
	for(i=0;i<length-1;i++)
	{
		min=i;
		for(j=i+1;j<length;j++)
			if(container[j]<container[min]) min=j;
		if(min!=i)
		{
			tmp=container[i];
			container[i]=container[min];
			container[min]=tmp;
		}
	}
}

template<class T>
void QuickSort<T>::quickSort(T* container,int low,int high)
{
	int ii,jj;
	int k,j,mid=(low+high)/2;

	if(low+insertum>high) //這段代碼代表的是插入排序的算法，由于封裝的緣故，只能將代碼復制過來
	{
		T tmp;

		for (ii = low; ii < high-low+1; ++ii)
		{
			tmp = container[ii];            
			for (jj = ii; jj > 0; --jj)
				if (container[jj - 1] > tmp)
					container[jj] = container[jj - 1];
				else
					break;          
			container[jj] = tmp;
		}
	}
	else//快速排序核心算法
	{
		if(container[mid]<container[low]) swap(container[mid],container[low]);
		if(container[high]<container[low]) swap(container[high],container[low]);
		if(container[high]<container[mid]) swap(container[high],container[mid]);

		T milestone=container[mid];
		swap(container[mid],container[high-1]);
		for(k=low,j=high-1;;)
		{
			while(container[++k]<milestone);
			while(container[--j]>milestone);
			if(k<j)
				swap(container[k],container[j]);
			else
				break;
		}

		swap(container[k],container[high-1]);
		quickSort(container,low,k-1);
		quickSort(container,k+1,high);
	}
}


template<class T>
void QuickSort<T>::sort(T* container,int length)
{
	quickSort(container,1,length);
}


template<class T>
void ShellSort<T>::sort(T* container,int length)
{
    int i;
    int j;
    int nIncrement;
    T tmp;

    for (nIncrement = length / 2; nIncrement > 0; nIncrement /= 2)
    {
        for (i = nIncrement; i < length; ++i)
        {
            tmp = container[i];
            for (j = i; j >= nIncrement; j -= nIncrement)
            {
                if (tmp < container[j - nIncrement])
                    container[j] = container[j - nIncrement];
                else
                    break;
            }
            container[j] = tmp;
        }
    }

}

template<class T>
void HeapSort<T>::percDown(T x[], int i, const int n)
{
    int nChild;
    T tmp;

    for (tmp = x[i]; leftChild(i) < n; i = nChild)
    {
        nChild = leftChild(i);
        if ((nChild != n - 1) && (x[nChild + 1] > x[nChild]))
            ++nChild;
        if (tmp < x[nChild])
            x[i] = x[nChild];
        else
            break;
    }
    x[i] = tmp;
}

template<class T>
void HeapSort<T>::sort(T* container,int length)
{
    int i;

    for (i = length / 2; i >= 0; --i)    // build heap
        percDown(container, i, length);
    for (i = length - 1; i > 0; --i)
    {
        swap(container[0], container[i]);         // delete max
        percDown(container, 0, i);
    }

}


template<class T>
void MergeSort<T>::msort(T x[], T tmp[], int left, int right)
{
    int center;

    if (left < right)
    {
        center = (left + right) / 2;
        msort(x, tmp, left, center);
        msort(x, tmp, center + 1, right);
        merge(x, tmp, left, center + 1, right);
    }

}

template<class T>
void MergeSort<T>::merge(T x[], T tmp[], int lpos, int rpos, int rightend)
{
    int i;
    int leftend;
    int numelements;
    int tmppos;

    leftend = rpos - 1;
    tmppos = lpos;
    numelements = rightend - lpos + 1;

    
    while ((lpos <= leftend) && (rpos <= rightend))
    {
        if (x[lpos] <= x[rpos])
            tmp[tmppos++] = x[lpos++];
        else
            tmp[tmppos++] = x[rpos++];
    }

    while (lpos <= leftend)     // copy rest of first half
        tmp[tmppos++] = x[lpos++];
    while (rpos <= rightend)    // copy rest of second half
        tmp[tmppos++] = x[rpos++];

    // copy tmp back
    for (i = 0; i < numelements; ++i, --rightend)
        x[rightend] = tmp[rightend];

}

template<class T>
void MergeSort<T>::sort(T* container,int length)
{
    T *tmp;

    tmp = new (T[length * sizeof(T)]);
    if (NULL != tmp)
    {
        msort(container, tmp, 0, length - 1);
        delete tmp;
    }

}

#endif//~SORT_STRATEGY_H