五分鐘掌握快速排序

       快速排序采用的分治法的思想，在資料量大的時候效率極高，是以在許多情景下都能能使用到，是必須掌握的排序方法。

       快速排序的基本思想是:

• 先從數列中取出一個數作為基準數（我更喜歡叫标兵）
• 進行分區，将比标兵大的數放到它右邊，小于等于的數放到它的左邊
• 對兩個分區重複第二步，直到各分區隻剩一個數時退出

       在網上看的一篇部落格用的是分治法加填坑法，講的通俗易懂！将快速排序法了解為挖坑填坑的操作。假如對下面數組進行快速排序，我們來分析一下排序的過程。

1	2	3	4	5	6
65	23	88	12	77	69	26

       首先，取第一個數為标兵，這時left=0，right=6，refer=arr[0]=65

       這時refer緩存的是65，可以了解為在a[0]那裡挖了個坑，後面就是填坑的操作。排序開始，right開始從後往前移動直到找到比refer小于等于的數，把這個數填到arr[0]那裡，當right=6時，符合條件，于是arr[0]=arr[6],left++。這裡left++是因為此時arr[left]肯定是小于refer的數了，下次就繼續從下一個數開始，避免重複操作。這時arr[6]又産生了一個坑，下次輪到left從前往後找比refer(65)大的數，當left=2時，符合條件，把這個數填到arr[6]那個坑那裡，arr[6]=arr[2],right--，這時arr[2]又産生一個坑。refer為65還不會變。這時left=3，right=5,不滿足跳出循環的條件，繼續下一輪。

1	2	3	4	5	6
26	23	88	12	77	69	88

       現在坑在arr[2]那裡，refer=65,left=3,right=5，right繼續從5那裡right--找比65小的數，當right=3時，符合條件,于是arr[2]=arr[3]，left++。這時新坑arr[3]出現啦，但是現在left(4)>right(3)，符合條件跳出了循環，arr[3]的坑還沒填，于是把标兵refer的值放在arr[3]那裡（标兵歸位），數組變為：

1	2	3	4	5	6
26	23	12	65	77	69	88

       這就保證arr[3]=refer=65那裡，左邊是比它小的數，右邊是比它大的數，至此一輪排序完成。後面就繼續遞歸調用本函數對arr[0…2]和arr[4…6]這兩個子區間重複上述步驟就可以了。

對挖坑填數進行總結

1. left =start; right = end; 将标兵挖出形成第一個坑arr[left]。
2. right--由後向前找比它小的數，找到後挖出此數填前一個坑arr[left]中。
3. left++由前向後找比它大的數，找到後也挖出此數填到前一個坑arr[right]中。
4. 再重複執行b，c二步，直到left>=right，将标兵填入arr[left]中。

以下是實作代碼：