【評論主題】22 關於快速排序法（quick sort）的敘述，下列何者錯誤？(A)在最差情況下（worst case）的時間複雜度為 O(n2) (B)在最佳情況下（best case）的時間複雜度為 O(n

【評論內容】

[轉自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...

【評論主題】22 關於快速排序法（quick sort）的敘述，下列何者錯誤？(A)在最差情況下（worst case）的時間複雜度為 O(n2) (B)在最佳情況下（best case）的時間複雜度為 O(n

【評論內容】

[轉自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...