我在 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 次迭代中完成了。也许我对“复杂性”一词的理解有误？
最佳答案
在每次迭代中，列表都会缩小一个元素，因为枢轴已移动且不再计数。因此，总迭代次数为 7+6+5+4+3+2+1 = 28。
请注意，这仍然是二次方，因为它等于 n*(n-1)/2。
关于c - 试图导致 "worse case"快速排序，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15728325/