第十章 内部排序.txt

严蔚敏《数据结构(c语言版)习题集》 参考答案

第十章 内部排序  


10.23

void Insert_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_Sort1

10.24

void BiInsert_Sort(SqList &L)//二路插入排序的算法
{
　int d[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]<L.r[i].key;j++)
　　　　d[j-1]=d[j];
　　　d[(j-2)%MAXSIZE+1]=L.r[i].key;
　　　first=(first-2)%MAXSIZE+1; //这种形式的表达式是为了兼顾first=1的情况
　　}
　}//for
　for(i=first,j=1;d[i];i=i%MAXSIZE+1,j++)//将序列复制回去
　　L.r[j].key=d[i];
}//BiInsert_Sort

10.25

void SLInsert_Sort(SLList &L)//静态链表的插入排序算法
{
　L.r[0].key=0;L.r[0].next=1;
　L.r[1].next=0; //建初始循环链表
　for(i=2;i<=L.length;i++) //逐个插入
　{
　　p=0;x=L.r[i].key;
　　while(L.r[L.r[p].next].key<x&&L.r[p].next)
　　　p=L.r[p].next;
　　q=L.r[p].next;
　　L.r[p].next=i;
　　L.r[i].next=q;
　}//for
　p=L.r[0].next;
　for(i=1;i<L.length;i++) //重排记录的位置
　{
　　while(p<i) p=L.r[p].next;
　　q=L.r[p].next;
　　if(p!=i)
　　{
　　　L.r[p]<->L.r[i];
　　　L.r[i].next=p;
　　}
　　p=q;
　}//for
}//SLInsert_Sort

10.26

void Bubble_Sort1(int a[ ],int n)//对包含n个元素的数组a进行改进的冒泡排序
{
　change=n-1; //change指示上一趟冒泡中最后发生交换的元素
　while(change)
　{
　　for(c=0,i=0;i<change;i++)
　　　if(a[i]>a[i+1])
　　　{
　　　　a[i]<->a[i+1];
　　　　c=i+1; //c指示这一趟冒泡中发生交换的元素
　　　}
　　change=c;
　}//while
}//Bubble_Sort1

10.27

void Bubble_Sort2(int a[ ],int n)//相邻两趟是反方向起泡的冒泡排序算法
{
　low=0;high=n-1; //冒泡的上下界
　change=1;
　while(low<high&&change)
　{
　　change=0;
　　for(i=low;i<high;i++) //从上向下起泡
　　　if(a[i]>a[i+1])
　　　{
　　　　a[i]<->a[i+1];
　　　　change=1;
　　　}
　　high--; //修改上界
　　for(i=high;i>low;i--) //从下向上起泡
　　　if(a[i]<a[i-1])
　　　{
　　　　a[i]<->a[i-1];
　　　　change=1;
　　　}
　　low++; //修改下界
　}//while
}//Bubble_Sort2

10.28

