在每个分区中交换中间元素和第一个元素的快速排序

Question

假设我们有一个标准的双向分区快速排序算法，它始终以第一个元素为中心。然而，在快速排序的这种轻微变体中，我们首先交换第一个和中间的元素，然后以 'new' 第一个元素为中心。我的问题是，这会改变最坏情况下的 运行 时间吗？

我最初的想法是否定的，因为在每个子数组中，元素之间的相对顺序仍然是随机的，因此切换第一个和中间元素不会改变整体运行时间。但是由于我对找到最坏情况很感兴趣，所以我不确定是否有一些 'special' 数组会导致这种轻微的变体改变原始算法的最坏情况运行时间。

Answer 1

Quicksort 最坏的情况是主元总是最小值或最大值。考虑到这一点，您可以构建一个最坏情况的数组：

• [1, 2]（双元素数组中的每个元素都是最小值或最大值）
• [3, 1, 2] post-swap 产生上述
• [1, 3, 2] 预交换
• [4, 1, 3, 2] post-swap 产生上述
• [1, 4, 3, 2] 预交换
• [5, 1, 4, 3, 2] post-swap 产生上述
• [4, 1, 5, 3, 2] 预交换
• [6, 4, 1, 5, 3, 2] post-swap 产生上述
• [1, 4, 6, 5, 3, 2] 交换前
• 等等