您现在的位置：学赛首页 > 自考学院 > 数据结构与算法 > 正文
第8章排序(算法设计)习题练习答案
http://www.educity.cn　作者：不详　来源：　2006年9月4日　发表评论　进入社区

13. 将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。
解：
    重写的算法如下：
  void InsertSort(SeqList R)
　　{//对顺序表中记录R[0..n-1]按递增序进行插入排序
　　　int i,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
　　}//InsertSort.

14.以单链表作为存储结构实现直接插入排序算法。 
解：
　#define int KeyType //定义KeyType 为int型
　typedef struct node{
　　　KeyType key; //关键字域
　　　OtherInfoType info; //其它信息域，
　　　struct node * next; //链表中指针域
　　}RecNode; //记录结点类型
　typedef RecNode * LinkList ; //单链表用LinkList表示

　void InsertSort(LinkList head)
　　{//链式存储结构的直接插入排序算法,head是带头结点的单链表
　　　RecNode *p,*q,*s; 
　　　if ((head->next)&&(head->next->next))//当表中含有结点数大于1
　　　　{
　　　　　p=head->next->next;//p指向第二个节点
　　　　　head->next=NULL;
　　　　　q=head;//指向插入位置的前驱节点
　　　　　while(p)&&(q->next)&&(p->key<q->next->key)
　　　　　　q=q->next;
　　　　　if (p)
　　　　　　{s=p;p=p->next;// 将要插入结点摘下
　　　　　　　s->next=q->next;//插入合适位置：q结点后
　　　　　　　q->next=s;
　　　　　　}
　　　　}
　　}

15.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关键字之前。请分析算法的时间复杂度。 
解：
　　因为只需将负数关键字排在前面而无需进行精确排列顺序，因此本算法采用两端扫描的方法，就象快速排序采用的方法一样，左边扫描到正数时停止，开始扫描右边，遇到负数时与左边的当前记录交换，如此交替进行，一趟下来就可以完成排序。

　void ReSort(SeqList R)
　　{//重排数组，使负值关键字在前
　　　int i=1,j=n; //数组存放在R[1..n]中
　　　while (i<j) //i<j表示尚未扫描完毕
　　　　{ while(i<j&&R[i].key<0) //遇到负数则继续扫描
　　　　　　i++;
　　　　　R[0]=R[i]; //R[0]为辅助空间
　　　　　while(i<j&&R[j].key>=0)// 遇到正数则继续向左扫描
　　　　　　　　j--;
　　　　　R[i++]=R[j];R[j--]=R[0];//交换当前两个元素并移动指针
　　　　}//endwhile
　　}//ReSort

　　本算法在任何情况下的比较次数均为n(每个元素和0)相比，交换次数少于n/2，总的来说，时间复杂度为O(n).

*16.写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。 
解：
　　算法如下：
　void BubbleSort(SeqList R)
　　{//R[1..n]是待排序文件，双向扫描冒泡排序
　　　int i,j,k;
　　　Boolean exchange; //交换标记
　　　i=n;j=1;
　　　exchange=TRUE;
　　　while (i>j)&&(exchange)
　　　　{k=i-1;exchange=FALSE;
　　　　　while (k>=j)//由下往上扫描
　　　　　　{if (r[k]>r[k+1])
　　　　　　　　{r[0]=r[k];r[k]=r[k+1];r[k+1]=r[k];exchange=TRUE;//交换
　　　　　　　　}//endif
　　　　　　　k--;
　　　　　　}//endwhile
　　　　　if (exchange)
　　　　　　{exchange=FALSE;
　　　　　　　j++;k=j+1;
　　　　　　　while(k<=i)//由上往下扫描
　　　　　　　　{if (r[k]<r[k-1])
　　　　　　　　　{r[0]=r[k];r[k]=r[k-1];r[k-1]=r[k];exchange=TRUE;//交换
　　　　　　　　　}//endif
　　　　　　　　　k++;
　　　　　　　　}endwhile
　　　　　　　i--;
　　　　　　}//endif
　　　　}endwhile
　　}//endsort

