資料結構›Ch7 搜尋與排序第 3 題/共 76 題
3. Quicksort、Pivot選擇
#DS-07-003易QuicksortPivot選擇
Which pivot selection strategy in Quicksort is usually the most effective at avoiding the worst-case runtime across arbitrary input distributions?
參考答案與解析
答案 (C):隨機選取樞紐,可以讓最壞情況(如已排序或反排序輸入導致的 O(n²))在期望值上被打散,因為對手(輸入資料)無法預先設計出讓「隨機」選擇都踩到最差情況的輸入,這是避免 quicksort 最壞情況最實用的標準做法。
📄 台大115
▤完整推導請見《WH 資工筆記 · 資料結構》Ch7 搜尋與排序