在我们的课堂上，我们被介绍了快速排序（带有数组）。我一直在撞墙，试图理解他们希望我们的快速排序作业如何与“三的中位数”枢轴选择方法一起工作。我只需要一个关于它是如何工作的高级解释。我们的文本没有帮助，我很难在谷歌上找到一个清晰的解释。

这是我到目前为止想明白的：

三的中位数函数取index 0（第一个）、array_end_index（最后一个）和（index 0array_end_index）/2（中间）中的元素。计算具有这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){}