快速排序性能分析

Quick_Sort Analysis of Capability

在决策树计算模型下,任何一个基于比较来确定元素相对位置的排序算法需要的计算时间是Ω(nlog2n).如果能设计一个需要O(nlog2n)时间的排序算法,在渐近的意义上,这个排序算法就是最优的.由C.A.R.Hoare发明的快速排序算法它在平均情况下需要O(nlog2n)时间.本文就该算法在最好情况下、最坏情况下、平均情况下的性能进行分析.

The Analysis of Quick_Sort Capability Under the calculating model of strategic tree,any order of algorisim based on comparison setting relatine location of element,while needs time of calculating is Ω(nlogn).If an order of algorisim of Ω(nlogn) time needed can be devised,the order of algorisim is the best one in a sense of advanling step by step.The Quick Sorting order of algorisim unvented gradually in an orderly way by C.A.R.Hoare nedds Ω(nlogn) time under an average condition.The thesis analyses the performance of the order of algorisin under the best,worst and average conditions.