考研题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本身已上升为根。

暂无分析

考试题1998年清华大学( )  

如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序序列,用【 】方法最快

A、起泡排序

B、快速排序

C、Shell排序

D、堆排序

E、简单选择排序

快速排序

起泡排序与简单选择排序均需要4趟,才能找到题目所需求的序列。

Shell排序只有将这1000个元素全部排序完成,才能找到题目所要求的序列。

堆排序需要先建立初始小顶堆后,再经过4次堆调整才能得到。

快速排序可以每次对第一个子序列进行划分,直到子序列长度小于等于4,若长度不足4,则对第二个子序列划分出相应长度的子序列即可。

考研题1992年清华大学( )  

回答问题并写出推导过程:

对50个整数进行快速排序需进行关键字间比较次数可能达到的最大值和最小值各为多少?

最大比较次数:在关键字有序的情况下,为

49+48+...+1=1225

最小比较次数:判定树如下图所示(树中结点,所示数字为此子序列所含关键字个数)

判定树 50 快速排序

最少比较次数:49+47+43+35+19=193.

当初始记录有序或基本有序时,快速排序将蜕化为起泡排序,关键字有序时比较次数最大。

若每次都分割成长度相等或仅相差1的子序列时,比较次数最少。而每次划分所进行比较的次数是该子序列中关键字个数减1,因此通过快速排序的判定树可求出总的比较次数。

考研题2000年东北大学( )  

在起泡(冒泡)排序过程中,有的关键字在某趟排序中可能朝着与最终排序相反的方向移动,请举例说明之。

快速排序过程中有没有这种现象?

例如(4,3,2,1),第一趟起泡后为(3,2,1,4),关键字3的位置被移动到首位,朝着与最终排序相反的方向移动。

快速排序过程中没有此现象。因为经过一趟排序的划分所确定的枢轴记录的位置就是此记录最终的位置,而且所有比枢轴记录小的记录均被移到枢轴之前,所有比枢轴记录大的记录均被移到枢轴右之后。

起泡排序每一趟只能将序列中最大(或最小)关键字移到正确位置,其它关键字可能在相互交换中朝着与最终排序相反的方向移动。

快速排序每一趟不仅能将枢轴记录移动到正确位置,而且其它记录移动的方向也和其最终的位置方向一致。

考研题1999年清华大学( )  

快速排序的最大递归深度是,最小递归深度是

n;[log2n]+1

若每趟排序后,枢轴位置均偏向于序列的一端,则为最坏情况,栈的最大深度为n。

若每趟排序都将记录序列均匀地分割或长度相近的两个子列,遇为最好情况,栈最大深度为[log2n]+1。

【扩展:改进快速排序算法】在一趟排序后比较分割所得两部分的长度,先对长度短的子序列进行快速排序,则栈的最大深度可降为O(log2n)。

考研题1998年北京邮电大学( )  

快速排序的速度在所有排序方法中为最快,而且所需附加的空间也最少。

快速排序需要一个额外的栈空间,比堆排序所需的空间要大。