快速排序(QuickSort)也是一種排序算法，對包含n個數組的輸入數組，最壞情況運行時間為O(n^2)。雖然這個最壞情況運行時間比較差，但是快速排序通常是用於排序的最佳實用選擇，這是因為其平均性能相當好，期望的運行時間為O(nlgn)，且O(nlgn)中隱含的常數因子很小，另外它還能夠進行就地排序在虛擬環境中也能很好的工作。
一、快速排序原理
快速排序也和合並排序一樣，基於分治法，分為分解、解決、合並三個步驟；
分解：數組array[low...high]被分為兩個(可能空)子數組array[low...temp-1]和array[temp+1...high]，使得array[low...temp-1]中的每一個元素都小於等於array[temp]，而array[temp+1...high]中的每一個元素都大於array[temp]，下標temp也是在這個過程中被計算出來；
解決：通過遞歸的調用快速排序，對子數組array[low...temp-1]，array[temp+1...high]進行排序；
合並：因為兩個子數組是就地排序的，將他們的合並不需要操作，整個數組array[low...high]是已經排好序的。
二、快速排序實現
[cpp]
#include <iostream>
#include <ctime>
#include <cstdlib>
#define N 10
using namespace std;
//快速排序的遞歸算法
void quickSort(int * array , int low , int high);
//求分割點
int partition(int * array , int low , int high);
//交換兩個變量的值
void exchange(int &a,int &b);
int main()
{
//聲明一個待排序數組
int array[N];
//設置隨機化種子，避免每次產生相同的隨機數
srand(time(0));
for(int i=0 ; i<N ; i++)
{
array[i] = rand()%101;//數組賦值使用隨機函數產生1-100之間的隨機數
}
cout<<"排序前："<<endl;
for(int j=0;j<N;j++)
{
cout<<array[j]<<" ";
}
cout<<endl<<"排序後："<<endl;
//調用快速排序函數對該數組進行排序
quickSort(array,0,N-1);
for(int k=0;k<N;k++)
{
cout<<array[k]<<" ";
}
cout<<endl;
return 0;
}//main
void quickSort(int * array , int low , int high)
{
if(low < high)
{
int temp = partition(array , low , high);
quickSort(array , low , temp-1);
quickSort(array , temp+1 , high);
}
}
int partition(int * array , int low , int high)
{
int i = low - 1;
int x = array[high];
for(int j=low ; j<high ; j++)
{
if(array[j] <= x)//在array[i]左邊都是小於x即array[high]的數，右邊均是大於它的數
{
i += 1;
exchange(array[i],array[j]);
}
}
exchange(array[i+1],array[high]);
return i+1;//所以循環完畢後，i+1就是該數組的分割點
}
void exchange(int &a,int &b)
{ www.2cto.com
int temp = a;
a = b;
b = temp;
}
運行結果：
三、快速排序性能分析
快速排序的運行時間與劃分是否對稱有關，而後者又與選擇了哪一個元素進行劃分有關。如果劃分是對稱的，那麼本算法在漸近意義上與合並排序一樣快，如果劃分是不對稱的那麼本算法在漸進意義上與插入排序一樣慢。下面分別討論快速排序的最壞情況劃分、最家情況劃分、平衡的劃分。
最壞情況劃分：快速排序的最壞情況劃分行為發生在劃分過程中產生的兩個區域分別包含n-1個元素和0個元素的時候。假設算法每次遞歸調用都出現了這種不對稱劃分，劃分的時間代價為O(n)，因為對一個大小為0的數組進行遞歸調用後，返回了T(n)=O(1)，故算法的運行時間可遞歸的表示為：
T(n) = T(n-1) + T(0) + O(n) = T(n-1) + O(n)
從直觀上來看，如果將每一層遞歸的代價加起來，就可以得到一個算術級數(等式(array,2)其和值的量極為O(n^2))利用代換法可以比較直接的證明遞歸式 T(n) = T(n-1) + O(n)的解為 T(n) = O(n^2)。
因此如果在算法的每一層遞歸上，劃分都是最大程度不對稱的，那麼算法的運行時間為O(n^2)，亦即快速排序算法的最壞情況運行時間不如插入排序的好。此外當輸入數組完全排好序時，快速排序的運行時間是O(n^2)，而插入排序的運行時間為O(n)。
最佳情況劃分：在Partition可能做的最平衡劃分中，得到的兩個子問題的大小都不可能大於[n/2]，因為若其中一個子問題的大小為[n/2]，則另外一個子問題的大小必然為[n/2]-1。在這種情況下，快速排序的運行速度要快得多，這時表達其運行時間的遞歸式為：
T(n) <= 2T(n/2) + O(n)
解該遞歸式可得T(n) = O(nlgn)。由於在每一層遞歸劃分的兩邊都是對稱的，因此從漸進意義上來看，算法運行的就更快了。
平衡的劃分： 快速排序的平均情況運行時間與其最佳情況運行時間很接近，而不是非常接近與其最壞情況運行時間(證明原因詳細參考《算法導論》原書第二版P88)，因為任何一種按常數比例進行劃分都會產生深度為O(lgn)的遞歸樹，其中每一層的代價都是O(n)，因而每當按照常數比例進行劃分時，總的運行時間都是O(nlgn)。
