摘要: Let Qn be the random number of comparisons made by quicksort in sorting n distinct keys, when we assume that all n! possible orderings are equally likely. Known results concerning moments for do not show how rare it is to make large deviations from its mean. Here give a good approximation probability such deviation, and find this quite small. As well as basic consider variant which partitioning key chosen median (2t+1) keys.
参考文章(2)
P. Hennequin, Combinatorial analysis of quicksort algorithm Theoretical Informatics and Applications. ,vol. 23, pp. 317- 333 ,(1989) , 10.1051/ITA/1989230303171
Colin McDiarmid, Surveys in Combinatorics, 1989: On the method of bounded differences Cambridge University Press. pp. 148- 188 ,(1989) , 10.1017/CBO9781107359949.008