●用插入排序和归并排序算法对数组<3，1，4，1，5，9，6，5>进行从小到大排序，则分别需要进行 (65) 次数组元素之间的比较。(65)A．12,14B．10,14C．12,16D．10,16

题目

●用插入排序和归并排序算法对数组<3，1，4，1，5，9，6，5>进行从小到大排序，则分别需要进行 (65) 次数组元素之间的比较。

(65)

A．12,14

B．10,14

C．12,16

D．10,16

相似考题

1.对初始状态为递增序列的数组按递增顺序排序，最省时间的是插入排序算法，最费时间的算法是()A.堆排序B.快速排序C.插入排序D.归并排序

2.将数组{1，1，2，4，7，5}从小到大排序，若采用（62）排序算法，则元素之间需要进行的比较次数最少，A.直接插入B.归并C.堆D.快速

3.● 将数组{1，1，2，4，7，5}从小到大排序，若采用（62）排序算法，则元素之间需要进行的比较次数最少，共需要进行（63）次元素之间的比较。 A.直接插入 B.归并 C.堆 D.快速 A.5 B.6 C.7 D.8

4.●将数组{1，1，2，4，7，5}从小到大排序，若采用(62)排序算法，则元素之间需要进行的比较次数最少，共需要进行(63)次元素之间的比较。(62)A．直接插入B．归并C．堆D．快速(63)A． 5B． 6C． 7D． 8

参考答案和解析
正确答案：A
更多“●用插入排序和归并排序算法对数组&lt;3,1,4,1,5,9,6,5&gt;进行从小到大排序,则分别需要进行 (65) ”相关问题

  • 第1题：

    采用插入排序算法对n个整数排序，其基本思想是：在插入第i个整数时，前i-1个整数己经排好序，将第i个整数依次和第i-1, i-2, ...个整数进行比较，找到应该插入的位置。现采用插入排序算法对6个整数{5.2.4.6.1.3}进行从小到大排序，则需要进行（31）次整数之间的比较。对于该排序算法，输入数据具有（32）特点时,对整数进行从小到大排序，所需的比较次数最多。

    A.9

    B.10

    C.12

    D.13


    正确答案：C
    一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：（1）从第一个元素开始，该元素可以认为已经被排序（2）取出下一个元素，在已经排序的元素序列中从后向前扫描（3）如果该元素（已排序）大于新元素，将该元素移到下一位置（4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置（5）将新元素插入到下一位置中（6）重复步骤2~5对于本题：{5.2.4.6.1.3}第一趟：第一次比较，5大于2（新元素），元素5向后位移一位，而5之前无数据，即将2插入到1位，2，5第二趟：第一次比较，5大于4（新元素），元素5向后移一位，再进行第二次比较，2小于4（新元素），即将4插入2之后的一位，即2，4，5依次类推，，，所以比较的次数为1+2+1+4+4=12如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1）次。平均来说插入排序算法的时间复杂度为O(n^2）。

  • 第2题：

    将数组{1，1，2，4，7，5}从小到大排序，若采用（请作答此空）排序算法，则元素之间需要进行的比较次数最少，共需要进行（ ）次元素之间的比较。

    A.直接插入
    B.归并
    C.堆
    D.快速

    答案：A
    解析：
    直接插入排序算法是：每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第1趟比较前两个数，然后把第2个数按大小插入到有序表中；第2趟把第3个数据与前两个数从前向后扫描，把第3个数按大小插入到有序表中；依次进行下去，进行了（n-1）趟扫描以后就完成了整个排序过程。直接插入排序属于稳定的排序，最坏时间复杂性为（n2），空间复杂度为0（1）。依题意，将数组{1，1，2，4，7，5}从小到大排序，若采用直接插入排序算法，则元素之间需要进行的比较次数最少，共需要进行6次元素之间的比较。

  • 第3题：

    在插入排序、选择排序、交换排序、归并排序算法中,要求内存量最大的是归并排序。（）


    插入排序：按关键字大小每次将一个待排序的元素插入到已排序的序列中，直至所有元素都插入完毕。 选择排序：每次从待排序的元素中选择具有最小（或最大）关键字的元素放到已排序序列的尾部（或头部），直至所有元素都排序完毕。 交换排序：从待排序的元素中选择两个次序相反的元素进行交换，直至任意两个元素的次序都正确。 K.路归并排序：每次将K（K≥2）个已排序的子序列组合在一起，形成一个有序的序列，重复该过程直至得到一个包含所有待排序元素的有序序列。 分配排序：根据元素本身所具有的值将各元素逐一映射到一组有序空间中，最后再依次从有序空间中将各元素取出即形成了排序结果。

  • 第4题：

    采用插入排序算法对n个整数排序，其基本思想是：在插入第i个整数时，前i-1个整数已经排好序，将第i个整数依次和第i-1，i-2，…个整数进行比较，找到应该插入的位置。现采用插入排序算法对6个整数{5，2，4，6，1，3}进行从小到大排序，则需要进行（ ）次整数之间的比较。对于该排序算法，输入数据具有（请作答此空）特点时，对整数进行从小到大排序，所需的比较次数最多。

    A.从小到大
    B.从大到小
    C.所有元素相同
    D.随机分布

    答案：B
    解析：
    采用插入排序算法对6个整数{5，2，4，6，1，3}进行从小到大排序的过程如表所示。

    综上，元素间共比较12次。从上表中的第4步可看出，当待插入的元素比已排序部分的所有元素都要小时，需要比较和移动的元素最多，因此当输入数据序列正好从大到小排列，而需要将其从小到大排序时，元素间的比较次数最多。

  • 第5题：

    55、在最好情况下，下列排序算法中，排序所需比较关键字次数最少的是

    A．冒泡排序和插入排序

    B．归并排序和快速排序

    C．冒泡排序和归并排序

    D．插入排序和快速排序


    B

相关内容