我一直在寻找证据来证明为什么均匀分割是快速排序算法的最佳情况。我看到的每个算法分析都简单地指出“最好的情况发生在分区尽可能均匀平衡时”，但没有证明为什么均匀分割比其他任何分割都好。
显然这是真的，但我想知道为什么。我们是如何得出均匀分裂快而不均匀分裂慢的知识的？
太久没正式做这个了，就不尝试了。然而，非正式地，它实际上是关于平衡的。如果你没有将数据平均分成两半，那么一个分区比另一个分区有更多的工作要做，因此将花费比两个分支的平均值更长的时间。