考研题1998年中国科学技术大学( )

若需在O(log2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方法是【 】。

A、快速排序

B、堆排序

C、归并排序

D、直接插入排序

归并排序

快速排序和堆排序的时间复杂度都是O(nlog2n),但这两种方法都是不稳定的。

直接插入排序的时间复杂度是O(n2),是稳定的。

归并排序的时间复杂度是O(nlog2n),是稳定的排序方法。

考研题2000年复旦大学( )

堆排序是不是一种稳定的排序方法?为什么?

堆排序不是一种稳定的排序方法。

在堆调整的过程中,关键字进行比较和交换时所走的路线是沿着根结点到叶子结点,对于相同的关键字可能存在后面的关键字先被调到前面的情况,因而堆排序是不稳定的。

考研题1998年中国科学院软件研究所( )

若要尽可能快地完成对实数数组的排序,且要求排序是稳定的,应该选【 】。

A、快速排序

B、堆排序

C、归并排序

D、基数排序

归并排序

基数排序、归并排序是稳定的内部排序方法,所有时间复杂度为O(n2)的简单排序法也是稳定的;

快速排序、堆排序和希尔排序等时间性能较好好的排序方法都是不稳定的;

基数排序不能对实数排序。

考研题1998年清华大学( )

如果待排序序列中两个数据元素具有相同的值,在排序前后它们的位置发生颠倒,则称该排序算法是不稳定的,【 】就是不稳定的排序算法。

A、起泡排序

B、归并排序

C、Shell排序

D、直接插入排序

E、简单选择排序

简单选择排序

考研题1999年中国科学院计算机技术研究所( )

若有n个元素已构成一个小根堆,那么如果增加一个元素Kn+1,请用文字简要说明如何在log2n的时间内将其重新调整为一个堆。

将Kn+1插入数组的第n+1个位置(即作为一个树叶插入),然后将其与双亲比较,若它大于其双亲则停止调整,否则将Kn+1与其父亲交换,重复地将Kn+1与新的双亲比较,算法终止于Kn+1大于等于其双其双亲或Kn+1本身已上升为根。