快速排序算法QuickSort

快速排序法（quicksort）是目前所公認最快的排序方法之一（視解題的對象而定），雖然快速排序法在最差狀況下可以達O(n2)，但是在多數的情況下，快速排序法的效率表現是相當不錯的。快速排序法的基本精神是在數列中找出适當的軸心，然後将數列一分為二，分别對左邊與右邊數列進行排序，而影響快速排序法效率的正是軸心的選擇。這邊所介紹的第一個快速排序法版本，是在多數的教科書上所提及的版本，因為它最容易了解，也最符合軸心分割與左右進行排序的概念，适合對初學者進行講解。

這邊所介紹的快速演算如下：

一趟快速排序的算法是：

設定兩個變量start、end，排序開始的時候：start=1，end=N；

以第一個數組元素作為關鍵資料，指派給pivot，即 pivot=arry[1]；

從end開始向前搜尋，即由後開始向前搜尋（end--），找到第一個小于pivot的值arry[end]，并與arry[start]交換,即swat(arry,start,end)；

從start開始向後搜尋，即由前開始向後搜尋（start++），找到第一個大于pivot的arry[start]，與arry[end]交換,即swat(arry,start,end);

重複第3、4步，直到 start==end，這個時候arry[start]=arry[end]=pivot，而pivot的位置就是其在整個數組中正确的位置；

通過遞歸，将問題規模不斷分解。将pivot兩邊分成兩個數組繼續求新的pivot，最後解出問題。

View Code

思路和前面的一樣，隻是使用java來實作。

上面的java版本快速排序寫的有點淩亂，下面給出改進版本，本文中的java版本快排并沒有想前面c++版本那樣使用swap方法。

如果使用上述方法進行快速排序，數組中有相同的數，那麼排序過程中會出現死循環，這裡需要修改Partition函數中的while循環的條件，将原來的arry[end]>pivot改為arry[end]>=pivot，arry[start]<pivot改為arry[start]<=pivot。

修改以後的Partition函數如下：

本文轉自xwdreamer部落格園部落格，原文連結：http://www.cnblogs.com/xwdreamer/archive/2011/06/15/2297000.html，如需轉載請自行聯系原作者