摘要：在决策树计算模型下，任何一个基于比较来确定元素相对位置的排序算法需要的计算时间是Ω(nlog2n)。如果能设计一个需要O(nlog2n)时间的排序算法，在渐近的意义上，这个排序算法就是最优的。由C．A．R．Hoare发明的快速排序算法它在平均情况下需要O(nlog2n)时间。本文就该算法在最好情况下、最坏情况下、平均情况下的性能进行分析。
　　关键词：快速排序；算法；性能分析
　　中图分类号：TP312
　　文献标识码：A
　　文章编号：1009—3044(2007)02—10443—02