基本思想
設當前待排序的數組無序區為R[low..high]，利用分治法可將快速排序的基本思想描述為：
分解：在R[low..high]中任選一個記錄作為基準（Pivot），以此基準將當前無序區劃分為左、右兩個較小的子區間R[low..pivotpos-1)和R[pivotpos+1..high]，并使左邊子區間中所有記錄的關鍵字均小于等于基準記錄（不妨記為pivot）的關鍵字pivot.key，右邊的子區間中所有記錄的關鍵字均大于等于pivot.key，而基準記錄pivot則位于正確的位置（pivotpos）上，它無需參加后續的排序。注意：劃分的關鍵是要求出基準記錄所在的位置pivotpos，劃分的結果可以簡單地表示為（注意pivot=R[pivotpos]）：R[low..pivotpos-1].keys ≤ R[pivotpos].key ≤ R[pivotpos+1..high].keys其中low≤pivotpos≤high。
求解：通過遞歸調用快速排序對左、右子區間R[low..pivotpos-1]和R[pivotpos+1..high] 快速排序。
組合：因為當“求解”步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言， “組合”步驟不需要做什么，可看作是空操作。
算法實現
快速排序算法，java實現，代碼如下所示：
public abstract class Sorter { public abstract void sort(int[] array); } public class QuickSorter extends Sorter { @Override public void sort(int[] array) { quickSort(array, 0, array.length - 1); } /** * 通過劃分，基于分治思想，遞歸執行子任務排序最后合并 * @param low 數組首位置索引 * @param high 數組末位置索引 */ PRivate void quickSort(int[] array, int low, int high) { int pivotPos; // 劃分基準元素索引 if (low < high) { pivotPos = partition(array, low, high); quickSort(array, low, pivotPos - 1); // 左劃分遞歸快速排序 quickSort(array, pivotPos + 1, high); // 右劃分遞歸快速排序 } } /** * 簡單劃分方法 * @param i * @param j * @return */ private int partition(int[] array, int i, int j) { Integer pivot = array[i]; // 初始基準元素，如果quickSort方法第一次調用，pivot初始為數組第一個元素 while (i < j) { // 兩個指針從兩邊向中間靠攏，不能相交 // 右側指針向左移動 while (j > i && array[j] >= pivot) { j--; } if (i < j) { // 如果在沒有使指針i和j相交的情況下找到了array[j] >= 基準元素pivot array[i] = array[j]; // 基準元素放到了j指針處 i++; // 左側i指針需要向右移動一個位置 } // 左側指針向右移動 while (i < j && array[i] <= pivot) { i++; } if (i < j) { // 如果在沒有使指針i和j相交的情況下找到了array[i] <= 基準元素pivot array[j] = array[i]; // 基準元素放到了i指針處 j--; // 右側j指針需要向左移動一個位置 } } array[i] = pivot; // 將基準元素放到正確的排序位置上 return i; } }排序過程
采用分治的思想對待排序數組進行劃分。分治法的基本思想是：將原問題分解為若干個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然后將這些子問題的解組合為原問題的解?？焖倥判?，主要是求得一個合理的劃分，從而基于此劃分來分治排序。使用簡單劃分方法的思想是：第一步：設置兩個指針i和j，它們的初值分別為區間的下界和上界，即i=low，i=high； 選取無序區的第一個記錄R[i](即R[low])作為基準記錄，并將它保存在變量pivot中；第二步：
首先，令j自high起向左掃描，直到找到第1個關鍵字小于pivot.key的記錄R[j]，將R[j]移至i所指的位置上，這相當于R[j]和基準R[i]（即pivot）進行了交換，使關鍵字小于基準關鍵字pivot.key的記錄移到了基準的左邊，交換后R[j]中相當于是pivot；然后，令i指針自i+1 位置開始向右掃描，直至找到第1個關鍵字大于pivot.key的記錄R[i]，將R[i]移到i所指的 位置上，這相當于交換了R[i]和基準R[j]，使關鍵字大于基準關鍵字的記錄移到了基準的右邊， 交換后R[i]中又相當于存放了pivot；接著，令指針j自位置j-1開始向左掃描，如此交替改變掃 描方向，從兩端各自往中間靠攏，直至i=j時，i便是基準pivot最終的位置，將pivot放在 此位置上就完成了一次劃分。快速排序示例過程，如下所示：假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20。首先，根據數組下界和上界，求得一個劃分，劃分過程如下：
第一次劃分：初始化：i = 0，j=19，以第一個元素array[0] = 94為基準pivot = array[0] = 94。首先指針j向前移動：array[19] = 49<pivot = array[0] = 94，i = 0<j = 19，繼續移動j指針；array[18] = 76<pivot = array[0] = 94，i = 0<j = 18，繼續移動j指針；……array[1] = 12<pivot = array[0] = 94，i = 0<j = 1，繼續移動j指針；i = 0pivotPos-1 = -1排序停止；右側部分繼續遞歸執行快速排序。
第二次劃分：對于{12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}：初始化：i = 1，j=19，以第二個元素（除了第一次劃分的基準元素）array[1] = 12為基準pivot = array[1] = 12。首先指針j向前移動：array[19] = 49>=pivot = array[1] = 12成立，并且j = 19>i = 1，j指針繼續移動；array[18] = 76>=pivot = array[1] = 12成立，并且j = 18>i = 1，j指針繼續移動；array[17] = 65>=pivot = array[1] = 12成立，并且j = 17>i = 1，j指針繼續移動；array[16] = 12>=pivot = array[1] = 12成立，并且j = 16>i = 1，j指針繼續移動；array[15] = 37>=pivot = array[1] = 12成立，并且j = 15>i = 1，j指針繼續移動；array[14] = 90>=pivot = array[1] = 12成立，并且j = 14>i = 1，j指針繼續移動；array[13] = 83>=pivot = array[1] = 12成立，并且j = 13>i = 1，j指針繼續移動；array[12] = 68>=pivot = array[1] = 12成立，并且j = 12>i = 1，j指針繼續移動；array[11] = 5>=pivot = array[1] = 12不成立，j指針停止移動：此時i = 1<j = 11，將j指針處的元素移動到i指針處：array[1] = 5（基準元素的拷貝為pivot = 12），同時i指針向后移動一次：i++，即i = 2；子數組變為（下面左邊的12表示基準元素，實際j指針移動后并沒有移動基準元素，而是pivot變量持有它的拷貝，12 處仍然是5）：{5,34,76,26,9,0,37,55,76,37,12,68,83,90,37,12,65,76,49}。指針i向后移動：array[2] = 34<=pivot = 12不成立，i指針停止移動：此時i = 2<j = 11，將i指針處的元素移動到j指針處：array[11] = 34（基準元素的拷貝為pivot = 12），同時j指針向前移動一次：j–，即j = 10；子數組變為：{5,12,76,26,9,0,37,55,76,37,34,68,83,90,37,12,65,76,49}。判斷i與j：i = 2= pivot = 12成立，并且j = 10>i = 2，j指針繼續移動；array[9] = 76>= pivot = 12成立，并且j = 9>i = 2，j指針繼續移動；array[8] = 55>= pivot = 12成立，并且j = 8>i = 2，j指針繼續移動；array[7] = 37>= pivot = 12成立，并且j = 7>i = 2，j指針繼續移動；array[6] = 0>= pivot = 12不成立，j指針停止移動：此時j = 6>i = 2，將j指針處的元素array[6] = 0移動到i指針處：array[2] = array[6] = 0（基準元素的拷貝為pivot = 12），同時i指針向后移動一次：i++，即i = 3；子數組變為（下面左邊的12表示基準元素，實際j指針移動后并沒有移動基準元素，而是pivot變量持有它的拷貝，12處仍然是0）：{5,0,76,26,9,12,37,55,76,37,34,68,83,90,37,12,65,76,49}。指針i第2次向后移動：array[3] = 76i = 3，將i指針處的元素array[3] = 76移動到j指針處：array[6] = array[3] = 0（基準元素的拷貝為pivot = 12），同時j指針向前移動一次：j–，即j = 5；子數組變為：{5,0,12,26,9,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。判斷i與j：i = 3=pivot = 12不成立，j指針停止移動：此時j = 5>i = 3，將j指針處的元素array[5] = 9移動到i指針處：array[3] = array[5] = 9（基準元素的拷貝為pivot = 12），同時i指針向后移動一次：i++，即i = 4；子數組變為（下面左邊的12表示基準元素，實際j指針移動后并沒有移動基準元素，而是pivot變量持有它的拷貝，12處仍然是9）：{5,0,9,26,12,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。指針i第3次向后移動：array[4] = 26i = 4，將i指針處的元素array[4] = 26移動到j指針處：array[5] = array[4] = 26（基準元素的拷貝為pivot = 12），同時j指針向前移動一次：j–，即j = 4；子數組變為：{5,0,9,12,26,76,37,55,76,37,34,68,83,90,37,12,65,76,49}。判斷i與j：i = 4<j = 4不成立，條件不滿足：將基準元素放到i指針處，array[4] = pivot = 12；并返回基準元素的索引i = 4。劃分結束。根據得到的基準元素的索引，遞歸快速排序。
算法分析
時間復雜度最好情況在最好情況下，每次劃分所取的基準都是當前無序區的”中值”記錄，劃分的結果是基準的左、右兩個無序子區間的長度大致相等，總的關鍵字比較次數：0(nlgn)。最壞情況最壞情況是每次劃分選取的基準都是當前無序區中關鍵字最?。ɑ蜃畲螅┑挠涗?，劃分的結果是基準左邊的子區間為空（或右邊的子區間為空），而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。因此，快速排序必須做n-1次劃分，第i次劃分開始時區間長度為n-i+1，所需的比較次數為n-i(1≤i≤n-1)，故總的比較次數達到最大值：n(n-1)/2 = O(n^2)如果按上面給出的劃分算法，每次取當前無序區的第1個記錄為基準，那么當文件的記錄已按遞增序（或遞減序）排列時，每次劃分所取的基準就是當前無序區中關鍵字最?。ɑ蜃畲螅┑挠涗?，則快速排序所需的比較次數反而最多。
空間復雜度快速排序在系統內部需要一個棧來實現遞歸。若每次劃分較為均勻，則其遞歸樹的高度為O(logn)，故遞歸后需棧空間為O(logn)。最壞情況下，遞歸樹的高度為O(n)，所需的棧空間為O(n)。
排序穩定性快速排序是不穩定的。
新聞熱點
疑難解答
