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