#include<string.h>
//------------------------------交換樞軸兩邊數據函數--------------------------------//
int partition(node *d,int low,int high,int &jc,int &bc)
{//交換順序表d中的從low到high的子表記錄，使樞軸記錄到位，并返回其所在位置，
//此時在它之前（后）的記錄均不大（小）于它
	int pi;
	d[0].data=d[low].data;   //用子表的第一個記錄作樞軸記錄
	strcpy(d[0].c,d[low].c);
	jc++;
    pi=d[low].data;   //樞軸記錄關鍵字
	while(low<high)       //從表的兩端交替地向中間掃描
	{
		bc++;
		while(low<high&&d[high].data>=pi)
		{--high;bc++;}
			d[low].data=d[high].data;	 //將比樞軸記錄小的記錄移到低端
	      strcpy(d[low].c,d[high].c);
		  jc++;
		while(low<high&&d[low].data<=pi)
		{++low;bc++;}
         	d[high].data=d[low].data;	 //將比樞軸記錄大的記錄移到高端
	      strcpy(d[high].c,d[low].c);
		  jc++;
	}
	d[low].data=d[0].data;	    //樞軸記錄到位
	strcpy(d[low].c,d[0].c);
	jc++;
		  return low;    //返回樞軸位置
} 
//-------------------------------快速排序函數----------------------------------------//
void quicksort(node *d,int low,int high,int &jc,int &bc)
{//對順序表d中的從low到high的子列作快速排序
	int piv;
	if(low<high)       //長度大于1
	{
		bc++;
		piv=partition(d,low,high,jc,bc);  //將子列一分為二
		quicksort(d,low,piv-1,jc,bc);    //對低子表遞歸排序，piv是樞軸位置
		quicksort(d,piv+1,high,jc,bc);   //對高子表遞歸排序
	}
}