带 "median of three" 主元选择的快速排序：了解过程

Question

我们在 class 中介绍了快速排序（使用数组）。我已经运行陷入困境，试图围绕他们希望我们的 Quicksort 分配如何与 "median of three" 枢轴选择方法一起工作。我只需要对它的工作原理进行高级解释。我们的文字没有帮助，我很难通过谷歌搜索找到明确的解释。

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

"median of three" 函数采用 index 0（第一个）、array_end_index（最后一个）和 (index 0 + array_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){}

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

函数参数如下：

/* @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

medianOfThree 的文档说：

* 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.

所以你的描述与文档不符。您正在做的是对数据中的第一个、中间和最后一个元素就地进行排序，并始终返回中间索引。

因此，可以保证枢轴索引位于边界之间（除非中间最终位于边界内...）。

即便如此，旋转边界也没有错...

Answer 2

计算 "median of three" 是一种在数组中获取伪中值元素并使该索引等于分区的方法。这是一种粗略估计数组的中位数的简单方法，可以提高性能。

为什么这会有用？因为从理论上讲，您希望这个分区值成为数组的真正中值，所以当您对该数组进行快速排序时，主元会平分这个数组并启用快速排序的 O(NlogN) 排序时间给你。

示例：您的数组是：

[5,3,1,7,9]

三个的中位数看5、1、9，中位数显然是5，所以这就是我们要考虑的快速排序配分函数的主元值。接下来你可以做的是将这个索引与最后一个交换并得到

[9,3,1,7,5]

现在我们尝试让所有小于 5 的值都在中间左侧，所有大于 5 的值都在中间右侧。我们现在得到

[1,3,7,9,5]

将最后一个元素（我们存储分区值的位置）与中间元素交换

[1,3,5,9,7]

这就是使用 3 的中间值的想法。想象一下，如果我们的分区是 1 或 9。你可以想象我们得到的这个数组不是快速排序的好例子。

Answer 3

首先了解快速排序，然后是三中位数。

要执行快速排序，您：

从您正在排序的数组中选择一个项目（任何项目都可以，但这是我们会回来的最佳选择）。
重新排列数组，使所有小于您选择的项目在数组中位于它之前，所有大于它的都在它之后。
递归地对您选择的项目前后的集合执行上述操作。

第 2 步称为 "partition operation"。考虑一下您是否有以下情况：

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.

现在右边的9只有一个元素，显然已经排好序了。 5 7 6 留待排序。如果我们以 5 为中心，我们最终将不理会它，我们只需要将 7 6 排序为 6 7.

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

1 2 3 4 5 6 7 8 9.

所以再次总结一下，快速排序选择一个项目，移动它周围的元素，使它们都相对于那个项目正确定位，然后对剩余的两个集合递归地做同样的事情，直到没有未排序的块离开，一切都已排序。

让我们回到我说"any item will do"时在那边捏造的事情。虽然确实任何项目都可以，但您选择的项目会影响性能。如果幸运的话，您最终会在与 n log n 成比例的操作中完成此操作，其中 n 是元素的数量。如果你相当幸运，它会是一个稍大的数字，仍然与 n log n 成正比。如果你真的很不幸，它将是一个与 n².

成正比的数字

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

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

只选择第一个，因为，嗯，为什么不呢？
选择中间那个，因为也许数组已经排序或由于某种原因接近排序，如果没有，它也不是比其他任何选择更糟糕的选择。
随机选择一个。
选择第一个，中间一个和最后一个，然后取这三个选项的中位数，因为它至少会是这三个选项中最好的。
为数组的前三分之一选择三个中位数，第二个三分之一的三个中位数，最后三分之一的三个中位数，然后最后去这三个中位数的中位数。

这些有不同的优缺点，但一般来说，这些选项中的每一个在选择最佳枢轴方面都比前一个提供了更好的结果，但代价是要花费更多的时间和精力来选择那个枢轴。（随机还有一个优势，那就是在某些情况下，有人故意尝试创建您将在其上出现更坏情况行为的数据，作为某种 DoS 攻击的一部分）。

My assignment states that, in order to proceed with partitioning the array, the pivot must lie in-between the left and right boundaries.

是的。当我们将 3 排序到正确的位置并在左侧排序时，再次考虑上面的内容：

1 2 3 4 8 9 5 7 6.

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

（顺便说一句，总是选择最佳枢轴的神奇完美的枢轴选择器只会选择 6 或 7，所以在这里选择 6 非常好，尽管有时三中位数会很不走运，最终会选择第三个更差的选项，或者甚至可能是从 3 个相等的元素中任意选择，所有这些元素都更差。它发生的可能性比与其他方法）。

带 "median of three" 主元选择的快速排序：了解过程

Quicksort w/ "median of three" pivot selection: Understanding the process

c++

partitioning

quicksort

multiple-languages