//分界值切分

//挖坑法:

int PartSortWakeng(int *a, int begin, int end)

{

	//挖空第一个值作为分界值

	int tmp = a[begin];

	while (begin<end)

	{

		//右指针碰到小于基准值,填坑,原位置变坑

		while (begin < end && a[end] >= tmp)

		{

			--end;

		}

		a[begin] = a[end];

		//左指针碰到大于基准值,填坑,原位置变坑

		while (begin<end && a[begin] <= tmp)

		{

			++begin;

		}

		//填右坑

		a[end] = a[begin];

	}

	//将基准值填到坑里

	a[begin] = tmp;

	return tmp;     //返回分界值位置

}

//快排：1.找到分界值 2.切分成三部分 3.对于剩下两部分进行上述操作

void QuickSort(int *a, int left,int right)

{

	//终止条件: 待排序部分只剩一个或没有元素了,已经有序

	if (left >= right)

	{

		return;

	}

       //分界值切分

	int div = PartSort(a, left, right);

       //剩余部分重复操作

	QuickSort(a, left, div - 1);

	QuickSort(a, div + 1, right);

}