Question

就平均性能而言,目前最好的内排序方法是( )排序法

Answer 1

就平均性能而言，目前最好的内排序方法是快速排序法。

测试平均性能之所以困难，是因为在这个概念中一个概率的因素。如果，程序最终必须产生一个特定结果，那么，你可以确定一个测试程序的运行结果是正确还是错误。相反，如果你在测试平均性能，那么对于一个单独的测试用例，无法判断运行结果是否正确。

快速排序算法开始时挑选序列中的一个特定元素开始排序，叫做pivot。然后，快速排序算法调整元素的顺序，使得小于等于中心数据的元素位于中心数据的前面，所有大于中心数据的元素排在中心数据的后面。最后，快速排序算法递归调用，来完成对这两部分元素的排序。

sort函数实现了快速排序算法，快速排序算法平均可以在 O(n log n) 时间内对含有n个元素的序列进行排序。除了这个平均性能之外，如果选择了“不幸”的输入情况，快速排序的运行时间会比平均时间长很多，比如，某些情况下快速排序的时间复杂度可以达到O(n2)。

快速排序法一般指快速排序算法。 快速排序（Quicksort），计算机科学词汇，适用领域Pascal，c++等语言，是对冒泡排序算法的一种改进。