目录: 标题| 题干| 答案| 搜索| 相关
问题

对于长度为n的线性表,在最坏的情况下,下列各排序法所对应的比较次数中正确的是


对于长度为n的线性表,在最坏的情况下,下列各排序法所对应的比较次数中正确的是A.插入排序为n/2 B.插入排序为n C.快速排序为n D.快速排序为n(n-1)/2

  • A插入排序为n/2
  • B插入排序为n
  • C快速排序为n
  • D快速排序为n(n-1)/2
参考答案
参考解析:

插入排序是指将无序子序列中的一个或几个记录插入到有序序列中,从而增加记录的有序子序列的长度。在最坏的情况下,当插入第一个元素时,需要比较的次数为0,插入第二个元素时,需要比较一次,插入第n个元素时,需要比较n-1次。那么直到将n个元素都插入序列中,需要比较次数的总和为0+1+2+…+n-1。因此,在最坏情况下,插入排序需要比较的次数为n(n-1)/2。快速排序的基本思想是通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可以分别对这两部分记录继续进行排序,以达到整个序列有序。它在最坏情况下,需要比较的次数也为n(n-1)/2。因此,本题的正确答案选D。

分类:其他