快速排序中的分割算法的解析與應用排序算法總結之快速排序

一，分割(partition)算法介紹

所謂分割算法，先標明一個樞軸元素，然後 将數組中的元素分成兩部分：比樞軸元素小的部分都位于樞軸元素左邊；比樞軸元素大的部分都位于樞軸元素右邊

此時，樞軸元素在數組中的位置就被“永久地确定”下來了---将整個數組排序，該樞軸元素的位置不會變化。

另外，樞軸元素的選取對分割算法至關重要。一般而言，終極追求的是：将數組平分。是以，盡可能地讓樞軸元素的選取随機化和靠近中位數。

這裡采用“三數取中”法選取樞軸元素。

關于快速排序排序算法，可參考：http://www.cnblogs.com/hapjin/p/5518922.html

二，分割算法的實作

①第4行，樞軸元素是通過“三數取中”法選擇的。在“三數取中”時，還做了一些優化：将 樞軸元素 放到 數組末尾的倒數第二個位置處。具體參考 media3()

需要注意的是：當輸入的數組中長度為1 或者 2 時， partition會出現向下越界（但對快排而言，當數組長度很小的，其實可以不用 partition，而是直接用插入排序）。是以，可加入以下的修改。

再來看看，三數取中算法，這裡也有個特殊情況：當數組中元素個數都沒有3個時....怎麼辦？

這裡提下第3-7行的兩個if語句：當需要 “取中”的目标數組長度為1時，或者說 對數組中某些範圍内[left, right]的元素進行“取中”時，若left=right，則根本就沒有3個數，違背了“三數取中”的本意（随機地選取樞軸元素），故直接 return。

當數組中元素隻有一個時，第18行會越界。為了防止這種情況，在第3-4行就先對數組長度進行判斷。當數組中隻有兩個元素，其實就相當于 center=left，是以，程式也沒問題。

三，分割算法的應用

給定一個數組，數組中某個元素出現的次數超過了數組大小的一半，找出這個元素。

比如輸入：[2,5,4,4,5,5,5,6,5] ，輸出 5

這個問題，其實可以轉化成求解中位數問題。因為，當數組有序時，出現次數超過一半的那個元素一定位于數組的中間。

所謂中位數，就是 假設 數組是有序的情況下，中間那個元素。即 arr[arr.length/2]

而要求解中位數，當然可以先對數組進行排序，但排序的時間複雜度為O(NlogN)，那有沒有更快的算法？

當然是有的。就是借助partition分割算法 來 實作。

上面算法不僅可以求解“找出超過一半的數字”，也可以求解任何一個數組的中位數。

這裡遞歸表達式 T(N)=T(N/2)+O(N)，O(N)表示将數組 分成兩部分所花的代價。

故時間複雜度為O(N)

四，參考資料

 整個完整代碼

本文轉自hapjin部落格園部落格，原文連結：http://www.cnblogs.com/hapjin/p/5587014.html，如需轉載請自行聯系原作者