● 将数组{1,1,2,4,7,5}从小到大排序,若采用(62)排序算法,则元素之间需要进行的比较次数最少,共需

答案：A

解析：

答案：B

解析：

答案：B

解析：

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

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


问题 2 答案解析：B
同31题解析

正确答案：
 

正确答案：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）。

正确答案：A
本题主要考查排序算法。本题给出的数组如果采用直接插入排序，那么其排序过程如下：首先1和1比较找到合适的插入位置，然后2和1比较，找到合适的插入位置；然后4和2比较，找到4的合适插入位置，然后7和4比较，找到7的合适插入位置，然后5和7比较，因为5比7小，因此要与4比较，然后就找到了5的合适位置，整个排序过程结束。总的比较次数为1+1+1+1+2=6次。归并排序的算法思想是将两个相邻的有序子序列归并为一个有序序列，然后再将新产生的相邻序列进行归并，当只剩下一个有序序列时算法结束。其过程如下：1和1比较，然后归并，2和4比较，然后归并，7和5比较，然后归并，解析来将再将[1,1]和[2,4]归并，用2分别与两个1比较得到[1,1,2,4],然后再用[1,1,2,4]与[5,7]归并。这时，用5与[1,1,2,4]中每个元素分别比较一次，最后即可得到整个有序序列。总的比较次数为：1+1+1+2+4=9次。堆排序的基本思想是先将序列建立堆，然后输出堆顶元素，再将剩下的序列建立堆，然后再输出堆顶元素，依此类推，直到所有元素均输出为止。因此在堆排序过程中，最重要的就是建堆。本题中给出的数组序列就是一个小顶堆，然后输出堆顶，将剩下的部分调整为小顶堆，调整的过程为，首先将最后一个元素5置换到堆顶，然后用5与左孩子结点比较，由于大于左孩子，因此与其置换位置，然后值为5的结点仍然大于其左孩子结点，再置换位置，这样就得到了新的小顶堆，这个过程总共比较2次。后面的排序过程是同样的道理。本题采用堆排序算法总共的比较次数为7次。快速排序的基本思想是：①以某个元素为支点（通常是第一个元素），通过比较关键码和交换记录，将待排序的序列分成两个区间。其中左区间中所有元素的关键字均不大于支点元素的关键字，而右区间中所有元素的关键字均不小于支点元素的关键字。称此过程为一次划分；②分别对左右区间的待排序序列，再按照以上方法进行划分，直到整个序列按关键字有序为止。由于本题给出的例子基本是从小到大有序，不适合采用快速排序发，其总共需要的比较次数为15次。

正确答案：A

正确答案：A,B