比较次数达到树形选择排序水平，同时又不增加存储用以保存树形选择排序中比较的中间结果的排序方

趟结果是__________。

A．13，38，65，97，76，49，27，50

B．13，27，38，49，50，65，76，97

C．97，76，65，50，49，38，27，13

D．13，38，65，50，76，49，27，97

对n个记录文件进行快速排序，平均比较次数为__________。

A．O(nlog2n)

B．O(n2)

C．O(log2N)

D．O(n)

进行上机实习。要求： (1)被排序的对象由计算机随机生成，长度分别取20，100，500三种。 (2)算法中增加比较次数和移动次数的统计功能。 (3)对实习的结果作比较分析。

出Shell排序(取d1=8)的各趟运行结果。

添入元素的建堆算法。

t[]，int last){ int current； int smallest； int holdData； int walker； for(current=0；current＜last；current++){ smallest=current； for(walker=current+1；walker＜=last；walker++) if(list[walker]＜list[smallest])smallest=walker； holdData=list[current]； list[current]=list[smallest]； list[smallest]=holdData； } return； }

在待排序的元素序列基本有序的前提下，效率最高的排序算法是_______。

A．插入排序

B．选择排序

C．快速排序

D．归并排序

_________。

A．已经有序

B．部分有序

C．完全无序

D．逆序

特别试一下“增量除以3”的方法，该方法对长度为n的序列以n／3，n／9…为增量。 void shellsort(Sortobject*pvector){ ／*Shell sort*／ int incr,start； for (incr=pvector-＞n／2；incr＞0；incr／=2) ／*for each increment*／ for(start=0；start＜incr；start++) ／*Sort each sublist*／ inssort2(pvector，start，incr)； } ／*Modified version of Insertion Sort for varying increments*／ void insson2(SortObject*pvector,int start，int incr){ int i，j； RecordNode temp； for(i=start+incr；i＜pvector-＞n；i+=incr){ temp=pvector-＞record[i]； for(j=i；(j＞=incr)&&(temp．key＜pvector-＞record[j-incr]．key)；j-=incr) pvector-＞record[j]=pvector-＞record[j-incr]； pvector-＞record[j]=temp； } }