王道数据结构36页第七题

第七题我觉得选B才是正确的，因为数组排序的最优时间复杂度不是O(nlogn)，而是O(n)。比如优化后的冒泡排序就是O(n)。

在编程比赛中…最优的排序都是按nlogn复杂度算的，教材上是不是有理论能排到on就不知道了

不感兴趣

开通SVIP免广告

而且冒泡这种交换类排序再优化应该也不能比快排快了，如果有on算法麻烦楼主贴一下，谢谢

就是如果一开始给定的n个元素的数组就是有序的情况，那么用优化的冒泡排序算法的时间复杂度就是O(n)

你这么说我理解你的意思了，冒泡排序在最优情况下确实一次扫描就可以。不过时间复杂度的定义是在假定最差的情况下统计的时间复杂度，所以答案不是On

堆排序？排序下限就是nlogn。它是说最坏情况下最快要多少。

下载贴吧APP
看高清直播、视频！

分享到: