algorithm - 这就是三中位数快速排序的工作原理吗？

Question

我知道以前有人问过这个问题。我读过它们，但我仍然不确定我的解释是否正确。

假设我们有一个数组 [51,20,26,16,19,38,10,37,49]。

首先，我们必须选择中位数作为基准(first、last 和 middle)。

[51,19,49]

据此，49 是支点，我们将其向后移动。

接下来，划分子数组[51,20,26,16,19,38,10,37] 49.

因为 51 是大于 49 的第一个元素，而 37 是小于 49 的第一个元素，我们交换它们。

[37,20,26,16,19,38,10,51]
  ^                    ^     

重复同样的步骤。

由于 51 是第一个大于 49 但其索引大于 37 的元素，我们将主元与 51 交换。现在我们的数组如下所示:

[37,20,26,16,19,38,10,49,51]

现在 49 和 51 已排序。

然后，我们再次从 [37,20,26,16,19,38,10] 中选择枢轴:[37,16,10]。

将枢轴交换到后面: [37,20,26,10,19,38,16]查找大于 16 的元素:37

寻找小于 16 的元素:10

交换

[10,20,26,37,19,38,16]

寻找大于 16 的元素:20

寻找小于 16 的元素:10

因为 20 的索引 > 10 的索引，我会用 20 交换主元

[10,16,26,37,19,38,20]

从这里开始，我将重复从寻找中位数到划分的步骤。但是，我真的不确定这是否是正确的方法。抱歉，如果这是一篇冗长的帖子，我会尽可能具体地说明我的思考过程。有人可以告诉我我的做法是否正确吗？

Answer 1

三个中位数和分区方案、Lomuto 或 Hoare 存在差异。对于 Hoare 分区方案，三个中位数通常排序为 first、middle、last:

[51,20,26,16,19,38,10,37,49] => [19,20,26,16,49,38,10,37,51]

霍尔从左和右扫描。左边没有 >= 49 的值，所以左边的扫描在到达 49 时停止。右边的扫描在 37 处停止，因为那是第一个 <= 49 的值，所以第一次交换的结果是

[19,20,26,16,37,38,10,49,51]

继续向左扫描，直到再次达到 49。右扫描在 10 处停止。由于右索引现在 <= 左索引，它停止扫描，并且使用递归

[19,20,26,16,37,38,10]   [49,51]

注意Hoare只保证左边部分元素<= pivot，右边部分元素>= pivot。元素 == 枢轴和枢轴本身可能会在左侧和/或右侧的任何位置结束。

---

Lomuto 方案通常只从左侧扫描，通常轴在右侧。 3 的中位数仍然可以像我上面显示的那样交换，除了它会导致 first <= last <= middle。这将导致

[51,20,26,16,19,38,10,37,49] => [19,20,26,16,51,38,10,37] [49]

Lomuto 然后从左边扫描，使用两个索引，一个每次都更新，另一个索引为每个元素更新 < pivot，随着它的进行交换。这导致:

[19,20,26,16,38,10,37,51] [49]

然后枢轴与第一个元素交换 >= 枢轴，结果是:

[20,26,16,19,38,10,37] [49] [51]

---

对于Lomuto方案，可以不交换就确定3的中位数，然后将3的中位数交换到最后一个位置，这与问题相同。

[51,20,26,16,19,38,10,37,49] => [51,20,26,16,19,38,10,37] [49]

第一个分区步骤将导致:

[51,20,26,16,19,38,10,37] [49] => [20,26,16,19,38,10,37] [49] [51]