資料結構與演算法
即使在最差情況下時間複雜度也是 O(n log n)，且幾乎不使用工作用陣列等額外記憶體就能排序的演算法為下列何者？
- A合併排序
- B堆積排序
- C快速排序
查看答案與解析
正確答案：B. 堆積排序
堆積排序在陣列中建立二元堆積，並反覆把根部的最大值與末尾交換、縮小堆積，因此最差也是 O(n log n)，額外空間只需常數。合併排序最差也是 O(n log n)，但在陣列上進行時需要與 n 成正比的工作空間。快速排序平均為 O(n log n)，實務上很快，但視樞紐的選法與資料而定，可能變成 O(n²)。此外，堆積排序會比較相距很遠的元素，因此快取效率差，也不是穩定排序。
- A. 最差為 O(n log n)，但在陣列上進行需要與 n 成正比的工作空間。
- B. 正確。最差也是 O(n log n)，只在陣列內部就能排序。
- C. 平均為 O(n log n)，但最差情況會變成 O(n²)。