快速排序代碼如下：
void quickSort(int a*, int p, int r)
{
if(p < r)
{
int q = partition(a, p, r); //劃分
quickSort(a, p, q-1);
quickSort(a, q+1, r);
}
}
每一趟的工作量 = 子問題的工作量 + 劃分的工作量（即劃分的比較次數(shù)）
下圖展示了n種可能的輸入：
每一次劃分的比較次數(shù)為 n-1，則工作量總和有：
上述工作量總和可簡寫為
假設(shè)首元素排好序在每個位置是等概率的蘸泻，則有:
下面利用差消法化簡上述遞推方程茄菊，即
首先套耕，兩邊同時乘n，有
將帶入，得：
為了滅掉瘫絮，
得：
也就是：
對兩邊同時除以
得
對向下寫出所有等式：
迭代求解齐佳，將這些等式帶回去得：
因為私恬，
所以，
綜上炼吴，
