原文地址：
快速排序的算法復雜度分析
以下是快排的java算法：
public class QuickSort {
public static void quickSort(int a[], int start, int end) {
if (start >= 0 && end <= a.length - 1 && start < end) {
int low = start;
int high = end;
int splitKey = a[start];
while (start < end) {
while (start < end && a[end] >= splitKey) end--;
a[start] = a[end];
while (start < end && a[start] <= splitKey) start++;
a[end] = a[start];
}
a[end] = splitKey;
quickSort(a, low, start - 1);
quickSort(a, start + 1, high);
}
}
public static void quickSort(int a[]) {
quickSort(a, 0, a.length - 1);
}
}
大家都知道快排的時間復雜度是O(n*ln[n])己沛，那么這個復雜度是如何計算出來的呢旱眯？
最好的情況下劳淆，每次劃分對一個記錄定位后肖抱，要記錄的左側(cè)子序列與右側(cè)子序列的長度相同。在具有n個記錄的序列中躯畴，一次劃分需要對整個待劃分序列掃描一遍爵政，所需的時間為O(n)及汉。
設是對n個記錄的序列進行排序的時間稠炬，每次劃分后焕阿，正好把劃分區(qū)域分為長度相等的連個子序列，顯然T(0)=T(1) =1,則有：
image.png
最壞的情況下酸纲，待排序的記錄序列正序或逆序捣鲸，每次劃分只能得到一個比上一次劃分少一個記錄的子序列瑟匆，（另一個子序列為空）闽坡。此時，必須經(jīng)過n-1次遞歸調(diào)用才能把所有記錄定位愁溜，而且第i趟劃分需要經(jīng)過n-i次比較才能找個才能找到第i個記錄的位置疾嗅，因此時間復雜度為
image.png
平均情況下，設軸值記錄的關(guān)鍵碼第k忻嵯蟆（1≤k≤n）,則有：
image.png
由上式可推出如下兩式：
image.png
兩式相減,然后兩邊同除以n(n+1)得
image.png
又因為f(n)單調(diào)遞減代承，單調(diào)有界數(shù)列極限定理，所以f(n)有界
image.png
此數(shù)稱為歐拉常數(shù)渐扮，
約為 0.57721566490153286060651209
所以
image.png
所以
image.png
**如果有何處不當论悴，請不吝賜教掖棉，一定多加完善。謝謝 **
參考資料：
【1】《算法設計與分析》第二版 王紅梅
