首页 > 试题广场 >

以下排序算法平均时间复杂度和插入排序相同的是()

[单选题]
以下排序算法平均时间复杂度和插入排序相同的是()
  • 冒泡排序
  • 堆排序
  • 希尔排序
  • 归并排序
网上很多这种图
发表于 2020-05-04 22:33:43 回复(1)
/**
 * @author yyl
 * @date 2018/11/17 下午11:06
 * 排序法	平均时间	最差情形	    稳定度	额外空间	 备注
 * 冒泡	    O(n2)	  O(n2)  	稳定  	O(1)	n小时较好
 * 选择   	O(n2)	  O(n2) 	不稳定   O(1)	n小时较好
 * 插入   	O(n2)	  O(n2)	    稳定 	O(1)	大部分已排序时较好
 * 基数   	O(logRB)  O(logRB)	稳定	    O(n)
 * 快速	    O(nlogn)  O(n2)  	不稳定	O(nlogn)	n大时较好
 * 归并   	O(nlogn)  O(nlogn)  稳定	    O(1)	n大时较好
 * 堆	    O(nlogn)  O(nlogn)	不稳定	O(1)	n大时较好
 */

发表于 2019-08-12 14:45:53 回复(0)
我给记错了:最好和最坏的时间复杂度都一样的是:归并排序算法。
同时,选择排序,插入排序和冒泡排序的时间复杂度都是n^2
编辑于 2020-05-26 23:15:37 回复(0)
维基百科 插入排序

发表于 2019-07-07 11:53:51 回复(0)