QuickSort - 枢轴始终处于中间位置时的最坏情况输入示例
QuickSort - Worst case input example when pivot is in the middle position always
如果我在中间位置选择枢轴，QuickSort 的最坏输入示例可能是什么？我正在考虑像 3、3、3、3 等元素一样的元素。或者它是否可以将它视为最坏的情况，即使它已经排序？
快速排序的最坏情况是枢轴位于任一端。所以让他们按排序到达是最坏的情况。
长度为 1 的唯一情况是 1 所以这也是最坏的情况。
否则我们只是将每个值递增 1，然后将 1 插入第一个主元。给我们 1 作为支点，之前最坏的情况作为我们的下一个。
因此，如果我们选择位置 floor(length/2) 处的元素作为我们的支点，这里有一些以这种方式生成的最坏情况输入。
1
2 1
3 1 2
4 2 1 3
5 3 1 2 4
6 4 2 1 3 5
一般来说，长度 n 是
n n-2 n-4 ... (1 2 or 2 1 as appropriate) ... n-5 n-3 n-1
请注意，这不是唯一的最坏情况。事实上，对于每个支点，它可以在任何一端并且仍然是最坏的情况。这意味着对于 n-1 个枢轴，我们可以做出选择，使 1..n 的 2^(n-1) 次序同样糟糕。
如果我在中间位置选择枢轴，QuickSort 的最坏输入示例可能是什么？我正在考虑像 3、3、3、3 等元素一样的元素。或者它是否可以将它视为最坏的情况，即使它已经排序？
快速排序的最坏情况是枢轴位于任一端。所以让他们按排序到达是最坏的情况。
长度为 1 的唯一情况是 1 所以这也是最坏的情况。
否则我们只是将每个值递增 1，然后将 1 插入第一个主元。给我们 1 作为支点，之前最坏的情况作为我们的下一个。
因此，如果我们选择位置 floor(length/2) 处的元素作为我们的支点，这里有一些以这种方式生成的最坏情况输入。
1
2 1
3 1 2
4 2 1 3
5 3 1 2 4
6 4 2 1 3 5
一般来说，长度 n 是
n n-2 n-4 ... (1 2 or 2 1 as appropriate) ... n-5 n-3 n-1
请注意，这不是唯一的最坏情况。事实上，对于每个支点，它可以在任何一端并且仍然是最坏的情况。这意味着对于 n-1 个枢轴，我们可以做出选择，使 1..n 的 2^(n-1) 次序同样糟糕。