当保证分区后的常数差异时，Quicksort 的最坏情况运行时间
Worst case runtime for Quicksort when a constant difference after partition is guaranteed
我们想用标准的快速排序进行排序，我们可以保证，在调用分区方法之后，两个部分的大小差异最多是一个常数因子a。该算法最坏情况下的运行时间是多少？
分区之间的限制 size-difference，快速排序是 worst-case O(n log(n))
本质上，快速排序在每次拆分时都会遍历整个数组。因此，我们只需要考虑 worst-case 分区，以及需要多少次拆分才能将其缩小到大小 1（或 2）。
现在，如果我们保证两个部分中较大的部分至多是另一个部分的 a 倍，那么最坏的情况就是较大的部分确实总是a 倍大。
在这种情况下，快速排序中“层”的数量将等于我们必须将数组的原始大小除以 (1+a)/a 得到 1 的次数。这等于输入大小的以 (1+a)/a 为底的对数。因为a是常量，所以(1+a)/a也是常量，因此分裂量是O(log(n))，这意味着算法运行在O(n log (n)) worst-case.
我们想用标准的快速排序进行排序，我们可以保证，在调用分区方法之后，两个部分的大小差异最多是一个常数因子a。该算法最坏情况下的运行时间是多少？
分区之间的限制 size-difference，快速排序是 worst-case O(n log(n))
本质上，快速排序在每次拆分时都会遍历整个数组。因此，我们只需要考虑 worst-case 分区，以及需要多少次拆分才能将其缩小到大小 1（或 2）。
现在，如果我们保证两个部分中较大的部分至多是另一个部分的 a 倍，那么最坏的情况就是较大的部分确实总是a 倍大。
在这种情况下，快速排序中“层”的数量将等于我们必须将数组的原始大小除以 (1+a)/a 得到 1 的次数。这等于输入大小的以 (1+a)/a 为底的对数。因为a是常量，所以(1+a)/a也是常量，因此分裂量是O(log(n))，这意味着算法运行在O(n log (n)) worst-case.