void Bubble_Sort3(int a[ ],int n)//对上一题的算法进行化简,循环体中只包含一次冒泡
{
　int b[ 3 ]; //b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用
　d=1;b[0]=0;b[ 2 ]=n-1; //d为冒泡方向的标识,1为向上,-1为向下
　change=1;
　while(b[0]<b[ 2 ]&&change)
　{
　　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_Sort3

10.29

void OE_Sort(int a[ ],int n)//奇偶交换排序的算法
{
　change=1;
　while(change)
　{
　　change=0;
　　for(i=1;i<n-1;i+=2) //对所有奇数进行一趟比较
　　　if(a[i]>a[i+1])
　　　{
　　　　a[i]<->a[i+1];
　　　　change=1;
　　　}
　　for(i=0;i<n-1;i+=2) //对所有偶数进行一趟比较
　　　if(a[i]>a[i+1])
　　　{
　　　　a[i]<->a[i+1];
　　　　change=1;
　　　}
　}//while
}//OE_Sort
分析:本算法的结束条件是连续两趟比较无交换发生

10.30

typedef struct {
　　　 　　　　　　  int low;
　　　　　　　　　  int high;
　　　　　　　　  } boundary; //子序列的上下界类型

void QSort_NotRecurve(int SQList &L)//快速排序的非递归算法
{
　low=1;high=L.length;
　InitStack(S); //S的元素为boundary类型
　while(low<high&&!StackEmpty(S)) //注意排序结束的条件
　{
　　if(high-low>2) //如果当前子序列长度大于3且尚未排好序
　　{
　　　pivot=Partition(L,low,high); //进行一趟划分
　　　if(high-pivot>pivot-low)
　　　{
　　　　Push(S,{pivot+1,high}); //把长的子序列边界入栈
　　　　high=pivot-1; //短的子序列留待下次排序
　　　}
　　　else
　　　{
　　　　Push(S,{low,pivot-1});
　　　　low=pivot+1;
　　　}
　　}//if
　　else if(low<high&&high-low<3)//如果当前子序列长度小于3且尚未排好序
　　{
　　　Easy_Sort(L,low,high); //直接进行比较排序
　　　low=high; //当前子序列标志为已排好序
　　}
　　else //如果当前子序列已排好序但栈中还有未排序的子序列
　　{
　　　Pop(S,a); //从栈中取出一个子序列
　　　low=a.low;
　　　high=a.high;
　　}
　}//while
}//QSort_NotRecurve

int Partition(SQList &L,int low,int high)//一趟划分的算法,与书上相同
{
　L.r[0]=L.r[low];
　pivotkey=L.r[low].key;
　while(low<high)
　{
　　while(low<high&&L.r[high].key>=pivotkey)
　　　high--;
　　L.r[low]=L.r[high];
　　while(low<high&&L.r[low].key<=pivotkey)
　　　low++;
　　L.r[high]=L.r[low];
　}//while
　L.r[low]=L.r[0];
　return low;
}//Partition

void Easy_Sort(SQList &L,int low,int high)//对长度小于3的子序列进行比较排序
{
　if(high-low==1) //子序列只含两个元素
　　if(L.r[low].key>L.r[high].key) L.r[low]<->L.r[high];
　else //子序列含有三个元素
　{
　　if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
　　if(L.r[low+1].key>L.r[high].key) L.r[low+1]<->L.r[high];
　　if(L.r[low].key>L.r[low+1].key) L.r[low]<->L.r[low+1];
　}
}//Easy_Sort

10.31

void Divide(int a[ ],int n)//把数组a中所有值为负的记录调到非负的记录之前
{
　low=0;high=n-1;
　while(low<high)
　{
　　while(low<high&&a[high]>=0) high--; //以0作为虚拟的枢轴记录
　　a[low]<->a[high];
　　while(low<high&&a[low]<0) low++;
　　a[low]<->a[high];
　}
}//Divide

10.32

typedef enum {RED,WHITE,BLUE} color; //三种颜色

void Flag_Arrange(color a[ ],int n)//把由三种颜色组成的序列重排为按照红,白,蓝的顺序排列
{
　i=0;j=0;k=n-1;
　while(j<=k)
　　switch(a[j])
　　{
　　　case RED:
　　　　a[i]<->a[j];
　　　　i++;
　　　　j++;
　　　　break;
　　　case WHITE:
　　　　j++;
　　　　break;
　　　case BLUE:
　　　　a[j]<->a[k];
　　　　k--; //这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况
　　}
}//Flag_Arrange
分析:这个算法中设立了三个指针.其中,j表示当前元素;i以前的元素全部为红色;k以后的元素全部为蓝色.这样,就可以根据j的颜色,把其交换到序列的前部或者后部.

10.33

void LinkedList_Select_Sort(LinkedList &L)//单链表上的简单选择排序算法
{
　for(p=L;p->next->next;p=p->next)
　{
　　q=p->next;x=q->data;
　　for(r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点
　　　if(r->next->data<x)
　　　{
　　　　x=r->next->data;
　　　　s=r;
　　　}
　　if(s!=q) //找到了值比q->data更小的最小结点s->next
　　{
　　　p->next=s->next;s->next=q;
　　　t=q->next;q->next=p->next->next;
　　　p->next->next=t;
　　} //交换q和s->next两个结点
　}//for
}//LinkedList_Select_Sort

10.34

void Build_Heap(Heap &H,int n)//从低下标到高下标逐个插入建堆的算法
{
　for(i=2;i<n;i++)
　{ //此时从H.r[1]到H.r[i-1]已经是大顶堆
　　j=i;
　　while(j!=1) //把H.r[i]插入
　　{
　　　k=j/2;
　　　if(H.r[j].key>H.r[k].key)
　　　　H.r[j]<->H.r[k];
　　　j=k;
　　}
　}//for
}//Build_Heap

10.35

void TriHeap_Sort(Heap &H)//利用三叉树形式的堆进行排序的算法
{
　for(i=H.length/3;i>0;i--)
　　Heap_Adjust(H,i,H.length);
　for(i=H.length;i>1;i--)