快速排序(QuickSort)
1、算法思想
快速排序是C.R.A.Hoare于1962年提出的一種劃分交換排序。它采用了一種分治的政策，通常稱其為分治法(Divide-and-ConquerMethod)。
（1） 分治法的基本思想
分治法的基本思想是：将原問題分解為若幹個規模更小但結構與原問題相似的子問題。遞歸地解這些子問題，然後将這些子問題的解組合為原問題的解。
（2）快速排序的基本思想
設目前待排序的無序區為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]快速排序。
③組合：
因為當"求解"步驟中的兩個遞歸調用結束時，其左、右兩個子區間已有序。對快速排序而言，"組合"步驟無須做什麼，可看作是空操作。
2、快速排序算法QuickSort
void QuickSort(SeqList R，int low，int high)
{ //對R[low..high]快速排序
int pivotpos； //劃分後的基準記錄的位置
if(low<high){//僅當區間長度大于1時才須排序
pivotpos=Partition(R，low，high)； //對R[low..high]做劃分
QuickSort(R，low，pivotpos-1)； //對左區間遞歸排序
QuickSort(R，pivotpos+1，high)； //對右區間遞歸排序
}
} //QuickSort
注意：
為排序整個檔案，隻須調用QuickSort(R，1，n)即可完成對R[l..n]的排序。
3、劃分算法Partition
下面介紹兩種劃分的解決思路：
這兩種劃分的過程都需要用到兩個指針i,j(訓示數組下标)；并且假定每次都指定數組的第一個元素作為基準。
（1）i,j下标同時從左往右走。
i和j初始同時指向基準，以後j指針一直向右走，如果j所指向的元素小于或者等于基準（第一個元素），那麼i也向右走一步。
（這個時候我們可以這樣了解 i 這個指針，它表示在其所指向元素的左邊（包括本身）都小于等于基準。）
那麼如果 j 所指向的元素大于基準，那麼 i 指針不動。
那麼就可能出現這樣的情況：
這個時候 指針 i 和 j 之間間隔了幾個元素，那怎麼辦呢？
這樣的話，先 i++； 然後把 i 所指向的元素 和 j 所指向的元素互換，這樣就ok了。
按照這樣一直做下去，直到 指針 j 指到最後一個元素結束；
最後再 交換 第一個元素（也就是基準） 和 指針 i 所指向的元素。
下面展示一下，用c++實作的代碼：
void swap(int &a, int &b)
{
int k;
k = a;
a = b;
b = k;
}
int split_1(int* a,int low,int high)
{
int i = 0;
int x = a[low];
for(int j = 1; j<=high; j++)
{
if(a[j] <= x)
{
i++;
if(i != j)
{
swap(a[i],a[j]);
}
}
}
swap(a[low],a[i]);
return i;
}
（2）i,j下标分别在最左端和最右端，同時往中間走。
初始狀态如下：
指針 i 向右掃描，直到所指向的元素大于基準值；
指針 j 向左掃描，直到所指向的元素小于基準值。
那麼這個時候，指針 i 所指向的元素大于基準值； 指針 j 所指向的元素小于基準值。
交換 指針 i 所指向元素 和 指針 j 所指向元素。
一直重複上述過程，直到，指針 i 跑到 指針 j 的右邊。
這個時候再 交換 基準和指針 j 所指向元素。
下面給出c++實作代碼：
void swap(int &a, int &b)
{
int k;
k = a;
a = b;
b = k;
}
int split_2(int* a, int low, int high)
{
int i = low;
int j = high;
int x = a[low];
while (i <= j)
{
while (a[i] <= x && i<high)
i++;
while (a[j] >= x && j>low)
{
j--;
}
if (i <= j)
{
swap(a[i], a[j]);
i++;
j--;
}
}
swap(a[low], a[j]);
return j;
} 對這兩種劃分方法的總結：雖然這兩種劃分的方法不同，但是其目的都是一樣的，就是為了确定基準值的最終位置，同時，基準值左邊的元素都比基準值小（或者等于）；基準值右邊的元素都比基準值大（或者等于）。
4、實作快速排序
基于上面已經給出了快速排序的僞代碼，結合劃分算法的代碼，應該很快就可以寫成快速排序的代碼。
void quickSort(int *a,int low,int high)
{
if(low<high)
{
//選擇一種劃分算法
int pos = split_1(a,low,high);
//int pos = split_2(a,low,high);
quickSort(a,low,pos-1);
quickSort(a,pos+1,high);
}
} 5、算法分析
快速排序的時間主要耗費在劃分操作上，對長度為k的區間進行劃分，共需k-1次關鍵字的比較。
（1）最壞時間複雜度
最壞情況是每次劃分選取的基準都是目前無序區中關鍵字最小(或最大)的記錄，（例如在數組元素已經有序的情況下，）劃分的結果是基準左邊的子區間為空(或右邊的子區間為空)，而劃分所得的另一個非空的子區間中記錄數目，僅僅比劃分前的無序區中記錄個數減少一個。
是以，快速排序必須做n-1次劃分，第i次劃分開始時區間長度為n-i+1，所需的比較次數為n-i(1≤i≤n-1)，故總的比較次數達到最大值：
Cmax = n(n-1)/2=O(n2)
如果按上面給出的劃分算法，每次取目前無序區的第1個記錄為基準，那麼當檔案的記錄已按遞增序(或遞減序)排列時，每次劃分所取的基準就是目前無序區中關鍵字最小(或最大)的記錄，則快速排序所需的比較次數反而最多。
（2） 最好時間複雜度
在最好情況下，每次劃分所取的基準都是目前無序區的"中值"記錄，劃分的結果是基準的左、右兩個無序子區間的長度大緻相等。總的關鍵字比較次數： 0(nlgn)
注意：
用遞歸樹來分析最好情況下的比較次數更簡單。因為每次劃分後左、右子區間長度大緻相等，故遞歸樹的高度為O(lgn)，而遞歸樹每一層上各結點所對應的劃分過程中所需要的關鍵字比較次數總和不超過n，故整個排序過程所需要的關鍵字比較總次數C(n)=O(nlgn)。
因為快速排序的記錄移動次數不大于比較的次數，是以快速排序的最壞時間複雜度應為0(n2)，最好時間複雜度為O(nlgn)。
（3）基準關鍵字的選取
在目前無序區中選取劃分的基準關鍵字是決定算法性能的關鍵。
①"三者取中"的規則
"三者取中"規則，即在目前區間裡，将該區間首、尾和中間位置上的關鍵字比較，取三者之中值所對應的記錄作為基準，在劃分開始前将該基準記錄和該區伺的第1個記錄進行交換，此後的劃分過程與上面所給的Partition算法完全相同。
②取位于low和high之間的随機數k(low≤k≤high)，用R[k]作為基準
選取基準最好的方法是用一個随機函數産生一個取位于low和high之間的随機數k(low≤k≤high)，用R[k]作為基準，這相當于強迫R[low..high]中的記錄是随機分布的。用此方法所得到的快速排序一般稱為随機的快速排序。
随機化的快速排序與一般的快速排序算法差别很小。但随機化後，算法的性能大大地提高了，尤其是對初始有序的檔案，一般不可能導緻最壞情況的發生。算法的随機化不僅僅适用于快速排序，也适用于其它需要資料随機分布的算法。
說明：重新選取好基準後，隻需要将基準和第一個元素進行交換處理，這樣上面的劃分算法代碼就可以原封不動啦。
（4）平均時間複雜度
盡管快速排序的最壞時間為O(n2)，但就平均性能而言，它是基于關鍵字比較的内部排序算法中速度最快者，快速排序亦是以而得名。它的平均時間複雜度為O(nlgn)。
（5）空間複雜度
快速排序在系統内部需要一個棧來實作遞歸。若每次劃分較為均勻，則其遞歸樹的高度為O(lgn)，故遞歸後需棧空間為O(lgn)。最壞情況下，遞歸樹的高度為O(n)，所需的棧空間為O(n)。
（6）穩定性
快速排序是非穩定的，例如[2，2，1]。