17.下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫描中进行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。
void BubbleSort(int A[],int n)
　//不妨设A[0..n-1]是整型向量
　int lastExchange,j,i=n-1;
　while (i>0)
　　lastExchange=0;
　　for(j=0;j<i;j++)//从上往下扫描A[0..i]
　　　　if(A[j+1]<A[j]){
　　　　　　交换A[j]和A[j+1];
　　　　　　lastExchange=j;
　　　　}
　　i=lastExchange;//将i置为最后交换的位置
　}//endwhile
}//BubbleSort 

解：算法如下：
void BubbleSort(int A[],int n)
　//不妨设A[0..n-1]是整型向量
　int lastExchange,j,i=0;
　while (i<n) //这一条很重要，如不改为这样，算法将无限循环下去
　　lastExchange=n;
　　for(j=n-1;j>i;j--)//从下往上扫描A[0..i]
　　　　if(A[j-1]<A[j]){
　　　　　　交换A[j]和A[j-1];
　　　　　　lastExchange=j;
　　　　}
　　i=lastExchange;//将i置为最后交换的位置
　}//endwhile
}//BubbleSort

18.改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。 
解：
　　改写后的算法如下：
　void QuickSort(SeqList R,int low ,int high)
　　{//对R[low..high]快速排序
　　　int pivotpos;
　　　if(high-low<=2)//若当前区内元素少于3个
　　　　{//则进行直接插入排序
　　　　　InsertSort(R,low,high);
　　　　}
　　　else
　　　　{
　　　　　pivotpos=midPartion(R,low,high);
　　　　　QuickSort(R,low,pivotpos-1);
　　　　　QuickSort(R,pivotpos+1，high);
　　　　}
　　}//QuickSort

　int midPartion(SeqList R,int i, int j)
　　{//三者取中规则定基准
　　　if(R[(i+j)/2].key>R[i].key)
　　　　{ 交换R[(i+j)/2]和R[i];}
　　　if(R[i].key>R[j].key)
　　　　{ 交换R[i]和R[j];}
　　　if(R[i].key)<R[(i+j)/2].key)
　　　　{ 交换R[i]和R[(i+j)/2];}
　　　//以上三个if语句就使区间的第一个记录的key值为三个key的中间值
　　　return Partion(R,i,j);//这样我们就可以仍使用原来的划分算法了
　　}

19.对给定的j(1≤j≤n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。 
答：
　int QuickSort(SeqList R,int j,int low,int high)
　　{ //对R[low..high]快速排序
　　　int pivotpos； //划分后的基准记录的位置
　　　if(low<high){//仅当区间长度大于1时才须排序
　　　　　pivotpos=Partition(R，low，high)； //对R[low..high]做划分
　　　　　if (pivotpos==j) return r[j];
　　　　　else if (pivotpos>j) return(R,j,low,pivotpos-1);
　　　　　　　　else return quicksort(R,j,pivotpos+1,high);
　　　　}
　　} //QuickSort

20.以单链表为存储结构，写一个直接选择排序算法。
答：
　#define int KeyType //定义KeyType 为int型
　typedef struct node{
　　　KeyType key; //关键字域
　　　OtherInfoType info; //其它信息域，
　　　struct node * next; //链表中指针域
　　}RecNode; //记录结点类型

　typedef RecNode * LinkList ; //单链表用LinkList表示

　void selectsort(linklist head)
　　{RecNode *p,*q,*s;
　　　if(head->next)&&(head->next->next)
　　　　{p=head->next;//p指向当前已排好序最大元素的前趋
　　　　　while (p->next)
　　　　　　{q=p->next;s=p;
　　　　　　　while(q)
　　　　　　　　{if (q->key<s->key) s=q;
　　　　　　　　　q=q->next;
　　　　　　　　}//endwhile
　　　　　　　交换s结点和p结点的数据；
　　　　　　　p=p->next;
　　　　　　}//endwhile
　　　　}//endif
　　}//endsort

21.写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提示：应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述，使其含有长度域)；将key先插入R中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后从下往上调整，使插入的关键字满足性质。请分析算法的时间。
答：
　#define n 100//假设文件的最长可能长度
　typedef int KeyType; //定义KeyType 为int型
　typedef struct node{
　　　KeyType key; //关键字域
　　　OtherInfoType info; //其它信息域，
　　}Rectype; //记录结点类型

