//快速排序類
#include "Sorter.h"

template <class Record,class Compare>
class QuickSorter:public Sorter<Record,Compare>
{
private:
	int SelectPivot(int left, int right);//選擇軸值，返回軸值下標(biāo)
	int Partition(Record Array[], int left, int right);  //分割,返回軸值位置
public:
	void Sort(Record Array[],int left,int right);
};

//快速排序，Array[]為待排序數(shù)組，i,j分別為數(shù)組兩端
template <class Record,class Compare>
void QuickSorter<Record,Compare>::Sort(Record Array[], int left,int right) 
{
    // 如果子序列中包含0或1個(gè)記錄，就不用排序
	if (right <= left) 
		return;    
	//選擇軸值
	int pivot = SelectPivot(left, right);
	// 將軸值放在數(shù)組末端
    swap(Array, pivot, right);   
    // 對(duì)剩余的記錄進(jìn)行分割，分割后軸值已到達(dá)正確位置
    pivot = Partition(Array, left, right);
    //對(duì)分割出的子序列進(jìn)行遞歸快速排序
    Sort(Array, left, pivot-1);  //對(duì)軸值左邊的子序列進(jìn)行遞歸快速排序
    Sort(Array, pivot+1, right); //對(duì)軸值右邊的子序列進(jìn)行遞歸快速排序
}

//選擇軸值
template <class Record,class Compare>
int QuickSorter<Record,Compare>::SelectPivot(int left,int right) 
{   //參數(shù)left,right分別表示序列的左右端下標(biāo)
   //選擇中間紀(jì)錄作為軸值
	return (left+right)/2; 
}

//分割
template <class Record,class Compare>
int QuickSorter<Record,Compare>::Partition(Record Array[], int left,int right) 
{
	Record TempRecord;		//存放軸值的臨時(shí)變量
    int i = left;				// i為左指針，j為右指針
	int j = right;	
    TempRecord = Array[j];	//將軸值存放在臨時(shí)變量中
    while (i != j)  {	//開(kāi)始進(jìn)行分割，i,j開(kāi)始向中間移動(dòng)，直到相遇
       //i指針向右移動(dòng)，直到找到一個(gè)大于等于軸值的記錄
       while (Compare::lt(Array[i], TempRecord) && (j>i))
		   i++;
       // 如果i,j尚未相遇，就將逆序元素?fù)Q到右邊的空閑位置
       if (i<j)
       {  
			Array[j] = Array[i];   
			j--;	//j指針向左移動(dòng)一步
       }
       // j指針向左移動(dòng)，直到找到一個(gè)小于等于軸值的記錄
       while (Compare::gt(Array[j], TempRecord) && (j > i))  j--;
       //如果i,j尚未相遇，就將逆序元素?fù)Q到左邊的空閑位置
       if (i<j)
		{
			  Array[i] = Array[j];
			  i++;	//i指針向右移動(dòng)一步
		}
    }	//end while
    Array[i] = TempRecord;	//把軸值回填到分界位置i上
	return i;	//返回分界位置i
}