数据结构(c语言版)题集答案——第十章_内部排序

《数据结构(c语言版)题集答案——第十章_内部排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章内部排序10.23voidInsert_Sort1(SqList&L)//监视哨设在高下标端的插入排序算法{k=L.length;for(i=k-1;i;--i)//从后向前逐个插入排序if(L.r[i].key>L.r[i+1].key){L.r[k+1].key=L.r[i].key;//监视哨for(j=i+1;L.r[j].key>L.r[i].key;++j)L.r[j-1].key=L.r[j].key;//前移L.r[j-1].key=L.r[k+1].key;//插入}}//Insert_Sort110

2、.24voidBiInsert_Sort(SqList&L)//二路插入排序的算法{intd[MAXSIZE];//辅助存储x=L.r.key;d=x;first=1;final=1;for(i=2;i<=L.length;i++){if(L.r[i].key>=x)//插入前部{for(j=final;d[j]>L.r[i].key;j--)d[j+1]=d[j];d[j+1]=L.r[i].key;final++;}else//插入后部{for(j=first;d[j]d[j-1]=d[j];d[(j-2)%MAXSIZ

3、E+1]=L.r[i].key;first=(first-2)%MAXSIZE+1;//这种形式的表达式是为了兼顾first=1的情况}}//forfor(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去L.r[j].key=d[i];}//BiInsert_Sort10.25voidSLInsert_Sort(SLList&L)//静态链表的插入排序算法{L.r[0].key=0;L.r[0].next=1;L.r[1].next=0;//建初始循环链表for(i=2;i<=L.le

4、ngth;i++)//逐个插入{p=0;x=L.r[i].key;while(L.r[L.r[p].next].keyp=L.r[p].next;q=L.r[p].next;L.r[p].next=i;L.r[i].next=q;}//forp=L.r[0].next;for(i=1;i{while(pq=L.r[p].next;if(p!=i){L.r[p]<->L.r[i];L.r[i].next=p;}p=q;}//for}//SLInsert_Sort10.26voidBubble_Sort1(inta[],intn

5、)//对包含n个元素的数组a进行改进的冒泡排序{change=n-1;//change指示上一趟冒泡中最后发生交换的元素while(change){for(c=0,i=0;iif(a[i]>a[i+1]){a[i]<->a[i+1];c=i+1;//c指示这一趟冒泡中发生交换的元素}change=c;}//while}//Bubble_Sort110.27voidBubble_Sort2(inta[],intn)//相邻两趟是反方向起泡的冒泡排序算法{low=0;high=n-1;//冒泡的上下界change=1;while

6、(low{change=0;for(i=low;iif(a[i]>a[i+1]){a[i]<->a[i+1];change=1;}high--;//修改上界for(i=high;i>low;i--)//从下向上起泡if(a[i]{a[i]<->a[i-1];change=1;}low++;//修改下界}//while}//Bubble_Sort210.28voidBubble_Sort3(inta[],intn)//对上一题的算法进行化简,循环体中只包含一次冒泡{intb[3];//b[0]为冒泡的下界,b[2]为上界,b[

7、1]无用d=1;b[0]=0;b[2]=n-1;//d为冒泡方向的标识,1为向上,-1为向下change=1;while(b[0]{change=0;for(i=b[1-d];i!=b[1+d];i+=d)//统一的冒泡算法if((a[i]-a[i+d])*d>0)//注意这个交换条件{a[i]<->a[i+d];change=1;}b[1+d]-=d;//修改边界d*=-1;//换个方向}//while}//Bubble_Sort310.29voidOE_Sort(inta[],intn)//奇偶交换排序的算法{chang

8、e=1;while(change){change=0;for(i=1;iif(a[i]>a[i+1]){a[i]<->a[i+1];change=1;}for(i=0;iif(a[i]>a[i+1]){a[i]<->a[i+1];change=1;}}//while}//OE_Sort分析