首页 > 试题广场 >

下列排序算法中,其时间复杂度和记录的初始排列无关的是()

[单选题]
下列排序算法中,其时间复杂度和记录的初始排列无关的是()
  • 插入排序
  • 堆排序
  • 快速排序
  • 冒泡排序
推荐
选B。考察的是排序算法的原理。
  • A插入排序:将待排序的元素插入到已排序的序列中,如果都是排序好的这最好O(N),如果是逆序最坏O(N2)
  • B堆排序:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,依次循环。最好和最坏一样O(N*log2N)
  • C快速排序:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。最好将基准数划分的很均匀,O(N*log2N)。当待排序的序列为正序或逆序排列时,且每次划分只得到一个比上一次划分少一个记录的子序列,最坏O(N2)
  • D冒泡排序:相邻元素比较交换。最好顺序,不用交换位置O(N),最坏是逆序情况为O(N2)

编辑于 2019-06-19 14:26:30 回复(0)

都考虑有序的初始状态

  • 插入排序:每个元素值需要看前面一个元素即可完成,时间复杂度降低为O(n)
  • 快速排序:每次partition的结果是只排了一个元素,时间复杂度提高到O(n^2)
  • 冒泡排序:遍历一个发现没有发生交换,结束程序,时间复杂度降低为O(n)
  • 堆排序:每次都得交换数组第一个元素和最后一个元素,时间复杂度不变。

需要注意的一点是,该题的冒泡是由标志的冒泡,也就是改进后的,此时没有发生交换则程序结束

发表于 2019-06-18 20:03:52 回复(0)
发表于 2019-08-05 22:22:44 回复(0)