試題詳解

下列關於「排序 n 個數字」的敘述何者不正確？
(A) 任何只使用比較 (comparison) 來排序的演算法都需要 Ω(n log n) 的時間。
(B) 由於整數排序法 (integer sort) 的時間複雜度與數字的範圍有關，若已知此 n 個數字都是介於 1 到 n⁷ 之間的正整數，則可在 O(n⁷) 的時間複雜度完成排序，但無法在 O(n) 的時間複雜度完成。
(C) 堆疊排序法 (heap sort) 與合併排序法 (merge sort) 的時間複雜度皆為 O(n log n)。
(D) 快速排序法 (quick sort) 的時間複雜度為 O(n²)。