　typedef struct{
　　　Rectype data[n] ; //存放记录的空间
　　　int length;//文件长度
　　}seqlist; 

　void heapInsert(seqlist *R,KeyType key)
　　{//原有堆元素在R->data[1]~R->data[R->length],
　　　//将新的关键字key插入到R->data[R->length+1]位置后，
　　　//以R->data[0]为辅助空间，调整为堆(此处设为大根堆)
　　　int large;//large指向调整结点的左右孩子中关键字较大者
　　　int low,high;//low和high分别指向待调整堆的第一个和最后一个记录
　　　int i;
　　　R->length++；R->data[R->length].key=key;//插入新的记录
　　　for(i=R->length/2;i>0;i--)//建堆
　　　　{
　　　　　low=i;high=R->length;
　　　　　R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点
　　　　　for(large=2*low;large<=high;large*=2){
　　　　　　　//若large>high，则表示R->data[low]是叶子，调整结束；
　　　　　　　//否则令large指向R->data[low]的左孩子
　　　　　　　if(large<high&&R->data[large].key<R->data[large+1].key)
　　　　　　　　　large++;//若R->data[low]的右孩子存在
　　　　　　　　　　　　　//且关键字大于左兄弟，则令large指向它
              if (R->data[0].key<R->data[large].key)
             　   { R->data[low].key= R->data[large].key;
　　　　　　　　　　low=large;//令low指向新的调整结点
　　　　　　　　　}
　　　　　　　else break;//当前调整结点不小于其孩子结点的关键字，结束调整
　　　　　}//endfor
　　　　　R->data[low].key=R->data[0].key;//将被调整结点放入最终的位置上
　　　　}//end of for
　　}end of heapinsert 

　算法分析：
　　设文件长度为n,则该算法需进行n/2趟调整，总的时间复杂度与初建堆类似，最坏时间复杂度为O(nlgn)，辅助空间为O(1).

22.写一个建堆算法：从空堆开始，依次读入元素调用上题中堆插入算法将其插入堆中。
答：
　void BuildHeap(seqlist *R)
　　{
　　　KeyType key;
　　　R->length=0;//建一个空堆
　　　scanf("%d",&key);//设MAXINT为不可能的关键字
　　　while(key!=MAXINT) 
　　　　{
　　　　　heapInsert(R,key);
　　　　　scanf("%d",&key);
　　　　}
　　}

23.写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆性质。
答：
　void HeapDelete(seqlist *R,int i)
　　{//原有堆元素在R->data[1]~R->data[R->length],
　　　//将R->data[i]删除，即将R->data[R->length]放入R->data[i]中后，
　　　//将R->length减1，再进行堆的调整，
　　　//以R->data[0]为辅助空间，调整为堆(此处设为大根堆)
　　　int large;//large指向调整结点的左右孩子中关键字较大者
　　　int low,high;//low和high分别指向待调整堆的第一个和最后一个记录
　　　int j;
　　　if (i>R->length) 
　　　　Error("have no such node");
　　　R->data[i].key=R->data[R->length].key;
　　　R->length--；R->data[R->length].key=key;//插入新的记录
　　　for(j=i/2;j>0;j--)//建堆
　　　　{
　　　　　low=j;high=R->length;
　　　　　R->data[0].key=R->data[low].key;//R->data[low]是当前调整的结点
　　　　　for(large=2*low;large<=high;large*=2){
　　　　　　　//若large>high，则表示R->data[low]是叶子，调整结束；
　　　　　　　//否则令large指向R->data[low]的左孩子
　　　　　　　if(large<high&&R->data[large].key<R->data[large+1].key)
　　　　　　　　　large++;//若R->data[low]的右孩子存在
　　　　　　　　　　　　　//且关键字大于左兄弟，则令large指向它
　　　　　　　if (R->data[0].key<R->data[large].key)
　　　　　　　　　　{ R->data[low].key= R->data[large].key;
　　　　　　　　　　　low=large;//令low指向新的调整结点
　　　　　　　　　　}
　　　　　　　else break;//当前调整结点不小于其孩子结点的关键字，结束调整
　　　　　　}//endfor
　　　　　R->data[low].key=R->data[0].key;//将被调整结点放入最终的位置上
　　　　}//end of for
　　}end of HeapDelete 

