我正在阅读《算法》第四版，它告诉我快速排序在最坏情况下使用 ~N^2/2 进行比较，因为 N+(N-1)+(N-2)+...+2 +1=(N+1)N/2。然而，书上还告诉我，分区的成本始终是N+1。所以我想知道为什么最坏情况的成本不是 (N+1)+(N-1+1)+(N-2+1)+...+(2+1)+0 = (N+ 1)+N+...+3=(N+4)(N-1)/2？
最佳答案
他们犯傻了？快速排序分区需要将主元与每个其他元素进行比较，这正是 N−1 次比较。在最坏的情况下，每次的主元要么是最小元素，要么是最大元素，因此总比较次数为 (N−1) + (N−2) + … + 1 + 0 = N(N−1)/2，全部成对。
关于algorithm - 为什么算法第四版中快速排序的最坏情况成本与我计算的成本不匹配？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/76333774/