你这答案不对啊.
方式： 平均 最坏 最好
插入 n^2 n^2 n
希尔 n^1.3 / /
冒泡 n^2 n^2 n
快速 nlogn n^2 nlogn
选择 n^2 n^2 n^2
堆排 nlogn nlogn nlogn
归并 nlogn nlogn nlogn
基数 d(n+r) d(n+r) d(n+r)
之所以有最好最坏就是因为受到了初始状态的影响,所以三个值全一样的就是不受影响的,几个外排你无视好了,但F堆排也肯定是答案之一.
最慢的选择排序就不说了,你自己看下算法就明白了.
归并排序是将数组不断的二分直至子数组长度为1,然后再开始合并,因此它的时间复杂度只与数组长度相关,而每一层的比较次数都是O(n)级别,共logn层,所以无论如何都是O(nlogn)
堆排则是通过建立特殊的数据结构,将每一次的比较结果都通过最大/小堆记录了下来,你可以理解为算法比较过a与b的大小之后,直道结束,它都知道a与b的大小了,而不需要再次比较,因此在堆建立完之后,要找出一个数的大小序号所需要的计算量都是O(logn)级别,对于共n个数的排序,一共就是O(nlogn),跟归并相比虽然都是n乘logn,但是意义是不同的.
然后就是你这个题有问题,不能说比较次数,是比较次数的量级,也就是时间复杂度表达式中最高次项及其系数是相同的,而无论是哪一种排序方式,准确地比较次数或多或少都会受到初始状态的影响