一趟快速排序算法描述:

quad quad quad (1) 初始化i=0，j=n-1 , prior=A[0]

quad quad quad(2) 从 j 处从右向左开始扫描 (j–) ，直到找到第一个 A[j]<prior 的位置，令 A[i]=A[j]

quad quad quad(3) 从 i 处从左向右开始扫描 (i++) ,直到找到第一个 A[i]>prior 的位置，令 A[j]=A[i]

quad quad quad (4) 重复 (2)(3) 直到 i=j ，令 A[i]=prior ,快速排速完成

时间复杂度分析:

经过上述一趟快速排序，我们只确定了一个元素的最终位置，我们最终需要经过n趟快速排序才能将一个含有 n 个数据元素的序列排好序，下面我们来分析其时间复杂度.

设 n 为待排序数组中的元素个数， T(n) 为算法需要的时间复杂度，则

quad quad quad quad quad quad quad T(n)=left { array{D(1)&n le 1/D(n)+T(I_1)+T(I_2)&n>1 }right.

其中 D(n)=n-1 ,是一趟快排需要的比较次数，一趟快排结束后将数组分成两部分 I_1 和 I_2

最好时间复杂度:

核心点:最好情况下，每一次划分都正好将数组分成长度相等的两半

quad quad quad quad quad quad quad T(n)=left { array{D(1)&n le 1/D(n)+T(frac{n}{2})+T(frac{n}{2})&n>1 }right.

begin{align}所以:T(n)&=D(n)+2T(n/2)/ &=D(n)+2D(n/2)+4T(n/4)/ &vdots / &=D(n)+2D(n/2)+···2^kD(n/2^k)/ &=n-1+2(frac{n}{2}-1)+···2^k(frac{n}{2^k}-1)/ &=n-1+n-2+···n-2^k/ &because k=log_2n / &therefore原式= nlog_2n-2n+1in O(nlog_2n) end{align}

最坏时间复杂度:

核心点:最坏情况下，每一次划分都将数组分成了0和n-1两部分

quad quad quad quad quad quad quad T(n)=left { array{D(1)&n le 1/D(n)+T(0)+T(n-1)&n>1 }right.

begin{align}所以:T(n)&=D(n)+T(n-1)/ &=D(n)+D(n-1)+T(n-2)/ &vdots / &=D(n)+D(n-1)+···+D(2)+D(1)/ &=n-1+n-2+···+1+0/ &=frac{n(n-1)}{2}in O(n^2)/ end{align}

平均时间复杂度:

核心点:任意一种划分情况出现的概率都相等

所有的划分情况为： left { array{I_1=0& I_2=n-1/I_1=1&I_2=n-2/vdots / I_1=n-1 &I_2=0 }right.

begin{align}所以:T(n)&=D(n)+frac{1}{n}sum_{i=0}^{n-1}[T(i)+T(n-i)]/ &=D(n)+frac{2}{n}sum_{i=0}^{n-1}T(i)···(1)/ &because T(n-1)=D(n-1)+frac{2}{n-1}sum_{i=0}^{n-2}T(i)···(2)/ &therefore n*(1)-(n-1)*(2)得:/ nT(n)-(n-1)T(n-1)&=nD(n)+2sum_{i=0}^{n-1}T(i)-(n-1)D(n-1)-2sum_{i=0}^{n-2}T(i)/ &=nD(n)-(n-1)D(n-1)+2T(n-1)/ &=2(n-1)+2T(n-1)/ &移项得/ &n*T(n)=(n+1)T(n-1)+2(n-1)/ &等式两边同除n(n+1)得/ &frac{T(n)}{n+1}=frac{T(n-1)}{n}+frac{2(n-1)}{n(n+1)}/ &令B_n=frac{T(n)}{n+1},得/ &B(n)=B(n-1)+frac{2(n-1)}{n(n+1)}/ 下面通过递归求解B(n)的&表达式，然后将B(n)带回来求T(n)/ B(n)&=B(n-1)+frac{2(n-1)}{n(n+1)}/ &=B(n-2)+frac{2(n-2)}{(n-1)n}+frac{2(n-1)}{n(n+1)}/ &vdots / &=B(1)+sum_{i=1}^nfrac{2(i-1)}{i(i+1)}/ &=sum_{i=1}^nfrac{2(i+1)-4}{i(i+1)}/ &=sum_{i=1}^n[frac{i}{2}-frac{4}{i(i+1)}]/ &because sum_{i=1}^nfrac{4}{i(i+1)}=4sum_{i=1}^n[frac{1}{i}-frac{1}{i+1}]=4[1-frac{1}{n+1}]=4frac{n}{n+1}/ &because sum_{i=1}^nfrac{1}{i}approx ln(n)+0.577/ &therefore B(n)=ln(n)+0.577-4frac{n}{n+1}/ &将其回代进B_n=frac{T(n)}{n+1}/ &得T(n)=(n+1)ln(n)-4n+0.577(n+1)in O(nlog_2n) end{align}

综上:快速排序最好时间复杂度为 O(nlog_2n) ,最坏时间复杂度为 O(n^2) ,平均时间复杂度为 O(nlog_2n)

快速排序的一些改进方案：

(1) 将快速排序的递归执行改为非递归执行

(2) 当问题规模 n 较小时 (n le 16) ,采用直接插入排序求解

(3) 每次选取 prior 前将数组打乱

(4) 每次选取 frac{E[first]+E[Last]}{2} 或 frac{E[first]+E[last]+E[(first+last)/2]}{3} 作为 prior