一、導論
??? 快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。這就是分而治之的思想，因此，快速排序算法也是分治策略的一種應用。
二、快速排序的大致思想
??? 快速排序?qū)崿F(xiàn)的重點在于數(shù)組的拆分。
??? 首先選擇列表中的一個元素作為基準元素【通常我們將數(shù)組的第一個元素定義為比較元素】，其他的元素都與這個元素做比較，找出小于這個基準值的值、大于基準值的值。這稱為“分區(qū)”，包括：
??? （1）一個由所有小于基準值的數(shù)字組成的子數(shù)組
??? （2）基準值
??? （3）一個由所有大于基準值的數(shù)組組成的子數(shù)組
??? 然后再將“小于v”和“大于v”的數(shù)據(jù)塊作為子數(shù)組，同樣選擇基準值，再進行上述類似操作，分別對這兩個子數(shù)組進行分區(qū)。當執(zhí)行到數(shù)據(jù)塊中只有1個元素或者0個元素時，即完成排序。
??? 這個問題中的基線條件是執(zhí)行到數(shù)據(jù)塊中只有1個或者0個元素。
三、例子演示
??? 將該數(shù)組從小到大排序。
??? 首先選取數(shù)組第一個數(shù)23為基準數(shù)，存入temp變量中，從數(shù)組的左右兩邊界向中間進行遍歷，定義兩個指針 i 和 j，i 最開始指向數(shù)組的第一個元素，j 最開始指向數(shù)組的最后一個元素。指針 i 從左向右移動，指針 j 從右向左移動。先移動 j 指針（從右忘左移），當 j 指向的數(shù)大于基準數(shù)時，略過，j 繼續(xù)往左移動，直到遇到小于等于基準數(shù)的數(shù)arr[j]，將arr[j]填入arr[i]中；再移動 i 指針，當 i 指向的數(shù)小于等于基準數(shù)時，略過，i 繼續(xù)往右移動，直到遇到不比基準數(shù)小的數(shù)arr[i]，將arr[i]填入arr[j]中；再移動 i 指針，再移動 j 指針...(輪換移動)，直到 i 和 j 指針相遇，此時將temp（基準數(shù)）填入arr[i]中即完成算法的第2個步驟。接下來分別將基準數(shù)左邊和右邊的數(shù)組按照以上方法進行聚合，直到每個子集只有一個元素，即排序完成。
??? 【下列圖中，顏色為黃色的表明該位置為下一個被賦值的位置，也就是一個坑，等待下一次的填充。橘黃色的表示該位置剛完成值的拷貝。】
??? 將數(shù)組第一個數(shù)23賦給temp變量，指針 i 指向數(shù)組第一個元素，指針 j 指向數(shù)組最后一個元素。
??? 從j開始遍歷（從右往左），遇到13時，因為13<=temp，因此將arr[j]填入arr[i]中，即此時指針 i 指向的數(shù)為13。
??? 再從i遍歷（從左往右），遇到45時，因為45>temp，因此將arr[i]填入arr[j]中，此時指針 j 指向的數(shù)為45。
??? 繼續(xù)從j遍歷，遇到11時，因為11<=temp，因此將arr[j]填入arr[i]中，即此時指針 i指向的數(shù)為11。
??? 從i遍歷，遇到89時，因為89>temp，因此將arr[i]填入arr[j]中，此時指針 j 指向的數(shù)為89。
??? 從j遍歷，遇到17時，因為17<=temp，因此將arr[j]填入arr[i]中，即此時指針 i 指向的數(shù)為17。
??? 從i遍歷，遇到72時，因為72>temp，因此將arr[i]填入arr[j]中，此時指針 j 指向的數(shù)為72。
??? 從j遍歷，遇到3時，因為3<=temp，因此將arr[j]填入arr[i]中，即此時指針 i 指向的數(shù)為3。
??? 從i遍歷，遇到26時，因為26>temp，因此將arr[i]填入arr[j]中，此時指針 j 指向的數(shù)為26。
??? 從j遍歷，和 i 重合，將temp（基準數(shù)23）填入arr[i]中。
??? 第一輪排序完成，緊接著遞歸，將23左邊和右邊的子區(qū)間分別用以上方法進行排序，直到區(qū)間只有一個元素即排序完成。
四、代碼截圖
五、算法時間復雜度分析
??? 快速排序的性能高度依賴于你選擇的基準值。
??? 1、最佳情況：算法復雜度O(n log n)
??? 快速排序最優(yōu)的情況就是每一次取到的元素都剛好平分整個數(shù)組。
??? 此時的時間復雜度公式則為：T(n) = 2T(n/2) + f(n)；
??? T(n/2)為平分后的子數(shù)組的時間復雜度，f(n) 為平分這個數(shù)組時所花的時間；在最佳情況下，棧長為O(log n)，每一層運行時間為O(n)。
??? 由主定理法可以得到：T(n)=O(nlogn)
??? 假設總是將中間的元素用作基準值，在這種情況下，調(diào)用棧如下：
??? 調(diào)用棧短得多！因為每次都將數(shù)組分成兩半，所以不需要那么多遞歸調(diào)用。很快就到達了基線條件，因此調(diào)用棧短得多。通過上圖也能發(fā)現(xiàn)，整個算法需要的時間為O(n) * O(log n) = O(n log n)。
??? 2、最糟情況：算法復雜度O(n^2)
??? 當待排序的序列為正序或逆序排列時，且每次劃分只得到一個比上一次劃分少一個記錄的子序列，注意另一個為空。如果遞歸樹畫出來，它就是一棵斜樹。
??? 此時需要執(zhí)行n‐1次遞歸調(diào)用，且第i次劃分需要經(jīng)過n‐i次關(guān)鍵字的比較才能找到第i個記錄，也就是樞軸的位置，因此比較次數(shù)為：
??? 最終其時間復雜度為O(n^2)。
??? 【換個說法：在最糟情況下，棧長為O(n)，在調(diào)用棧的每層都涉及O(n)個元素，完成每層所需的時間都為O(n)。因此整個算法需要的時間為O(n) * O(n) = O(n^2)】。
??? 3、平均情況：算法復雜度O(n log n)
??? 最佳情況也是平均情況。只要每次都隨機地選擇一個數(shù)組元素作為基準值，快速排序的平均運行時間就將為O(nlogn)?？焖倥判蚴亲羁斓呐判蛩惴ㄖ?，也是D&C典范。
