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

Question

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

Answer 1

正确答案：A,B
试题62、63分析本题主要考查排序算法。本题给出的数组如果采用直接插入排序，那么其排序过程如下：首先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次。快速排序的基本思想是：（1）以某个元素为支点（通常是第一个元素），通过比较关键码和交换记录，将待排序的序列分成两个区间。其中左区间中所有元素的关键字均不大于支点元素的关键字，而右区间中所有元素的关键字均不小于支点元素的关键字。称此过程为一次划分；（2）分别对左右区间的待排序序列，再按照以上方法进行划分，直到整个序列按关键字有序为止。由于本题给出的例子基本是从小到大有序，不适合采用快速排序发，其总共需要的比较次数为15次。参考答案（62）A（63）B