快速排序的複雜性計算

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. 沒錯。