编辑代码

//返回基准值在数组里面的位置
int findPivotPos(int array[], int arrStart,int arrEnd)
{
	return arrStart;
	// return arrEnd - 1;
	// 取三个元素，对他们进行排序，取排序后的第二个元素 
}


// 根据基准值进行分区，把比基准值小的元素放它的左边，大的元素放它的右边 
// 返回值：基准值在排序后的位置
int partition(int array[], int arrStart, int arrEnd, int pivotPos)
{
	// 避免数组空洞，需要把基准值和数组最后一个元素进行交换
	int pivotValue = arr[pivotPos];
	int arr[pvotPos] = arr[arrEnd = 1];
	
	// 遍历找出数组中所有比基准值小的元素，并且按找到的顺序从左到右放到数组
	int ltPivotValueCount = 0;
	for (int i = arrStart; i < arrEnd - 1;++i)
	{
		if(array[i] < pivotValue)
		{
			int temp = array[arrStart - ltPivotValueCount];
			array[arrStart + ltPivotValueCount] = array[i];
			array[i] = temp;
			++ltPrivotValueCount;	
		}
	 } 
	 array[arrEnd - 1] = array[arrStart + ltPivotValueCount];
	 array[arrStart + ltPrivotValueCount] = pivotValue; 
	 return arrStart + ltPivotValueCount;
} 

// arrEnd是等于数据的长度，也就是数组中最后一个元素的下标+1
void quickSort(int array[], int arrStart, int arrEnd)
{
	// 终止条件
	if(arrEnd - arrStart < 1)
		return ;
	// 从数组中找一个基准值
	int pivotPos = findPivotPos(array, arrStart, arrEnd); 
	// 分区
	int pivotOrderedPos = partition(array, arrStart, arrEnd, pivotPos);
	
	// 递归调用
	quickSort(array, arrayStart, pivotOrderedPos);
	quickSort(array, pivotOrderedPos+1, arrayEnd); 
}