22 關於快速排序法（quick sort）的敘述，下列何者錯誤？
(A)在最差情況下（worst case）的時間複雜度為 O(n2)
(B)在最佳情況下（best case）的時間複雜度為 O(n log n)
(C)基準值（pivot）的選擇與時間複雜度無關
(D)使用分而治之法則（divide and conquer）

答案：登入後查看
統計： A(38), B(43), C(244), D(53), E(0) #2574661

詳解 (共 2 筆)

#4766169
選定一個基準值(Pivot) 將比基準...
(共 257 字，隱藏中）
前往觀看
7
0
#4620391

[轉自https://alrightchiu.github.io/SecondRound/comparison-sort-quick-sortkuai-su-pai-xu-fa.html]

Quick Sort是一種「把大問題分成小問題處理」的Divide and Conquer方法，概念如下：

  • 在數列中任意挑選一個數，稱為pivot，然後調整數列，使得「所有在pivot左邊的數，都比pivot還小」，而「在pivot右邊的數都比pivot大」。
  • 接著，將所有在pivot左邊的數視為「新的數列」，所有在pivot右邊的數視為「另一個新的數列」，「分別」重複上述步驟(選pivot、調整數列)，直到分不出「新的數列」為止。

常見的Comparison Sort及其時間複雜度如表一，假設問題有NN筆資料：

    Quick Sort        Merge Sort        Heap Sort  Insertion Sort  Selection Sort  
best case    NlogNNlog⁡N       NlogNNlog⁡N       NlogNNlog⁡N           NN          N2N2
average case       NlogNNlog⁡N      NlogNNlog⁡N      NlogNNlog⁡N          N2N2          N2N2
worst case    N2N2      NlogNNlog⁡N      NlogNNlog⁡N          N2N2          N2
0
1