<分区>
所以我正在考试，这次考试的很大一部分将是快速排序算法。众所周知，该算法的最佳情况和实际平均情况是:O(nlogn)。最坏的情况是 O(n^2)。
至于最坏的情况，我知道如何解释:它发生在选定的主元是数组中的最小值或最大值时，然后我们将有 n quicksort 调用，这可能占用 n 时间(我的意思是分区操作)。我说得对吗？
现在是最佳/平均情况。我读过 Cormens 的书，得益于那本书，我了解了很多东西，但至于快速排序算法，他专注于如何解释 O(nlogn) 复杂性的数学公式。我只是想知道为什么是 O(nlogn)，而不是进行一些数学证明。现在我只看到一些维基百科的解释，如果我们选择一个将数组每次划分为 n/2, n/2+1 部分的枢轴，那么我们将有一个调用树depth logn，但我不知道这是不是真的，即使是这样，那为什么是 logn。
我知道网上有很多关于快速排序的资料，但它们只涉及实现，或者只是告诉我复杂性，而不是解释它。
