23 將 1 至 n 的 n 個整數以某種初始順序存入一個陣列中，並加以排序。以下敘述何者錯誤？
(A)若以堆積排序法（heap sort）來排序，其第一個步驟需先將陣列中的數值位置加以調整，使陣列成 為一個堆積，此步驟的運算時間複雜度為 O(n)
(B)不管陣列中數值的初始排列狀況如何，合併排序法（merge sort）的運算時間複雜度均為 O(n log n)
(C)不管陣列中數值的初始排列狀況如何，快速排序法（quick sort）的運算時間複雜度均為 O(n log n)
(D)存在一種運算時間複雜度低於 O(n log n)的排序法，可將這個陣列中的數值加以排序

答案：登入後查看
統計： A(6), B(18), C(68), D(13), E(0) #1218243

詳解 (共 2 筆)

#1343150
快速有兩種可能的大O
O(n^2), 但平均情況時, 時間複雜度為O(nlogn)
1
0
#4756018

quicksort 是一個非常熱門且應用廣泛的排序法，相對簡單的實作就可達到 O(nlogn)O(nlog⁡n) 的平均時間複雜度。雖然最差時間複雜度與 bubble sort 同為 O(n2)O(n2)，但這種情形非常少見。簡單的最佳化實作下，Quicksort 僅需 O(logn)O(log⁡n) 的額外儲存空間，比它的競爭對手 mergesort 來得節省。非常適合運用在真實世界中的排序法。

 

來自 <https://rust-algo.club/sorting/quicksort/> 

0
0