【正确答案】正确答案：算法的基本设计思想：利用快速排序思想解决。由于要求“对每粒砾石的颜色只能看一次”，设3个指针i、j和k，分别指向红色、白色砾石的后一位置和待处理的当前元素。从k=n开始，从右向左搜索，若当前元素是蓝色砾石，则元素不动，指针左移(即k—1)；若当前元素是红色砾石，分i≥j(这时尚没有白色砾石)和i=j) { ／／左侧只有红色砾石，交换r[k]和r[i] temp=r[k]； r[k]=r[i]; r[i]=temp; i++； } else { ／／左侧已有红色和白色砾石，先交换白色砾石到位 temp=r[j]； r[j]=r[i]; r[i]=temp; j++; temp=r[k]; ／／再交换r[k]和r[i]，使红色砾石入位 r[k]=r[i]; r[i]=temp； i++； } } if(r[k]．key==2) { if(i<=j) { temp=r[k]； ／／左侧已有白色砾石，交换r[k]和r[j] r[k]=r[j]; r[j]=temp； j++； } else { temp=r[k]; r[k]=r[i]; r[i]=temp; j=i+1； ／／i、j分别指向红、白色砾石的后一位置 } } }／／while if(r[k]．key==2) j++； ／／处理最后一粒砾石 else if(r[k]．key==1) { temp=r[j]； r[j]=r[i]; r[i]=temp； i++： J++； } ／／最后红、白、蓝色砾石的个数分别为i一1、J—i、n—j+1 }／／QkSort 若将j(上面指向白色)看作工作指针，将r[1一j一1]作为红色，r[j,k一1]作为白色，r[k_．n]作为蓝色。从j=l开始查看，若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 if(r[j]==3) { ／／当前元素是蓝色 temp=r[j]； r[j]=r[k]； r[k]=temp; k一一； } } 对比两种算法，可以看出，正确选择变量(指针)的重要性。
【答案解析】