DS 图解快排

//分界值切分
//挖坑法:
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);
	
}