Quicksort Q：有限多个不同的键

Question

需要证明具有特殊分区的快速排序，其中一个数组被分成 3 个部分（< 比 3 个主元，= 到主元，> 比主元）和一个大小为 N 的特殊数组，其中只有 7 个不同的键是可能的可以在 O(N) 中排序。

所以，我想我们可以假设在中间某处选择了枢轴（否则我们可以有类似 [0, 1, 2, 3, 4, 5, 6, 6, 6, 6, . ....] 并且应该采用 O(N^2))。

这是我的想法：
假设我们进行了第一次分区。现在我们进入递归步骤 2。假设我们只关注正确的分区。由于这里的每个元素都大于枢轴，并且只有 7 个不同的键，因此该分区中的不同键的数量严格小于 7。这意味着在算法迭代 7 次后，左右子中的所有元素-sub-...-分区应该相同。

现在，如果算法停止在常量数组上重复出现，我可以看到这将是 O(N)，但我的理解是事实并非如此。如果不是这样，请澄清这一点。

这是怎么回事？

Answer 1

快速排序算法如下所示：

quicksort(A, lo, hi):
  if lo < hi:
    p := partition(A, lo, hi)
    quicksort(A, lo, p - 1)
    quicksort(A, p + 1, hi)

我们有一个特殊的三向分区，所以让我们说它 returns 它选择的任何枢轴的相等范围，我们只需要低于和高于它：

quicksort(A, lo, hi):
  if lo < hi:
    p1, p2 := 3-way-partition(A, lo, hi)
    quicksort(A, lo, p1 - 1) // (1)
    quicksort(A, p2 + 1, hi) // (2)

现在，考虑最坏的情况。我们有一个看起来像 [0,1,2,3,4,5,6,6,6,6...] 的数组，我们的主元选择算法尽可能地愚蠢：它以严格递增的顺序选择主元。在这种情况下，第一个递归调用（上面的 (1)）将始终不执行任何操作，因为不会有比主元更小的东西。所以我们只处理一个递归调用——大小为 N - 1。

每次递归调用都会将问题大小减一，直到第 7 次递归调用（它将选择 6 主元）——第 7 次递归调用完成排序。这是只有 7 个不同键的关键步骤 - 您最多只需要 7 个调用。这 7 次调用中的每一次都会迭代整个数组……即 O(7N) == O(N)。更一般地说，如果只有 k 个不同的键，你可以说最坏的情况是来自同一个参数的 O(kN)。

Quicksort Q：有限多个不同的键

Quicksort Q: Finitely many distinct keys

c++

java

sorting

computer-science

quicksort