/*交换函数:为了提高效率，当所交换的两个元素值不相等时，用异或运算*/
void swap(int *a, int *b)
{
	if (*a != *b){
		*a = *a^*b;
		*b = *a^*b;
		*a = *a^*b;
	}
	else{
		int temp = *a;
		*a = *b;
		*b = temp;
	}
}

/*第一种快排：只有一个长度n,每次需计算出low和high指针*/
int QuickSort_process1(int *a, int n)
{
	int low, high, temp;
	low = 0;
	high = n - 1;
	temp = a[0];
	while (low < high){
		while (low < high&&temp <= a[high])
			--high;
		if (low < high)
			a[low] = a[high];
		while (low<high&&temp>a[low])
			++low;
		if (low < high)
			a[high] = a[low];
	}
	a[high] = temp;
	return high;
}
void QuickSort1(int *a,int n)
{
	int pos;
	if (n>0){
		pos = QuickSort_process1(a, n);
		QuickSort1(a, pos);
		QuickSort1(a + pos + 1, n - pos - 1);
	}
}

/*第二种快排：有两个指针，一个快，一个慢。快的指针找比基元素小的数，慢的指针指向比基元素小的最后一个元素*/
/*这样，在排序结束后，整个数组就被基元素分为了两部分。*/
int QuickSort_process2(int *a, int n)
{
	int first, second, temp;
	first = 0;
	second = -1;
	temp = a[n - 1];
	while (first != n){
		if (a[first] < temp){
			swap(a+second+1,a+first);
			++second;
		}
		++first;
	}
	swap(a + second + 1, a + n - 1);
	return second + 1;
}

void QuickSort2(int *a, int n)
{
	int pos;
	if (n > 0){
		pos = QuickSort_process2(a,n);
		QuickSort2(a, pos);
		QuickSort2(a + pos + 1, n - pos - 1);
	}
}

/*第三种快排，比较传统的那种，参数中有low指针和high指针*/
int QuickSort_process3(int *a, int low, int high)
{
	int l, h, temp;
	l = low;
	h = high;
	temp = a[low];
	while (l < h){
		while (l< h&&a[h] >= temp)
			--h;
		if (l < h)
			a[l] = a[h];
		while (l < h&&a[l] < temp)
			++l;
		if (l < h)
			a[h] = a[l];
	}
	a[h] = temp;
	return h;
}

void QuickSort3(int *a, int low,int high)
{
	int pos;
	if (low < high){
		pos = QuickSort_process3(a,low,high);
		QuickSort3(a,low,pos-1);
		QuickSort3(a,pos+1,high);
	}
}