摘要: 快速排序:確定一個樞紐元，一次遍歷后將數組劃分成兩個部分，第一部分均比樞紐元小，第二部分都比樞紐元大，然后對這兩個數組進行快速排序，是一種遞歸的方法
平均運行時間O(Nlog(N)),最壞運行時間O(N^2)
最壞情形：對于預排序的序列。
對與樞紐元相等的元素處理：
i,j都停止：會比較相等元素，但是可以劃分成長度相當的兩個子數組
i,j都不停止，不會比較相等元素，但是可能產生長度不平衡的兩個子數組(與樞紐元相等的元素較多時)樞紐元的選取：
1. 選取第一個元素做樞紐元：對于（部分）預排序的序列運行時間O(N^2)
2. 隨機生成樞紐元：能避免上述問題，但是產生樞紐元的代價高
3. 三數中值分割法：選取左端，右端，中間位置三個元素的中值
閱讀全文