数据结构与算法：第6章 内部分类

内存中完成：6.1简单的分类算法6.2Shell分类6.3快速分类6.4归并分类6.5堆分类6.6基数分类第6章内部分类（Sorting）分类内部分类外部分类外存上完成：归并分类(Sorting)也叫排序(Ordering)，是将一组数据按照规定顺序进行排列，其目的是为了方便查询和处理。对于给定数组A，经过分类处理之后，满足关系：

A[1].key≤A[2].key≤……≤A[n].key如果在分类之前存在关系

A[i].key=A[j].key(1≤i＜j≤n)经分类后，A[i]和A[j]分别被移至A[i1]和A[j1]，并且i1和j1满足关系

1≤i1＜j1≤n我们称这种分类是稳定的，否则称其为不稳定的分类。按分类时分类对象存放的设备，分成内部分类(internalsorting)和外部分类(externalsorting)。分类过程中数据对象全部在内存中的分类，叫内部分类。分类过程数据对象并非完全在内存中的分类，叫外部分类。分类的种类structrecords{keytypekey;fieldsother;}；typedefrecordsLIST[maxsize];分类表的存储结构影响分类性能的因素比较关键字的次数—当关键字是字符串时，是主要因素。交换记录位置和移动记录的次数—当记录很大时，是主要因素。

012345678910265076301265129751301265265129751301301301937129751438438438863937438751694694694742863937694751742742742694742863937742751751751751076694742863937863863863863863438438694742863937937937937937937如何取消不必要的循环？6.1简单的分类算法6.1.1气泡分类气泡分类算法：VoidBubbleSort(intn,LIST&A){intx,y;for(i=1;i<=n-1;i++)for(j=n;j>=i+1;j--)if(A[j].key<A[j-1])swap(A[j],A[j-1])}Voidswap(x,y)records&x,records&y{recordsw;w=x;x=y;y=w;}=1/2·C2n2+(C3-1/2·C2)·n≤(C2/2+C3)n2当n2≥1时

