algorithm - 快速排序复杂度计算

Question

1. 如果数组的所有元素具有相同的值，则快速排序的分区返回什么值？ 我的答案：O(n^2)
2. 快速排序算法，以防数组已按要求排序。 我的答案：O(n^2)
3. 快速排序算法，以防数组已经按需求的相反顺序排序。 我的答案：O（n log n）
4. 假设用于快速排序的分区算法将元素分成 1-α 和 α，其中 0< α ≤1/2，α 是常数。推导递归关系并计算其复杂度。 我的答案：O（n log n）

请同时回答：

讨论用于分割快速排序中使用的数组的 Hoare 分区算法以及合适的示例。

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. 正确的。