和球有料精有有转码博打中 C刀 品n cn logion 品和 4程h cn log10/9 n 品n 器n C拉 a≤Cn 间题5： ≤C 你能香借助这个图解释影响 O(nlgn) Quicksort效率的因素？
In fact,any split of cont proportioality yiedsr of ept)where thecsta level is O().The rnning time is therefore ()whenever the split has constant rorionity. 问题⑥； 你看了这句话有什么想法？
问题7 为什么直观上也会觉得快速排序的平均效 率更接近最好情况，而不是最坏情况？ 直觉对于探索很重要。 “大胆假设，小心求证！” EE1A1EEB1111 Θ(n) A811211801118888i Θ(n) 0 2- (n-1)/2 (n-1)/2 (n-1)/2-1 (n-1)/2 (a) (b)
直觉对于探索很重要。 “大胆假设，小心求证！
Worst-Case Performance of Quicksort T(n)=max (T(q)+T(n-q-1))+(n) 0≤g≤n-1 g是Partition的返回值。 问题8： 你能说说解这个递 归的策略吗？ Guess and verifying
Worst-Case Performance of Quicksort q是Partition的返回值。 Guess and verifying
再次观察partition过程 PARTITION(A,p,r) 1 x=A[r] 2i=p-1 3 for j=ptor-1 4 ifA[j]≤x 5 i=i+1 6 exchange A[i]with A[j] 7 exchange A[i+1]with A[r] 8 return i +1
再次观察partition过程