快速排序的复杂性计算

Question

1. 如果数组中的所有元素具有相同的值，那么q的快分类返回的分区值是多少？ myAns：O（n^2）
2. 快速排序算法，以防数组已按照需求排序。 myAns：O（n^2）
3. 快速排序算法，以防数组已按照需求的相反顺序排序。假设用于快速排序的分区算法将元素分成1-α和α，其中0 = <α≤1/ 2，α是常数。推导递归关系并计算其复杂性。 myAns：为O（n log n）的

请回答为：

讨论用于在分份快速排序与合适的实施例中使用的阵列霍尔分区算法。

Answer 1

请指明你的问题在未来。

你需要指定你正在使用什么枢轴 - 我猜你总是使用第一个分区元素作为枢轴，在这种情况下，你的答案是2和3是正确的，但如果你使用中间分区元素或随机分区元素，那么你对2的回答将是不正确的（预期的运行时将是n log n）。

4您的答案是不正确的 - alpha需要计入您的复杂性分析。如果alpha = .5，那么复杂度是n log n，但是如果alpha = 1/n，那么复杂度是n^2。你可能应该提供你衍生的重复关系。

Answer 2

1. 取决于您实施快速排序的方式。

2. 取决于枢轴选择策略。

3. 取决于枢轴选择策略。

4. 没错。