一萎羔、導(dǎo)論
??? 快速排序由C. A. R. Hoare在1960年提出潘悼。它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分继谚，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小允乐，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序费彼，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列痰娱。這就是分而治之的思想弃榨，因此，快速排序算法也是分治策略的一種應(yīng)用梨睁。
二鲸睛、快速排序的大致思想
??? 快速排序?qū)崿F(xiàn)的重點在于數(shù)組的拆分。
??? 首先選擇列表中的一個元素作為基準(zhǔn)元素【通常我們將數(shù)組的第一個元素定義為比較元素】坡贺，其他的元素都與這個元素做比較官辈，找出小于這個基準(zhǔn)值的值、大于基準(zhǔn)值的值遍坟。這稱為“分區(qū)”拳亿，包括：
??? （1）一個由所有小于基準(zhǔn)值的數(shù)字組成的子數(shù)組
??? （2）基準(zhǔn)值
??? （3）一個由所有大于基準(zhǔn)值的數(shù)組組成的子數(shù)組
??? 然后再將“小于v”和“大于v”的數(shù)據(jù)塊作為子數(shù)組，同樣選擇基準(zhǔn)值愿伴，再進行上述類似操作肺魁，分別對這兩個子數(shù)組進行分區(qū)。當(dāng)執(zhí)行到數(shù)據(jù)塊中只有1個元素或者0個元素時隔节，即完成排序鹅经。
??? 這個問題中的基線條件是執(zhí)行到數(shù)據(jù)塊中只有1個或者0個元素。
三怎诫、例子演示
??? 將該數(shù)組從小到大排序瞬雹。
??? 首先選取數(shù)組第一個數(shù)23為基準(zhǔn)數(shù)，存入temp變量中刽虹，從數(shù)組的左右兩邊界向中間進行遍歷，定義兩個指針 i 和 j呢诬，i 最開始指向數(shù)組的第一個元素涌哲，j 最開始指向數(shù)組的最后一個元素。指針 i 從左向右移動尚镰，指針 j 從右向左移動阀圾。先移動 j 指針（從右忘左移），當(dāng) j 指向的數(shù)大于基準(zhǔn)數(shù)時狗唉，略過初烘，j 繼續(xù)往左移動，直到遇到小于等于基準(zhǔn)數(shù)的數(shù)arr[j]，將arr[j]填入arr[i]中肾筐；再移動 i 指針哆料，當(dāng) i 指向的數(shù)小于等于基準(zhǔn)數(shù)時，略過吗铐，i 繼續(xù)往右移動东亦，直到遇到不比基準(zhǔn)數(shù)小的數(shù)arr[i]，將arr[i]填入arr[j]中唬渗；再移動 i 指針典阵，再移動 j 指針...(輪換移動)，直到 i 和 j 指針相遇镊逝，此時將temp（基準(zhǔn)數(shù)）填入arr[i]中即完成算法的第2個步驟壮啊。接下來分別將基準(zhǔn)數(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（基準(zhǔn)數(shù)23）填入arr[i]中酪我。
??? 第一輪排序完成消痛，緊接著遞歸，將23左邊和右邊的子區(qū)間分別用以上方法進行排序都哭，直到區(qū)間只有一個元素即排序完成秩伞。
四、代碼截圖
五欺矫、算法時間復(fù)雜度分析
??? 快速排序的性能高度依賴于你選擇的基準(zhǔn)值纱新。
??? 1、最佳情況：算法復(fù)雜度O(n log n)
??? 快速排序最優(yōu)的情況就是每一次取到的元素都剛好平分整個數(shù)組汇陆。
??? 此時的時間復(fù)雜度公式則為：T(n) = 2T(n/2) + f(n)；
??? T(n/2)為平分后的子數(shù)組的時間復(fù)雜度带饱，f(n) 為平分這個數(shù)組時所花的時間毡代；在最佳情況下阅羹，棧長為O(log n)，每一層運行時間為O(n)教寂。
??? 由主定理法可以得到：T(n)=O(nlogn)
??? 假設(shè)總是將中間的元素用作基準(zhǔn)值捏鱼，在這種情況下，調(diào)用棧如下：
??? 調(diào)用棧短得多酪耕！因為每次都將數(shù)組分成兩半导梆，所以不需要那么多遞歸調(diào)用。很快就到達了基線條件迂烁，因此調(diào)用棧短得多看尼。通過上圖也能發(fā)現(xiàn)，整個算法需要的時間為O(n) * O(log n) = O(n log n)盟步。
??? 2藏斩、最糟情況：算法復(fù)雜度O(n^2)
??? 當(dāng)待排序的序列為正序或逆序排列時，且每次劃分只得到一個比上一次劃分少一個記錄的子序列却盘，注意另一個為空狰域。如果遞歸樹畫出來，它就是一棵斜樹黄橘。
??? 此時需要執(zhí)行n‐1次遞歸調(diào)用兆览，且第i次劃分需要經(jīng)過n‐i次關(guān)鍵字的比較才能找到第i個記錄，也就是樞軸的位置塞关，因此比較次數(shù)為：
??? 最終其時間復(fù)雜度為O(n^2)抬探。
??? 【換個說法：在最糟情況下，棧長為O(n)描孟，在調(diào)用棧的每層都涉及O(n)個元素驶睦，完成每層所需的時間都為O(n)。因此整個算法需要的時間為O(n) * O(n) = O(n^2)】匿醒。
??? 3场航、平均情況：算法復(fù)雜度O(n log n)
??? 最佳情況也是平均情況。只要每次都隨機地選擇一個數(shù)組元素作為基準(zhǔn)值廉羔，快速排序的平均運行時間就將為O(nlogn)溉痢。快速排序是最快的排序算法之一憋他，也是D&C典范孩饼。
