c++ - 如何进行三个快速排序中位数的最坏情况排列

Question

<分区>

Answer 1

不幸的是，没有通用的答案，因为这取决于“三的中位数”部分的实现方式，以及“分区”步骤的实现方式。通过给它们提供大量完全相同的元素，许多人很容易陷入最坏的情况。但对于更有趣的情况，一般概念是这样的。

你从数字 1....N 和一个“相同大小的未知数组开始。你还不知道哪个数字在哪个索引中。

  1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19,20
[ A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T]

快速排序的最坏情况是选择的主元尽可能靠近一端，因此您希望将三个元素中最大(或最小)的三个元素考虑为中位数。通常(但不总是!)第一个、中间和最后一个元素。

  1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17
[19, B, C, D, E, F, G, H, I,18, K, L, M, N, O, P, Q, R, S,20]

现在我们知道，在分区步骤之后，数组可能看起来像这样，这取决于分区的实现方式:

[ S, B, C, D, E, F, G, H, I,18, K, L, M, N, O, P, Q, R,19,20]
                                                       ^ pivot

然后它将递归到 [18-R] 小节。 (它可能会也可能不会在 [20] 小节上另外递归，但我们在那里无能为力。因此我们重复该模式，将接下来的两个最大元素粘贴在剩下的末尾和中间:

[16, B, C, D, E, F, G, H,15,18, K, L, M, N, O, P, Q,17]

所以在分区之后它看起来像:

[ P, B, C, D, E, F, G, H,15, Q, K, L, M, N, O,16,18,17]
                                               ^ pivot

然后我们继续处理下一小节:

[ P, B, C, D, E, F, G, H,15, Q, K, L, M, N, O]

请注意，当我们填充“最大”元素时，我们会将数组位置(字母)替换为数字。完成后，我们将知道每个数组位置中的数字。到目前为止，我有这个:

[19, B, C, D, E, F, G, H,15,18, K, L, M, N, O, P, Q,17,19,20]

不幸的是，正如我所提到的，这在很大程度上取决于如何选择枢轴以及如何实现分区。可能存在一个您可以填写的简单模式，但我不知道它会是什么。您还会注意到，我一直将前三名的中位数放在最左边，因为这使得大多数分区实现的行为更加相似，但实际上，如果您知道分区的工作原理，最好将中位数放在最左边其他两个可能位置之一的前三名，只是为了再给它一个交换。