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，且左子树的高度始终大于等于右子树的高度。
我们再分析插入情况：当均为空二叉树或满二叉树（m=2h-1）时，应在小堆插入；小堆满（二叉树）后在大堆插入。即当m>=n且m<>2h-1且?log2m?-?log2n?<=1在小堆插入，否则在大堆插入。 最后分析调堆情况：在小堆m处插入结点x后，若x的值不大于大堆的m/2结点的值，则在小堆调堆；否则，结点x与大堆的m/2结点交换，然后进行大堆调堆。在大堆n处插入结点x后，若x不小于小堆的n结点，则在大堆调堆；否则，结点x与小堆的n结点交换，然后进行小堆调堆。 （1） （1） 在DEAP中插入结点4后的结果如图：
4先插入到大堆，因为4小于小堆中 对应位置的19，所以和19交换。交换后只需 调整小堆，从叶子到根结点。这时，大堆不需
4 45 5 8 25 40 15 10 9 30 20 19 调整，因为插入小堆19时，要求19必须小于 对应大堆双亲位置的25，否则，要进行交换。
void InsertDEAP(int l[],r[],m,n,x)
//在DEAP中插入元素x,l[]是小堆，r[]是大堆，m和n分别是两堆的元素个数，x是待插入元素。
{if (m>=n && m<>2h-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] 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 c=n; f=c/2; 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算法