c - 试图引起“更糟糕的情况”快速排序

Question

我在 C 中实现了一个快速排序实现，我试图找出导致更差情况性能所需的输入。

根据维基百科：

总是以这种方式选择分区中的最后一个元素作为枢轴会导致已排序列表或相同元素列表的性能不佳 (n^2)。

所以我尝试这样做，结果如下代码。枢轴始终是最后一个元素，输入是已经排序的列表。

为了证明复杂度确实是 n^2，我创建了一个全局变量，我在每次迭代中递增，然后最后打印它。

我预计该程序会打印：

Done in 64 iterations

但是，它在 28 次迭代中完成了。也许我对“复杂性”一词的理解是错误的？

Answer 1

在每次迭代中，列表都会缩小一个元素，因为枢轴被移动并且不再计算在内。因此，总迭代次数为 7+6+5+4+3+2+1 = 28。

请注意，这仍然是二次的，因为它等于n*(n-1)/2。

Answer 2

对于 n=8，迭代次数为 28。

迭代次数等于n*(n-1)/2= 8*7/2 = 28。

现在函数是f(n)=n*(n-1)/2 = n ² /2 - n/2。

f(n) = O(n 2 ^/ 2 - n/2) = O((1/2)n ² ) = O(n ² )。

因此，您的输入实际上是快速排序的最坏情况。