1、引言
今天的運氣不是很好，再加上項目的壓力。準備停止學習一周，等把項目這一關過了，再繼續深入學習分享算法。后來吧今天遇到的事情都比較郁悶，也無心情繼續開發項目。便想轉移一下注意力，繼續學習快速排序算法的內容。
昨天了解了遞歸的使用原理。今天可以使用這個新技能來解決一個新的問題————快速排序。快速排序是一種排序算法，這個算法比前天學習的選擇排序要快得多，實屬優雅代碼的典范。
2、快速排序
2.1 學習準備
這里講解一個比較著名的遞歸式問題解決方法————分而治之（divide and comquer，D&C)。為了方便理解，還是使用一個示例給大家講解一下這是個什么樣的使用原理。
給定一個數字數組arr=[2,4,6],我們可以將這些數字相加并返回結果，使用循環其實可以很容易得出結論（具體代碼可以自行來敲哦！可以粘到留言板我幫你檢查哦~）,那么如何使用遞歸函數解決這個需求呢？
這里給出一種思路實現：
1、找出基線條件
我們首先考慮最簡單的數組是什么樣的？一種是空數組或者數組中只有一個元素，這完全可以直接計算出來，結果要么就是null或者就是這個元素的值。計算總和非常容易，這就是我們需要找的基線條件（不明白基線條件可以看昨天的文章哦）。
2、縮小數組
我們需要算出這個數組的和，其實可以表示為sum([2,4,6]),那么如何縮小數組的規模呢？那么sum([2,4,6])=2+sum([4,6]) = 2 + 4 + sum([6])(達到基線條件) = 2+4+6=12。
3、函數的運行過程
下圖解釋了函數是如何運行的，遞歸保存了運行的狀態！
運行過程
運行狀態
2.2 快速排序的原理
使用快速排序算法對數組進行排序，首先考慮對于排序算法而言，最簡單的數組上面介紹要么是空數組或者只有一個元素的數組。因此基線條件為空或者只包含一個元素。在這種情況，可以直接返回該數組。
代碼片段實現：
private int[] quickSort(int[] array){
if(array.length < 2){
return array;
}
}
我們再在數組里加一個元素，兩個元素應該如何排序呢？思路也很簡單，如果從小到大排序，就需要將這兩個元素進行比較，如果前一個比較小，直接返回；如果前一個比較大，就需要互相交換，然后返回數組。那么包含三個元素或者更長的數組應該怎么排序呢？
此時我們可以考慮分而治之算法，將數組進行分解，直到滿足基線條件。第一步，從數組中選擇一個基準值，理論上這個基準值是可以隨意挑選的，你可以選擇數組首項也可以選擇中項甚至可選擇尾項。（有什么區別在后面講）
我們暫時先將數組中的第一個值用作基準值，接下來，我們需要找出比基準值大的和小的元素，這被稱為"分區"，這樣操作之后，你會有一個比基準值小的數字組成的子數組、基準值、一個比基準值大的數字組成的子數組。
但是這里只是進行了分區，但這個分區數組并不一定就是有序的。但是我們三項的數組就可以在選出一個基準值的情況下，然后對后面的數組（只含有兩項）進行排序（這個很容易），這樣我們也得到了有序數組，那么四項數組、五項數組甚至更多項呢？
2.2 代碼實現
書上使用的Python代碼，我將其翻譯為JAVA語言，快速排序算法利用python語言是很好實現的，但是java實現起來還是比較麻煩的。通過網上查閱，先將編譯好的java代碼進行展現。
private static int partition(int[] arr, int low, int high) {
//指定左指針i和右指針j
int i = low;
int j= high;
//將第一個數作為基準值。挖坑
int x = arr[low];
//使用循環實現分區操作
while(i<j){//5 8
//1.從右向左移動j，找到第一個小于基準值的值 arr[j]
while(arr[j]>=x && i<j){
j--;
}
//2.將右側找到小于基準數的值加入到左邊的（坑）位置， 左指針想中間移動一個位置i++
if(i<j){
arr[i] = arr[j];
i++;
}
//3.從左向右移動i，找到第一個大于等于基準值的值 arr[i]
while(arr[i]<x && i<j){
i++;
}
//4.將左側找到的打印等于基準值的值加入到右邊的坑中，右指針向中間移動一個位置 j--
if(i<j){
arr[j] = arr[i];
j--;
}
}
//使用基準值填坑，這就是基準值的最終位置
arr[i] = x;//arr[j] = y;
//返回基準值的位置索引
return i; //return j;
}
private static void quickSort(int[] arr, int low, int high) {//???遞歸何時結束
if(low < high){
//分區操作，將一個數組分成兩個分區，返回分區界限索引
int index = partition(arr,low,high);
//對左分區進行快排
quickSort(arr,low,index-1);
//對右分區進行快排
quickSort(arr,index+1,high);
}
}
2.3 運行時間
快速排序的運行時間在于你選擇的基準值。假設你一直都選擇第一個元素作為基準值，且要處理的數組是有序的。快速排序不檢查數組元素的順序，因此還是會嘗試對其排序，但是這會有一個問題，每次選擇第一個作為基準值，導致比基準值小的數組都是空的，使得調用棧非常高。運行時間較長。棧長表示為O(n)。
調用棧（最糟情況）
那有沒有更好的辦法呢？有的，我們可以參考二分查找的實現方法，每次選擇中間的元素作為基準值，就會發現調用棧被減短了許多，不需要太多的遞歸調用，就會達到基線條件，最佳情況下棧長為O(logn)。
最佳情況
因此，在最糟糕的情況下（選擇第一個為基準值）運行時間為O(n)。在最佳情況下，運行時間僅為O(nlogn)。
