试题-下面哪种排序的平均比较次数最少（）

题目

下面哪种排序的平均比较次数最少（）

A.插入排序

B.选择排序

C.堆排序

D.快速排序

解答

正确答案是 D

快排平均：T(n)=2T(n/2)+n ==>> T(n)=nlog(n) 堆排序平均：每次下滤，两个儿子比较，然后与父亲比较，因为一般下滤logn层，每次共比较2logn，所以n*2logn

C 3条回复评论

粽子

尽管快速排序的最坏时间为O(n² )，但就平均性能而言，它是基于关键字比较的内部排序算法中速度最快者，快速排序亦因此而得名。它的平均时间复杂度为O(nlgn)。应该选D吧

发表于 2018-10-13 14:17:42

米米大户

综合来说，快排算是综合性能最好的内部排序算法了。

发表于 2018-10-13 14:17:31

老干妈拌面

我是这样理解的：快排平均：T(n)=2T(n/2)+n ==>> T(n)=nlog(n) 堆排序平均：每次下滤，两个儿子比较，然后与父亲比较，因为一般下滤logn层，每次共比较2logn，所以n*2logn 这里说的是大概，在这里上下浮动~~

发表于 2018-10-13 14:17:08