摘要: LetQnbe the random number of comparisons made by quicksort in sortingndistinct keys when we assume that alln! possible orderings are equally likely. Known results concerning moments forQndo not show how rare it is forQnto make large deviations from its mean. Here give a good approximation to probability such deviation and find this quite small. As well as basic quicksort, consider variant which partitioning key chosen median (2t+1) keys.
core.ac.uk
elsevier.com
ualberta.ca 
sci-hub.se 参考文章(12)
P. Hennequin, Combinatorial analysis of quicksort algorithm Theoretical Informatics and Applications. ,vol. 23, pp. 317- 333 ,(1989) , 10.1051/ITA/1989230303171
Donald Ervin Knuth, The Art of Computer Programming, 2nd Ed. (Addison-Wesley Series in Computer Science and Information Addison-Wesley Longman Publishing Co., Inc.. ,(1978)
Tony Hoare, Algorithm 63‚ Partition; Algorithm 64‚ Quicksort; Algorithm 65‚ Find Communications of The ACM. ,vol. 4, ,(1961)
J. Neveu, T. P. Speed, Discrete Parameter Martingales ,(1975)
Mireille Régnier, A limiting distribution for quicksort Theoretical Informatics and Applications. ,vol. 23, pp. 335- 343 ,(1989) , 10.1051/ITA/1989230303351
Uwe Rösler, A limit theorem for “quicksort” Theoretical Informatics and Applications. ,vol. 25, pp. 85- 100 ,(1991) , 10.1051/ITA/1991250100851
Hosam M. Mahmoud, Evolution of random search trees ,(1991)
David Williams, Probability with martingales ,(1991)
Ryan Hayward, Colin McDiarmid, Strong concentration for Quicksort symposium on discrete algorithms. pp. 414- 421 ,(1992)
Luc Devroye, A note on the height of binary search trees Journal of the ACM. ,vol. 33, pp. 489- 498 ,(1986) , 10.1145/5925.5930