我知道最坏的情况发生在枢轴是最小或最大元素时。然后其中一个分区为空，我们对 N-1 个元素重复递归
但是它是如何计算到O(N^2)
我看了好几篇文章还是没能完全理解。
同样，最好的情况是枢轴是数组的中位数，左右部分大小相同。但是，那么值 O(NlogN) 是如何计算的
最佳答案
I understand worst case happens when the pivot is the smallest or the largest element. Then one of the partition is empty and we repeat the recursion for N-1 elements.
因此，想象一下您反复选择最差的支点；即在 N-1 的情况下，一个分区是空的，您递归 N-2 个元素，然后是 N-3，依此类推，直到到达 1。
N-1 + N-2 + ... + 1 的总和为 (N * (N - 1))/2。 (如今，学生们通常在高中数学中学习到这一点……)
O(N(N-1)/2) 与 O(N^2) 相同。您可以从 Big-O 表示法的数学定义中的第一原理推断出这一点。
Similarly, best case is when the pivot is the median of the array and the left and right part are of the same size. But, then how the value O(NlogN) is calculated.
这有点复杂。
把问题想象成一棵树:
在顶层，您将问题拆分为两个大小相等的子问题，并将 N 个对象移动到它们正确的分区中。
在第 2 级。您将两个子问题拆分为四个子子问题，并在 2 个问题中将 N/2 个对象移动到它们正确的分区中，总共移动了 N 个对象。
在底层，您有 N/2 个大小为 2 的子问题，您(名义上)将其拆分为 N 个大小为 1 的问题，再次复制 N 个对象。
显然，在每一层你都移动了 N 个对象。对于大小为 N 的问题，树的高度是 log2N。所以...有 N * log2N 个对象移动；即 O(N * log2)
但是log2N是logeN * loge2。 (又是高中数学。)
所以 O(Nlog2N) 是 O(NlogN)
关于java - 试图理解快速排序的复杂性，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40298538/