数据结构考研分类复习真题 第十章 答案[9]

从节省存储空间考虑先选堆排序再选快速排序最后选择归并排序

从排序结果的稳定性考虑选择归并排序堆排序和快速排序都是不稳定排序

从平均情况下排序最快考虑先选择快速排序

()堆排序快速排序归并排序 ()归并排序 ()快速排序 ()堆排序

平均比较次数最少: 快速排序; 占用空间最多: 归并排序; 不稳定排序算法:快速排序堆排序希尔排序

求前k个最大元素选堆排序较好因为在建含n个元素的堆时总共进行的关键字的比较次数不超过n 调整建新堆时的比较次数不超过logn次在n个元素中求前k个最大元素在堆排序情况下比较次数最多不超过n+klogn

稳定分类是指若排序序列中存在两个关键字值相同的记录Ri与Rj(Ki=Kji≠j)且Ri领先于Rj若排序后Ri与Rj的相对次序保持不变则称这类分类是稳定分类(排序)否则为不稳定分类

AC和E是稳定分类(排序)B和D是不稳定分类(排序)

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []