我们正在课堂上介绍快速排序（使用数组）。我一直在努力思考他们希望我们的快速排序分配如何与“三的中位数”枢轴选择方法一起工作。我只需要一个高层次的解释它是如何工作的。我们的文字没有帮助，我很难用谷歌搜索找到一个明确的解释。
到目前为止，这是我认为可以理解的：
“三的中位数”函数采用index 0(first)、array_end_index(last) 和(index 0 + array_end_index)/2(middle) 中的元素。计算具有这 3 个中值的指数。返回对应的索引。
功能参数如下：
/* @param left
* the left boundary for the subarray from which to find a pivot
* @param right
* the right boundary for the subarray from which to find a pivot
* @return
* the index of the pivot (middle index); -1 if provided with invalid input
*/
int QS::medianOfThree(int left, int right){}
然后，在“分区”函数中，索引与“三的中位数”函数返回的数字匹配的数字作为枢轴。我的作业指出，为了继续对数组进行分区，枢轴必须位于左右边界之间。问题是，我们的“三的中位数”函数返回三个索引之一：第一个、中间或最后一个索引。这三个指数中只有一个（中间）可以“介于”任何东西之间。
功能参数如下：
/* @param left
* the left boundary for the subarray to partition
* @param right
* the right boundary for the subarray to partition
* @param pivotIndex
* the index of the pivot in the subarray
* @return
* the pivot's ending index after the partition completes; -1 if
* provided with bad input
*/
int QS::partition(int left, int right, int pivotIndex){}
我有什么误解？
以下是函数的完整描述：
/*
* sortAll()
*
* Sorts elements of the array. After this function is called, every
* element in the array is less than or equal its successor.
*
* Does nothing if the array is empty.
*/
void QS::sortAll(){}
/*
* medianOfThree()
*
* The median of three pivot selection has two parts:
*
* 1) Calculates the middle index by averaging the given left and right indices:
*
* middle = (left + right)/2
*
* 2) Then bubble-sorts the values at the left, middle, and right indices.
*
* After this method is called, data[left] <= data[middle] <= data[right].
* The middle index will be returned.
*
* Returns -1 if the array is empty, if either of the given integers
* is out of bounds, or if the left index is not less than the right
* index.
*
* @param left
* the left boundary for the subarray from which to find a pivot
* @param right
* the right boundary for the subarray from which to find a pivot
* @return
* the index of the pivot (middle index); -1 if provided with invalid input
*/
int QS::medianOfThree(int left, int right){}
/*
* Partitions a subarray around a pivot value selected according to
* median-of-three pivot selection.
*
* The values which are smaller than the pivot should be placed to the left
* of the pivot; the values which are larger than the pivot should be placed
* to the right of the pivot.
*
* Returns -1 if the array is null, if either of the given integers is out of
* bounds, or if the first integer is not less than the second integer, OR IF THE
* PIVOT IS NOT BETWEEN THE TWO BOUNDARIES.
*
* @param left
* the left boundary for the subarray to partition
* @param right
* the right boundary for the subarray to partition
* @param pivotIndex
* the index of the pivot in the subarray
* @return
* the pivot's ending index after the partition completes; -1 if
* provided with bad input
*/
int QS::partition(int left, int right, int pivotIndex){}