排序常用算法设计

第8 章排序(算法设计)习题练习答案

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] 课后答案网 www.khdaw.com

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[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->keynext->key) q=q->next; if (p)

课后答案网 www.khdaw.com

{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

{ while(i

R[0]=R[i]; //R[0]为辅助空间

while(i=0)// 遇到正数则继续向左扫描 j--;

R[i++]=R[j];R[j--]=R[0];//交换当前两个元素并移动指针 }//endwhile }//ReSort

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

*16.写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。 解： 算法如下： void BubbleSort(SeqList R) 课后答案网 www.khdaw.com

{//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[0]=r[k];r[k]=r[k-1];r[k-1]=r[k];exchange=TRUE;//交换 }//endif k++; }endwhile i--; }//endif }endwhile }//endsort

17.下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫

描中进行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照

它写一个自下往上扫描的冒泡排序算法。 课后答案网 www.khdaw.com void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=n-1; while (i>0) lastExchange=0;