c - 试图导致 "worse case"快速排序

Question

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

根据 wikipedia :

always choosing the last element in the partition as the pivot in this way results in poor performance (n^2) on already sorted lists, or lists of identical elements.

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

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

我期望程序会打印:

Done in 64 iterations

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

Answer 1

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

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