第10章 排序答案

//沿从叶子结点R[s]到根结点T[0]的路径调整败者树 t=(s+k)/2; //T[t]是R[s]的双亲结点 while(t>0)

{ if(R[s].key>R[T[t]].key) s<-->T[t]; //s指示新的胜者 t=t/2; }//while T[0]=s; }//Adjust

void CreateLoserTree(int T[]) { //建立败者树，已知R[0]到R[k-1]为完全二叉树T的叶子结点，存有k个关键字，

沿

//从叶子到根的k条路径将T调整为败者树

R[k].key=MINKEY; //MINKEY是最小关键字 for(i=0;i=0;i--) Adjust(T,i); }//CreateLoserTree

21、[题目分析]利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”，设3个指针i，j和k，分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始，从右向左搜索，若该元素是兰色，则元素不动，指针左移（即k-1）；若当前元素是红色砾石，分i>=j（这时尚没有白色砾石）和i

为方便处理，将三种砾石的颜色用整数1、2和3表示。 void QkSort(rectype r[],int n)

// r为含有n个元素的线性表，元素是具有红、白和兰色的砾石，用顺序存储结构存储， //本算法对其排序，使所有红色砾石在前，白色居中，兰色在最后。 {int i=1,j=1,k=n,temp; while (k!=j)

{while (r[k].key==3) k--;// 当前元素是兰色砾石，指针左移 if (r[k].key==1) // 当前元素是红色砾石 if (i>=j){temp=r[k];r[k]=r[i];r[i]=temp; i++;}

//左侧只有红色砾石，交换r[k]和r[i]

else {temp=r[j];r[j]=r[i];r[i]=temp; j++;

//左侧已有红色和白色砾石，先交换白色砾石到位 temp=r[k];r[k]=r[i];r[i]=temp; i++;

//白色砾石（i所指）和待定砾石（j所指） } //再交换r[k]和r[i]，使红色砾石入位。

if (r[k].key==2)

if (i<=j) { temp=r[k];r[k]=r[j];r[j]=temp; j++;}

// 左侧已有白色砾石，交换r[k]和r[j]

else { temp=r[k];r[k]=r[i];r[i]=temp; j=i+1;}

//i、j分别指向红、白色砾石的后一位置

}//while

if (r[k]==2) j++; /* 处理最后一粒砾石

else if (r[k]==1) { temp=r[j];r[j]=r[i];r[i]=temp; i++; j++; } //最后红、白、兰色砾石的个数分别为: i-1;j-i;n-j+1 }//结束QkSor算法

[算法讨论]若将j（上面指向白色）看作工作指针，将r[1..j-1]作为红色，r[j..k-1]为白色，r[k..n]为兰色。从j=1开始查看，若r[j]为白色，则j=j+1；若r[j]为红色，则交换r[j]与r[i]，且j=j+1，i=i+1；若r[j]为兰色，则交换r[j]与r[k];k=k-1。算法进行到j>k为止。

算法片段如下： int i=1,j=1,k=n; while(j<=k)

if (r[j]==1) //当前元素是红色

{temp=r[i]; r[i]=r[j]; r[j]=temp; i++;j++; } else if (r[j]==2) j++; //当前元素是白色

else //(r[j]==3 当前元素是兰色

{temp=r[j]; r[j]=r[k]; r[k]=temp; k--; } 对比两种算法，可以看出，正确选择变量（指针）的重要性。

22、[题目分析]根据定义，DEAP是一棵完全二叉树，树根不包含元素，其左子树是一小堆（MINHEAP，下称小堆），其右子树是一大堆（MAXHEAP，下称大堆），故左右子树可分别用一维数组l[]和r[]存储，用m和n分别表示当前两完全二叉树的结点数，左右子树的高度差至多为1，且左子树的高度始终大于等于右子树的高度。

h

我们再分析插入情况：当均为空二叉树或满二叉树（m=2-1）时，应在小堆插入；小堆

h

满（二叉树）后在大堆插入。即当m>=n且m<>2-1且?log2m?-?log2n?<=1在小堆插入，否则在大堆插入。

最后分析调堆情况：在小堆m处插入结点x后，若x的值不大于大堆的m/2结点的值，则在小堆调堆；否则，结点x与大堆的m/2结点交换，然后进行大堆调堆。在大堆n处插入结点x后，若x不小于小堆的n结点，则在大堆调堆；否则，结点x与小堆的n结点交换，然后进行小堆调堆。

（1） 在DEAP中插入结点4后的结果如图： 4先插入到大堆，因为4小于小堆中

45 4 对应位置的19，所以和19交换。交换后只需

5 8 调整小堆，从叶子到根结点。这时，大堆不需 25 40 调整，因为插入小堆19时，要求19必须小于 15 20 19 10 9 30 对应大堆双亲位置的25，否则，要进行交换。 void InsertDEAP(int l[],r[],m,n,x)

//在DEAP中插入元素x,l[]是小堆，r[]是大堆，m和n分别是两堆的元素个数，x是待插入元素。

h

{if (m>=n && m<>2-1 && ?log2m?-?log2n?<=1)// 在小堆插入x,h是二叉树的高度 {m++; //m增1

if (x>r[m/2]) //若x大于大堆中相应结点的双亲，则进行交换 {l[m]=r[m/2]; c=m/2; f=c/2;

while (f>0 && r[f]

{r[c]=r[f]; c=f; f=c/2;} r[c]=x;

} //结束调大堆

else //调小堆

{c=m; f=c/2;

while (f>0 && l[f]>x)

{l[c]=l[f]; c=f; f=c/2;} l[c]=x; }

else //在大堆插入x

{n++; //n增1

if (x

while (f>0 && l[f]>x) //调小堆 {l[c]=l[f]; c=f; f=c/2;} l[c]=x;

} //结束调小堆

else //调大堆

{c=n; f=c/2;

while (f>0 && r[f]

{r[c]=r[f]; c=f; f=c/2;} r[c]=x; }

}//结束InsertDEAP算法