快速排序最坏情况

Question

我在网上搜索了一下，但没有找到太多，我的问题是关于一个维度为 n 的输入，快速排序算法中出现最坏情况的概率是多少）。我知道这非常罕见，但我想知道从数字上讲它有多少，我们如何评估它。谢谢

Answer 1

快速排序的最坏情况是所选元素（轴）始终是剩余集合中的 smallest/biggest 个元素。

要生成这样的序列 - 你需要递归地工作，每一步在你最后一个枢轴的两侧创建两个数组，其中先前选择的枢轴是最大的或最小的，所以 QS 的递归算法将数组拆分为一侧为 0 的最坏情况。