我在C中实现了一个quicksort实现，并试图找出需要哪些输入才能导致更差的案例性能。
根据wikipedia：
总是以这种方式选择分区中的最后一个元素作为轴心，会导致已经排序的列表或相同元素的列表的性能较差（n^2）。
所以我试着这么做，结果是the following code。轴心始终是最后一个元素，输入是一个已经排序的列表。
为了证明复杂性确实是N ^ 2，我创建了一个全局变量，在每次迭代中增加它，然后最后打印它。
我本以为程序会打印：
Done in 64 iterations
然而，它在28次迭代中做到了。也许我对“复杂性”一词的理解是错误的？
最佳答案
在每次迭代中，列表都会缩小一个元素，因为轴心点已移动且不再计数。所以，迭代的总数是7+6+5+4+3+2+1=28。
注意，这仍然是二次的，因为它等于n*(n-1)/2。