快速排序

快速排序是一種基于分治思想的算法，它不穩定，最壞情況為O（n^2），但實踐證明快速排序算法是這麼多算法中平均運作時間比較優秀的，也是很多庫函數所采用的算法，比如STL的qsort用的就是快速排序實作的。

快速排序的核心思想：選出一個主元（pivot），然後以主元為基準劃分出兩撥，一撥小于主元，一撥大于或等于主元。但在每一撥裡，元素的順序是沒有保證的，然後再把子序列繼續同樣處理，直到最後子序列中剩下一個元素時，不再繼續遞歸，最終排序完成。

@1：選擇主元，也就是劃分的基準。采用最右或是最左都可以。

@2：i這個變量在整個過程中指向的位置：小于主元的那一撥裡的最後一個元素的位置，在非遞減排序中（本例如此），小于主元的在左側

@3：快速排序是不穩定的，@3代碼中的（<或是<=）會影響到快速排序的遞歸樹模型，如果用（<），則j所指向的元素和i指向的元素相同且i不會增加，也不會交換；如果用（<=），則i會右移并且交換。

@4：i變量的指向增加，并且後面三行代碼交換

@5：這兩行代碼是把主元安插在合适的位置，因為主元在最右側，且大于或等于主元的一撥靠右側，是以主元要和右側一撥中的第一個交換（僅适用于非遞減排序+最右選為主元）。

@6：主元的最後位置是在i+1處，此位置為分割的兩撥的分割點。

@7：在遞歸控制的判斷條件中，隻有一個元素時停止遞歸，這一點和歸并相似。

@1：當子序列足夠小的時候，用直接插入排序要比繼續遞歸下去更合适。至于以多少個子序列元素為準，這個可以随意定，但不能過大。

這個改進是在每一次遞歸到足夠小時，就就地直接插入排序，然後傳回。

這個改進和上個改進相比，有一個優化的地方：當遞歸到足夠小的子序列時，不排序而是直接傳回。當調用完遞歸後，在整個序列上應用直接插入排序，由于遞歸後序列的有序度已經很高了，是以這個直接插入排序會很快。

這個partition函數的思路：從左右兩側往中間并行推進，i左側是小于主元的區間，j右側是大于或等于主元的區間。i和j之間的是還未被處理的區間。

@1：先調用median3函數，取左，中，右三個值的中值，并把其放到數組的最右邊。更科學的選取主元

@2：選取主元

@3：最外層循環使用死循環，在整個循環中，i和j滿足某個條件會跳出循環

@4：i從左到右，遇到比主元小的直接continue，直到遇到一個比主元大的（或是i和j相遇），跳出小循環

@5：j從右到左，遇到比主元大于或等于的直接continue，直到遇到一個小于主元的（或是i和j相遇），跳出小循環

@6：當兩個小循環都結束後，i指向一個大于主元的，j指向一個大于或等于主元的，然後i和j所指位置的元素互換，然後i和j分别移動一個位置

@7：如果（i < j）不成立，則一定是i和j相遇，那麼一趟劃分結束

@8：最後相遇的位置i或j就是分割點，如果這個點的元素比主元大（一般都要大，除非相等），交換。

@9：最後把分割點傳回