带“三中位数”主元选择的快速排序：了解过程

Question

我们将在课堂上介绍快速排序（使用数组）。我一直在尝试解决他们希望我们的快速排序作业如何与“三中位数”枢轴选择方法配合使用的问题。我只需要一个关于这一切如何运作的高级解释。我们的文字没有帮助，我很难在谷歌上找到清晰的解释。

这是我认为到目前为止所理解的：

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){}

然后，在“partition”函数中，索引与“median of Three”函数返回的数字相匹配的数字作为主元。我的作业指出，为了继续对数组进行分区，枢轴必须位于左右边界之间。问题是，我们的“三个中位数”函数返回三个索引之一：第一个、中间或最后一个索引。这三个索引中只有一个（中间）可以是任何东西的“中间”。

功能参数如下：

/* @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){}

Answer 1

首先从理解快速排序开始，然后是三中位数。

要执行快速排序，您：

1. 从您正在排序的数组中选择一个项目（任何项目都可以，但哪个是最好的项目，我们将在后面讨论）。
2. 重新排序数组，使数组中所有小于您选择的项目的项目都位于该项目之前，而所有大于该项目的项目都位于该项目之后。
3. 对您选择的项目之前和之后的集合递归地执行上述操作。

步骤2称为“分区操作”。考虑一下您是否有以下情况：

3 2 8 4 1 9 5 7 6

现在假设您选择了其中的第一个数字作为枢轴元素（我们在步骤 1 中选择的那个）。应用第 2 步后，我们最终会得到如下结果：

2 1 3 4 8 9 5 7 6

该值3现在位于正确的位置，并且每个元素都位于其正确的一侧。如果我们现在对左侧进行排序，我们最终会得到：

1 2 3 4 8 9 5 7 6.

现在，让我们只考虑它右侧的元素：

4 8 9 5 7 6.

如果我们选择4下一步转动，我们最终不会改变任何东西，因为它一开始就处于正确的位置。它左侧的元素集是空的，因此这里无需执行任何操作。我们现在需要对集合进行排序：

8 9 5 7 6.

如果我们使用 8 作为主元，我们最终会得到：

5 7 6 8 9.

它右边的now9只有一个元素，所以显然已经排序了。留下5 7 6来排序。如果我们以 为中心，5我们最终会不管它，我们只需要对 进行7 6排序6 7。

现在，考虑到更广泛背景下的所有这些变化，我们最终得到的是：

1 2 3 4 5 6 7 8 9.

因此，再次总结一下，快速排序选择一个项目，移动它周围的元素，以便它们都相对于该项目正确定位，然后对剩余的两组递归执行相同的操作，直到没有未排序的块，并且一切都已完成已排序。

让我们回到我刚才说“任何项目都可以”时捏造的事情。虽然任何项目都可以，但您选择的项目都会影响性能。如果幸运的话，您最终将在与 n log n 成比例的操作中完成此操作，其中 n 是元素的数量。如果你足够幸运的话，它会是一个稍大的数字，但仍与 n log n 成正比。^{如果你真的很不幸，它将是一个与 n 2}成正比的数字。

那么哪个是最好的选择呢？最好的数字是完成分区操作后最终位于中间的项目。但我们不知道那是什么项目，因为要找到中间的项目，我们必须对所有项目进行排序，这就是我们首先要做的。

因此，我们可以采取一些策略：

1. 就选择第一个，因为，呃，为什么不呢？

2. 选择中间的一个，因为也许由于某种原因数组已经排序或接近排序，如果没有，它也不比任何其他选择更糟糕。

3. 随机选择一个。

4. 选择第一个、中间一个和最后一个，然后选择这三个选项的中间值，因为它至少是这三个选项中最好的。

5. 选择数组的前三分之一的三中位数，第二个三分之一的三中位数，最后三分之一的三中位数，然后最后选择这三个中位数的中位数。

这些都有不同的优点和缺点，但一般来说，这些选项在选择最佳枢轴方面比前一个选项提供了更好的结果，但代价是花费更多的时间和精力来选择该枢轴。（随机的另一个优势是，可以击败某些情况，即有人故意尝试创建数据，而这些数据将导致最坏情况的行为，作为某种 DoS 攻击的一部分）。

我的作业指出，为了继续对数组进行分区，枢轴必须位于左右边界之间。

是的。当我们排序3到正确的位置并对左侧进行排序时，再次考虑上面的情况：

1 2 3 4 8 9 5 7 6.

现在，我们需要对范围进行排序4 8 9 5 7 6。边界是和 之间的线以及和数组末尾之间的线（或者以另一种方式看待它，边界是 4 和 6，但它是包含这些项的包容性边界）。因此，我们选择的三是（第一个）（最后一个），或者是或取决于我们在将计数除以2时向上还是向下舍入（我们可能像整数除法中通常的那样向下舍入）。所有这些都在我们当前正在排序的分区的边界内。因此，我们的中位数为三（或者如果我们四舍五入，我们就会选择）。3464695965

（顺便说一句，一个神奇的完美枢轴选择器总是选择最好的枢轴，只会选择 或6，7所以这里的选择6相当不错，尽管有时三中位数会不走运并最终选择第三个更差的选择，或者甚至可能是从 3 个相同元素中任意选择，所有这些都更差。与其他方法相比，这种情况发生的可能性要小得多）。