用快速排序（Quick sort）來排序，並以第一個元素為基準（Pivot），下列那個數列所需排序時間最長？

題目

用快速排序（Quick sort）來排序，並以第一個元素為基準（Pivot），下列那個數列所需排序時間最長？ A. 5 4 3 2 1 6 B. 5 6 1 2 3 4 C. 6 5 4 3 2 1 D. 6 1 2 3 4 5

官方答案

• 答案：C. 6 5 4 3 2 1

解析

快速排序以首元素為基準（pivot）時，若數列已遞減排序，每次分割均將最大者與其餘 n−1 個放同一側，造成最不平衡的 n−1 與 0 分割，遞迴深度達 n−1 層，比較次數約 n(n−1)/2 為最壞情況。C『6 5 4 3 2 1』完全遞減，每輪 pivot 皆為當前最大，分割最失衡，耗時最長（約 15 次比較），故選 C。A 因末項 6 大於 pivot 會先獨立成側，較 C 略佳。

AI 參考解析（推得答案已與官方答案比對一致），非官方公告內容，僅供備考參考。

官方資料

• 官方試題 PDF
• 官方答案 PDF

答案以考選部公告之測驗式試題標準答案 PDF 為準。