=Cn2T(n)=O(f(n))=O(C·n2)=O(n2)f(n)=C3n+∑C2·(n-i)i=1n-1算法分析：例：设计双向气泡排序算法，在排序过程中交替改变扫描方向。VoidDoubleBubbleSort(LIST&A,intn){inti=1,flag=1;while(flag){flag=0;for(j=n-i+1;j>=i+1;j--)//较小元素A[j]if(A[j].key<A[j-1].key){flag=1;swap(A[j],A[j-1]);}for(j=i+1;j<=n-i+1;j++)//较大元素A[n-i+1]if(A[j].key>A[j+1].key){flag=1;swap(A[j],A[j+1]);}i++;}}T(n)=O(n2)flag?

初始状态：(265)301751129937863742694076438

第1趟：(265301)751129937863742694076438

第2趟：(265301751)129937863742694076438

第3趟：(129265301751)937863742694076438

第4趟：(129265301751937)863742694076438

第5趟：(129265301751863937)742694076438

第6趟：(129265301742751863937)694076438

第7趟：(129265301694742751863937)076438

第8趟：(076129265301694742751863937)438

第9趟：(076129265301438694742751863937)6.1.2插入分类插入分类算法：voidInsertSort(n,A)Intn;LISTA;{inti,j;A[0].key=-∞;for(i=1;i<=n;i++){j=i;while(A[j].key<A[j-1].key){swap(A[j],A[j-1]);j=j-1;}}}T(n)=O(n2)j=i;temp=A[j]While(temp.key<A[j-1].key){A[j]=A[j-1];j=j-1;}A[j]=temp;

初始状态：265301751129937863742694

076

438

第1趟：076301751

129

937863742694265438

第2趟：076129751301937863742694

265438

第3趟：076129265

301937863742694751438

第4趟：076129265301937863742694751438

第5趟：076129265301438863742

694

751937

第6趟：076129265301438694

742

863751937

第7趟：076129265301438694742863751

937

第8趟：076129265301438694742751

863937

第9趟：076129265301438694742751863

9376.1.3选择分类选择分类算法（冒泡程序）voidSelectSort(n,A)intn;LISTA;{inti,j，lowindex;keytypelowkey;for(i=1;i<n;i++){lowindex=i;for(j=i+1;j<=n;j++)if(A[j].key<A[lowindex].key)lowindex=j;swap(A[i],A[lowindex]);}}T(n)=O(n2)例：设计算法，实现奇偶转换排序。基本思想：第一趟对所有奇数的i，将A[i]和A[i+1]进行比较；第二趟对所有偶数的i，将A[i]和A[i+1]进行比较；

if(A[i]>A[i+1])swap(A[i],A[i+1]);

重复上述二趟交换过程交换进行，直至整个数组有序。问：

(1)结束条件是什么？

(2)实现算法。VoidOESort(LIST&A,intn){inti,flag;do{flag=0;for(i=0;i<n;i+=2)if(A[i]>A[i+1]){flag=1;swap(A[i],A[i+1]);}for(i=1;i<n;i+=2)if(A[i]>A[i+1]){flag=1;swap(A[i],A[i+1]);}}while(flag);}(2)奇偶转换排序算法：(1)结束条件为不产生交换：6.2Shell分类希尔（Shell）排序又称缩小增量法，基本思想为：先取定一个整数d1<n，把全部结点分成d1个组，所有距离为d1倍数的记录放在一组中，在各组内进行直接插入排序；然后取d2<d1，重复上述分组和排序工作，直至取di=1，即所有记录放在一个组中排序为止。特点：每次以不同的增量分组，组内进行直接插入排序，在最后一次作组内直接插入排序时，所有记录“几乎”有序了。“逆序”结点作跳跃移动，提高了排序速度。例：希尔排序过程

初始状态:265301

751

129

937863742

694

076

438第1趟分组d=5:排序结果：265301694076438863742751129937第2趟分组d=2:排序结果：129

076

265

301

438

751

694

863

742

937第3趟分组d=1:排序结果：076129265301438694742751863937VoidShellsort(LIST&A,intn){for(k=n/2;k>=1;k/=2){for(i=k+1;i<=n;i++){x=A[i];j=i-k;while((j>0)&&(x.key<A[j].key)){A[j+k]=A[j];j-=k;}A[j+k]=x;}//组内排序，将x直接插入到组内合适的位置

}}

是C.R.A.Hoare1962年提出的一种划分交换排序。采用的是分治策略(一般与递归技术结合使用)，以减少分类过程之中的比较次数。分解:将原问题分解为若干个与原问题相似的子问题，又称划分求解:递归地求解子问题，若子问题的规模足够小，则直接求解组合:将每个子问题的解组合成原问题的解。6.3快速分类—划分交换分类基本思想：对于：A[1].key,A[2].key,……,A[n].key选定中间值v，使之对某个k有：

A[1].key,A[2].key,……,A[k-1].key＜A[k].key而：A[k+1].key,A[k+2].key,……,A[n].key≥A[k].key然后分别对A[1],…,A[k-1]和A[k+1],…,A[n]作同样的处理。算法要点：（1）中间值v的选择，其位置确定在A[k]

设findpivot(i,j),求A[i].key,…,A[j].key的中间值v。

ⅰv=(A[i].key，A[(i+j)/2].key,A[j].key的中值)ⅱv=从A[i].key到A[j].key

最先找到的两个不同关键字中的最大的。

算法要点（续）：（2）A[i].key,…,A[j].key分割成A[i],…,A[k-1]和A[k+1],…,A[j]

两部分。扫描：令游标L从左（L=i）向右扫描，越过key小于v的记录，直到A[L].key≥v为止；同时令游标R从右（R=j）开始向左扫描，越过key大于等于v的记录,

直到A[R].key＜v的记录A[R]为止；测试：若L>R（L=R+1），成功划分，L是右边子序列的起始下表；交换：若L<R,则swap(A[L],A[R])；重复上述操作，直至过程进行到L>R（L=R+1）为止。Intfindpivot(inti,intj){keytypefirstkey;intk;firstkey=A[i].key;for(k=i;k<=j;k++)if(A[k].key>firstkey)returnk;elsereturni;return0;}找中间值算法:Intpartion(i,j,pivot)Inti,j;keytypepivot;{intL,R;L=i;R=j;do{

swap(A[L],A[R]);while(A[L].key<pivot)L=L+1;while(A[R].key>=pivot)R=R-1;}while(L<=R);returnL;}Voidquicksort(inti,intj){keytypepivot;intpiovtindex,k;pivotindex=findpivot(i,j);if(pivotindex){pivot=A[pivotindex].key;k=partion(i,j,pivot);quicksort(i,k-1);quicksort(k,j);}}分割:[i,……,j][i,…k-1,k,k+1,…j]快速分类调用：quicksort(1,n)T(n)=O(f(n))3562951413时间复杂性和稳定性时间复杂性：T(n)=O(nlog2n)稳定性：是不稳定的分类举例3563954112v=35569334v=5433v=49565v=9655v=6211v=29655433211组合例：对长度为n的记录序列进行快速排序时，所需要的比较次数依赖于这n个元素的初始序列。问：(1)当n=8时，在最好情况下需要进行多少次比较？

(2)给出n=8时的最好情况的初始排序实例。解：n=8n=3n=4n=1n=1n=1n=2n=17次比较2次比较3次比较1次比较(1)共13次(2)如：2313172160301828一次划分后：{18131721}23{306028}二次划分后：{1713}18{21}四次划分后：{28}30{60}三次划分后：{13}1713216028结果：1317182123283060intPartition(inti，intj，intpivot)

{//对A[low..high]做划分，并返回基准记录的位置

while(i<j)//从区间两端交替向中间扫描，直至i=j为止

{

while(i<j&&A[j].key>=pivot)//pivot相当于在位置i上

j--；//从右向左扫描，查找第1个关键字小于pivot的记录A[j]

if(i<j)//表示找到的A[j]的关键字<pivot

A[i++]=A[j]；//相当于交换A[i]和A[j]，交换后i指针加1

while(i<j&&A[i].key<=pivot)//pivot相当于在位置j上

i++；//从左向右扫描，查找第1个关键字大于pivot的记录A[i]

if(i<j)//表示找到了A[i]，使R[i].key>pivot

A[j--]=A[i];//相当于交换A[i]和A[j]，交换后j指针减1

}//endwhile

A[i]=pivot；//基准记录已被最后定位

returni；

}//partition另一种划分方法6.4归并分类合并两个有序序列Voidmerge(l,m,n,A,B)Intl,m,n;LISTA,&B;{inti,j,k,t;i=l;k=l;j=m+1;while((i<=m)&&(j<=n)){if(A[i].key<=A[j].key)B[k++]=A[i++];elseB[k++]=A[j++];}if(i>m)for(t=j;t<=n;t++)B[k+t-j]=A[t];elsefor(t=i;t<=m;t++)B[k+t-i]=A[t];}合并A[l],…,A[m]和

A[m+1],…,A[n]形成新的分类序列

B[l],…,…,B[n]算法时间复杂度T(n)=O(n-l+1){26}{5}{77}{1}{61}{11}{59}{15}{48}{19}{526}{177}{1161}{1559}{1948}{152677}{11155961}{1948}{15111526596177}{1948}{151115192648596177}归并次数：1，2，…，2i-1，若长度为n，则共需归并log2n总的时间复杂性为：T(n)=O(n·log2n)Voidmpass(n,l,A,B)intn,l;LISTA,&B;{inti,t;i=1;while(i<=(n-2*l+1)){merge(i,i+l-1,i+2*l-1,A,B)i=i+2*l;}if((i+l-1)<n)merge(i,i+l-1,n,A,B);elsefor(t=i;t<=n;t++)B[t]=A[t];}VoidT_W_SORT(n,A)Intn;LIST&A;{intl;LISTB;

l=1;while(l<n){mpass(n,l,A,B);

l=2*l;mpass(n,l,B,A);

l=2*l;}}Voidmerge(l,m,n,A,B)Voidmpass(n,l,A,B)l

mm+1nl

nABi=1;while(i<=(n-2*l+1)){merge(i,i+l-1,i+2*l-1,A,B)i=i+2*l;}if((i+l-1)<n)merge(i,i+l-1,n,A,B);elsefor(t=i;t<=n;t++)B[t]=A[t];？lllllllllllll2l2l2l2l2l2l……AB>l<l{26}{5}{77}{1}{61}{11}{59}{15}{48}{19}{526}{177}{1161}{1559}{1948}{152677}{11155961}{1948}{15111526596177}{1948}{151115192648596177}归并次数：1，2，…，2i-1，若长度为n，则共需归并log2n总的时间复杂性为：T(n)=O(n·log2n)6.5堆分类[定义]把具有如下性质的数组A表示的二元树称为堆（Heap）:(1)若2*i≤n，则A[i].key≤A[2*i].key;(2)若2*i+1≤n，则A[i].key≤A[2*i+1].key;小顶堆或：把具有如下性质的数组A表示的二元树称为堆（Heap）:(1)若2*i≤n，则A[i].key≥A[2*i].key;(2)若2*i+1≤n，则A[i].key≥A[2*i+1].key;大顶堆例：1123394655112339465511233946551123394655132539465132539465123453956234539561133456953345695211354569354569321145956459563321155965596433211569569543321169695543321199655433211Voidpushdown(first,last)Intfirst,last;{intr;r=first;while(r<=last/2)if((r==last/2)&&(last%2==0)){if(A[r].key>A[2*r].key)swap(A[r],A[2*r]);r=last;/*结束循环*/}elseif((A[r].key>A[2*r].key)&&(A[2*r].key<=A[2*r+1].key)){swap(A[r],A[2*r]);/*左孩子比右孩子小，与左孩子交换*/r=2*r;}elseif((A[r].key>A[2*r+1].key)&&(A[2*r+1].key<A[2*r].key)){swap(A[r],A[2*r+1]);/*右孩子比左孩子小，与右孩子交换*/r=2*r+1;}elser=last;}整理堆：O(last/first)last/2?2258491736225849173i=n/2……16225849173622534967816225349678堆分类Voidsort(n,A)intn;LISTA;{inti;for(i=n/2;i>=1;i--)pushdown(i,n);for(i=n;i>=2;i--){swap(A[1],A[i]);pushdown(1,i-1);}}T(n)=O(n·log2n)整理堆建堆堆排序？first？last?6.6基数分类——多关键字分类321986123432543018765678987789098890109901210012Q[0]:901109Q[1]:210012018Q[2]:321123Q[3]:432Q[4]:543Q[5]:Q[6]:765Q[7]:678Q[8]:986987789Q[9]:890098901109210012018321123432543765678986987789890098Q[0]:012018098Q[1]:109123Q[2]:210Q[3]:321Q[4]:432Q[5]:543Q[6]:678Q[7]:765789Q[8]:890Q[9]:901986987012018098109123310321432543678765789890901986987Q[0]:890210Q[1]:321901Q[2]:432012Q[3]:123543Q[4]:Q[5]:765Q[6]:986Q[7]:987Q[8]:018678098Q[9]:789109890210321901432012123543765986987018678098789109

Voidradixsort(figure,A)intfigure;QUEUE&A;{QUEUEQ[10];recordsdata;intpass,r,i;for(pass=1;pass<=figure;pass+){for(i=0;i<=9;i++)MAKENULL(Q[i]);while(!EMPTY(A)){data=FRONT(A);DEQUEUE(A);r=RADIX(data.key,pass);ENQUEUE(data,Q[r]);}for(i=0;i<=9;i++)while(!EMPTY(Q[i])){data=FRONT(Q[i]);DEQUEUE(Q[i]);ENQUEUE(data,A);}}}IntRADIX(k,p)Intk,p;{intpower,i;power=1;for(i=1;i<=p-1;i++)power=power*10;return((k%(power*10))/power);}6.7*词典排序[定义]设集合S

中的元素为整数元组，关系≤为S

的线性序，对两个元素(s1,s2,…,sp)

和(t1,t2,…,tq)

存在(s1,s2,…,sp)≤(t1,t2,…,tq)

，当存在一个整数j，1≤j≤max[p,q]，使得sj≤tj，且所有1≤i＜j，si＝ti；或者p≤q，并且si＝ti，1≤i≤p，则关系≤称为词典序。输入:一个序列A1,A2,…,An，其中Ai为k元组(ai1,ai2,…,aik),aij为0～m-1的整数输出:一个序列A1,A2,…,An，B1,B2,…,Bn，使得Bi≤Bi+1,1≤i＜n。{将A1,A2,…,An

进入队列QUEUE;for(j=k;j>=1;j--){for(i=0;i<=m-1;i++)初始化桶Q[i];while(QUEUE不空){设Ai

为QUEUE的队首元素，删除Ai，并放到桶Q[aij]中；}for(i=0;i<=m-1;i++)将桶Q[i]连接到队列QUEUE后;}}词典排序算法6.8*求第k个最小元素——顺序统计问题在一个含有n

个元素的序列中，要求出第

k

个最小元素,也称顺序统计。可以先进行排序，然后求出第k

个最小元素。T(n)=O(nlogn)。下面的算法使得T(n)=O(n)。（证明P233略）基本思想：

根据某一元素m

将原序列S

化分成3个子序列S1，S2和S3，使得S1的所有元素都小于m

，S2的所有元素等于m，而S3的所有元素都大于m，通过统计S1和S2的元素个数，可以确定所求的第k个最小元素是在S1和S2或S3中。通过上述方式，将一个给定的问题转换成一个更小的问题。为保证O(n)，必须保证在线性时间里找到划分元素m，使得S1和S2的大小不超过S的一个固定部分。问题的关键是如何选择划分元素m。下面算法中，S被划分成若干子序列，每个子序列由5个元素组成。对每个子序列排序，取其中值组成一个序列M。M只包含n/5个元素，可以比原来快5倍的速度找到n个元素的中值。输入：由n

个元素组成的序列S

和整数k(1≤k≤n)

。输出：S

中第k

个最小元素。ElementtypeSelect(intk,LISTS){if(|S|<50){Sort(S);returnS中第k个最小元素；

}else{将S分为|S|/5个元素序列，每个序列由5个元素组成，剩余元素最多4个；设M为由每个5元素序列的中值组成的序列；

m=Select

(┌|M|/2┐,M);

设S1，S2，和S3分别为S中小于、等于和大于m的元素序列；

if(|S|>=k)returnSelect(k,S1);elseif(|S1|+|S2|>=k)returnm;elsereturnSelect(k-|S1|-|S2|,S3);}}小结——各种排序的比较排序方法平均时间最好情况最坏情况辅助空间稳定性简单排序O(n2)O（n）O(n2)O(1)稳定希尔排序O（n1.3）------O(1)不稳定快速排序O(n·log2n)O(n·log2n)O(n2)O(log2n)不稳定堆排序O(n·log2n)O(n·log2n)O(n·log2n)O(1)不稳定归并排序O(n·log2n)O(n·log2n)O(n·log2n)O(n)稳定基数排序O(d·(n+r·d))O(d·(n+r·d))O(d·(n+r·d))O(n+r·d)稳定不同条件下，排序方法的选择：

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。

当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；且以直接插入排序最佳。

(3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏况。这两种排序都是不稳定的。基数排序适用于n值很大而关键字较小的序列。若要求排序稳定，则可选用归并排序，基数排序稳定性最佳。课堂练习题：在上面的排序方法中:(1)直接插入排序、冒泡排序、归并排序和基数排序是稳定的。(2)其他排序算法均是不稳定的。(3)以带*号的表示区别：希尔排序：[8,1,10,5,6,8*]

快速排序：[2,2*,1]

直接选择排序：[2,2*,1]

堆排序：[2,2*,1]1、以关键字序列(265,301,751,129,937,863,742,694,076,438)为例，分别写出执行以下排序算法的各趟排序结束时，关键字序列的状态。

(1)直接插入排序(2)希尔排序(3)冒泡排序(4)快速排序

(5)直接选择排序(6)归并排序(7)堆排序(8)基数排序上述方法中：(1)哪些是稳定的排序?(2)哪些是非稳定的排序?(3)对不稳定的排序试举出一个不稳定的实例。初始态：265[301751129937863742694076438]第一趟：265301[751129937863742694076438]第二趟：265301751[129

937863742694076438]第三趟：129265301751[937863742694076438]第四趟：129265301751937[863

742694076438]第五趟：129265301751863937[742

694076438]第六趟：129265301742751863937[694076438]第七趟：129265301694742751863937[076438]第八趟：076129265301694742751863937[438]第九趟：076129265301438694742751863937

(1)直接插入排序(方括号表示无序区)(2)希尔排序(增量为5，3，1)

初始态：265

301

751129

937

863

742

694076

438

第一趟：265301694076438863742751129937

第二趟：076301129265438694742751863937

第三趟：076129265301438694742751863937

(3)冒泡排序(方括号为无序区)初始态：[265301751129937863742694076438]第一趟：076[265301751129937863742694438]第二趟：076129[265301751438937863742694]第三趟：076129265[301438694751937863742]第四趟：076129265301[438694742751937863]第五趟：076129265301438[694742751863937]第六趟：076129265301438694742751863937(4)快速排序(方括号表示无序区，层表示对应的递归树的层数)初始态：[265301751129937863742694076438]第二层：[076129]265[751937863742694301438]第三层：076[129]265[438301694742]751[863937]第四层：076129265[301]438[694742]751863[937]第五层：076129265301438694[742]751863937第六层：076129265301438694742751863937(5)直接选择排序(方括号为无序区)

初始态265301751129937863742694076438]第一趟：076[301751129937863742694265438]第二趟：076129[751301937863742694265438]第三趟：076129265[301937863742694751438]第四趟：076129265301[937863742694751438]第五趟：076129265301438[863742694751937]第六趟：076129265301438694[742751863937]第七趟：076129265301438694742[751863937]第八趟：076129265301438694742751[937863]第九趟：076129265301438694742751863937(6)归并排序(为了表示方便，采用自底向上的归并，方括号为有序区)初始态：[265][301][751][129][937][863][742][694][076][438]第一趟：[265301][129751][863937][694742][076438]第二趟：[129265301751][694742863937][076438]第三趟：[129265301694742751863937][076438]第四趟：[076129265301438694742751863937](6)堆排序（通过画二叉树可以一步步得出排序结果）初始态：[265301751129937863742694076438]建立初始堆：[937694863265438751742129075301]第一次排序重建堆：[863694751765438301742129075]937第二次排序重建堆：[751694742265438301075129]863937第三次排序重建堆：[742694301265438129075]751863937第四次排序重建堆：[694438301265075129]742751863937第五次排序重建堆：[438265301129075]694742751863937第六次排序重建堆：[301265075129]438694742751863937第七次排序重建堆：[265129075]301438694742751863937第八次排序重建堆：[129075]265301438694742751863937第九次排序重建堆：075129265301438694742751863937(8)基数排序(方括号内表示一个箱子共有10个箱子，箱号从0到9)初始态：265301751129937863742694076438第一趟：[][301751][742][863][694][265][076][937][438][129]第二趟：[301][][129][937438][742][751][863265][076][][694]第三趟：[075][129][265][301][438][][694][742751][863][937]

若关键字是非负整数，则基数排序最快；若要求辅助空间为O(1)，则应选堆排序；若要求排序是稳定的，且关键字是实数，则应选归并排序，因为基数排序不适用于实数，虽然它也是稳定的。

此时Partion返回值是low.此时快速排序的运行时间是：

(high-low)(high-low-1)/2=O((high-low)^2)，可以修改Partion，将其中RecTypepivot=R[i];句改为：

RecTypepivot=R[(j+i)/2]；也就是取中间的关键字为基准，这样就能使划分的结果是平衡的。3、若关键字是非负整数，快速排序、归并、堆和基数排序哪一个最快?

若要求辅助空间为O(1)，则应选择谁?

若要求排序是稳定的，且关键字是实数，则应选择谁?2、当R[low..high]中的关键字均相同时，Partion返回值是什么?

此时快速排序的的运行时间是多少?能否修改Partion,使得划分结果是平衡的(即划分后左右区间的长度大致相等)?

堆的性质是：任一非叶结点上的关键字均不大于(或不小于)其孩子结点上的关键字。据此我们可以通过画二叉树来进行判断和调整：

(1)此序列不是堆，经调整后成为大顶堆：

(100,80,73,66,39,42,57,35,21)

(2)此序列不是堆，经调整后成为小顶堆：

(12,24,33,65,33,56,48,92,86,70)

(3)此序列是一大顶堆。

(4)此序列不是堆，经调整后成为小顶堆：

(05,23,20,56,28,38,29,61,35,76,100)4、判别下列序列是否为堆(小顶堆或大顶堆)，若不是，则将其调整为堆：

(1)(100,86,73,35,39,42,57,66,21)

(2)(12,70,33,65,24,56,48,92,86,33)

(3)(103,97,56,38,66,23,42,12,30,52,06,20)

(4)(05,56,20,23,40,38,29,61,35,76,28,100)5、有序数组是堆吗?这四种排序算法中，直接选择、快速排序均是不稳定的，因此先予以排除，剩下两种算法中，由于直接插入算法所费时间比冒泡法更少，因此选择直接插入排序算法为宜。有序数组是堆。因为有序数组中的关键字序列满足堆的性质。

若数组为降序，则此堆为大顶堆，反之为小顶堆。6、若文件初态是反序的，且要求稳定排序，则在直接插入、直接选择、冒泡排序和快速排序中选哪则种方法为宜?应选直接选择排序为更好。分析如下：

(1)在直接插入排序算法中，反序输入时是最坏情况，此时：关键字的比较次数：Cmax=(n+2)(n-2)/2

记录移动次数为：Mmax=(n-1)(n+4)/2

Tmax=n2-4n-3(以上二者相加)

(2)在冒泡排序算法中，反序也是最坏情况，此时：

Cmax=n(n-1)/2

Mmax=3n(n-1)/2

Tmax=2n2-2n

(3)在选择排序算法中，

Cmax=n(n-1)/2Mmax=3(n-1)

Tmax=n2/2-5n/2-3

虽然它们的时间复杂度都是O(n2),但是选择排序的常数因子为1/2，因此选择排序最省时间。7、若文件初态是反序的，则直接插入，直接选择和冒泡排序哪一个更好?

重写的算法如下：

voidInsertSort(SeqListR)

{//对顺序表中记录R[0..n-1]按递增序进行插入排序

inti,j;

for(i=n-2;i>=0;i--)//在有序区中依次插入R[n-2]..R[0]

if(R[i].key>R[i+1].key)//若不是这样则R[i]原位不动

{

R[n]=R[i];j=i+1;//R[n]是哨兵

do{//从左向右在有序区中查找插入位置

R[j-1]=R[j];//将关键字小于R[i].key的记录向右移

j++;

}while(R[j].key<R[n].key]);

R[j-1]=R[n];//将R[i]插入到正确位置上

}//endif}8、将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。intQuickSort(SeqListR,intj,intlow,inthigh){//对R[low..high]快速排序

intpivotpos；//划分后的基准记录的位置

if(low<high){//仅当区间长度大于1时才须排序

pivotpos=Partition(R，low，high)；//对R[low..high]做划分

if(pivotpos==j)returnr[j];

elseif(pivotpos>j)return(R,j,low,pivotpos-1);

elsereturnquicksort(R,j,pivotpos+1,high);

}//Endif}//QuickSort9、对给定的j(1≤j≤n),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。

10、设向量A[0..n-1]中存有n个互不相同的整数，且每个元素的值均在

0到n-1之间。试写一时间为O(n)的算法将向量A排序，结果可输出到另一个向量B[0..n-1]中。Sort(int*A,int*B)

{//将向量A排序后送入B向量中

inti;

for(i=0;i<=n-1;i++)

B[A[i]]=A[i];

}Sort(int*A)

{inti;

for(i=0;i<=n-1;i++)

A[i]=i;

}写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提示：应为堆R增