24.已知两个单链表中的元素递增有序，试写一算法将这两个有序表归并成一个递增有序的单链表。算法应利用原有的链表结点空间。
答：
  typedef struct node{
　　　KeyType key; //关键字域
　　　OtherInfoType info; //其它信息域，
　　　struct node * next; //链表中指针域
　　}RecNode; //记录结点类型

　typedef RecNode * LinkList ; //单链表用LinkList表示

　void mergesort(LinkList la,LinkList lb,LinkList lc)
　　{RecNode *p,*q,*s,*r;
　　　lc=la;
　　　p=la;//p是la表扫描指针，指向待比较结点的前一位置
　　　q=lb->next;//q是lb表扫描指针，指向比较的结点
　　　while(p->next)&&(q)
　　　　　if (p->next->key<=q->key)
　　　　　　p=p->next;
　　　　　else {s=q;q=q->next;
　　　　　　　　s->next=p->next;p->next=s;//将s结点插入到p结点后
　　　　　　　　p=s;}
　　　if (!p->next) p->next=q;
　　　free(lb);
　　}

25.设向量A[0..n-1]中存有n个互不相同的整数，且每个元素的值均在0到n-1之间。试写一时间为O(n)的算法将向量A排序，结果可输出到另一个向量B[0..n-1]中。
答：
　sort(int *A,int *B)
　　{//将向量A排序后送入B向量中
　　　int i;
　　　for(i=0;i<=n-1;i++)
　　　　B[A[i]]=A[i];
　　}

*26.写一组英文单词按字典序排列的基数排序算法。设单词均由大写字母构成，最长的单词有d个字母。提示：所有长度不足d个字母的单词都在尾处补足空格，排序时设置27个箱子，分别与空格，A，B...Z对应。
答： 
　#define KeySize 10 //设关键字位数d=10
　#define Radix 27 //基数rd为27
　typedef RecType DataType;//将队列中结点数据类型改为RecType类型
　typedef struct node{
　　　char key[KeySize]; //关键字域
　　　OtherInfoType info; //其它信息域，
　　}RecType; //记录结点类型
　typedef RecType seqlist[n+1]; 

　void RadixSort(seqlist R)
　　{
　　　LinkQueue B[Radix];
　　　int i;
　　　for(i=0;i<Radix;i++)//箱子置空
　　　　InitQueue(&B[i]);
　　　for(i=KeySize-1;i>=0;i--){//从低位到高位做d趟箱排序
　　　　　Distribute(R,B,i);//第KeySize-i趟分配
　　　　　Collect(R,B);//第KeySize-i趟收集
　　　　}
　　} 

　void Distribute(seqlist R,LinkQueue B[], int j)
　　{//按关键字的第j个分量进行分配，初始时箱子为空
　　　int i;
　　　j=KeySize-j; // 确定关键字从低位起的位置
　　　for(i=0;i<n;i++) //依次扫描R[i]，将其装箱
　　　　　if (R[i].key[j]-'A'>26)
　　　　　　　EnQueue(&B[0],R[i]);//将第j位关键字位空格的记录入第0个队列
　　　　　else EnQueue(&B[0],R[R[i].key[j]-'A'+1]); 
　　}

　void Collect(seqlist R,LinkQueue B[])
　　{
　　　//依次将各非空箱子中的记录收集起来，本过程结束，各箱子都变空
　　　int i,j;
　　　for (j=0;j<Radix;j++)
　　　　while(!QueueEmpty(&B[j]))
　　　　　R[i++]=DeQueue(&B[j]);//将出队记录依次输出到R[i]中
　　}

【大 中 小】【收藏到我的学赛】 【发表评论】【进入社区】