快速排序的時間複雜度變成 O(n²) 的典型情況為下列何者？

正確答案：C. 資料已排序，且總是以開頭元素為樞紐的情況

快速排序把元素分成小於樞紐與大於樞紐的部分，再對各部分繼續分割。若資料已排序又總是以開頭為樞紐，每次樞紐都是最小值，分割會偏成「0個與其餘全部」，因此比較次數為 n(n−1)/2 次（n = 100 時為4,950次）。若隨機選擇樞紐，或取3個值的中位數，持續發生偏斜分割的可能性就非常小。資料個數與時間複雜度無關。

• A. 隨機選擇時，持續偏斜分割的可能性非常小，平均為 O(n log n)。
• B. 個數是否為2的冪次，與分割是否偏斜無關。
• C. 正確。每次樞紐都是最小值，分割極度偏斜。