Question

排序算法时间复杂度

Answer 1

排序算法的时间复杂度是若文件的初始状态是正序的，一趟扫描即可完成排序。

比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，是不会再交换的。

各种常用的算法，对时间复杂度的情况是这样。直接插入排序，是n平方的时间复杂度。直接选择排序是n平方的时间复杂度，冒泡排序也是n平方的时间复杂度。快速排序，希尔排序，和归并排序，都是n×（logn）的时间复杂度。

次线性时间

对于一个算法，若其匹配T(n) = o(n)，则其时间复杂度为次线性时间（sub-linear time或sublinear time）。实际上除了匹配以上定义的算法，其他一些算法也拥有次线性时间的时间复杂度。例如有O(n)葛罗佛搜索算法。