//快速排序
//算法思想：設數(shù)組a中存放了n個數(shù)據(jù)元素,;pw為數(shù)組的低端下標,high維數(shù)組的高端下標,從數(shù)組a中任取一個元素(通常取a[low])作為標準,
//調(diào)整數(shù)組a中各個元素的位置,使排在標準元素面前的元素的關(guān)鍵字均小于標準元素的關(guān)鍵字,排在標準元素后面的元素的關(guān)鍵字均大于等于
//標準元素的關(guān)鍵字。這樣一次過程結(jié)束后，一方面講標準元素放在了未來排好序的數(shù)組中該表尊元素應位于的未知上，另一方面將數(shù)組中
//的元素以標準元素為中心分成了兩個子數(shù)組,位于標準元素左邊子數(shù)組中元素的關(guān)鍵字均小于標準元素的關(guān)鍵字，位于標準元素右邊子數(shù)組
//元素的關(guān)鍵字均大于等于標準元素的關(guān)鍵字。對于這兩個子數(shù)組中的元素分別再進行方法雷同的遞歸快速排序。遞歸算法的出口條件是
//high>low;
//算法實現(xiàn):
void QuickSort(DataType a[],int low,int high)
//用遞歸方法對數(shù)據(jù)元素a[low]……a[high]進行快速排序
{
	int i=low,j=high;
	DataType temp=a[low];		//取第一個元素為標準元素

	while (i<j)
	{
		while(i<j&&temp.key<=a[j].key)	j--;		//在數(shù)組的右端掃描
		if(i<j)
		{
			a[i]=a[j];
			i++;
		}
		while (i<j&&a[i].key<temp.key)	i++;		//在數(shù)組的左端掃描
		if(i<j)
		{
			a[j]=a[i];
			j--;
		}
	}
	a[i]=temp;

	if(low<i) QuickSort(a,low,i-1);		//對左端子集合進行掃描
	if(i<high) QuickSort(a,j+1,high);	//對右端子集合進行掃描
}