数据结构考研分类复习真题 第十章 答案[47]

[题目分析]利用快速排序思想解决由于要求对每粒砾石的颜色只能看一次设个指针ij和k分别指向红色白色砾石的后一位置和待处理的当前元素从k=n开始从右向左搜索若该元素是兰色则元素不动指针左移(即k)若当前元素是红色砾石分i>=j(这时尚没有白色砾石)和i<j两种情况前一情况执行第i个元素和第k个元素交换之后i+后一情况i所指的元素已处理过(白色)j所指的元素尚未处理应先将i和j所指元素交换再将i和k所指元素交换对当前元素是白色砾石的情况也可类似处理

为方便处理将三种砾石的颜色用整数和表示

void QkSort(rectype r[]int n)

// r为含有n个元素的线性表元素是具有红白和兰色的砾石用顺序存储结构存储

//本算法对其排序使所有红色砾石在前白色居中兰色在最后

{int i=j=k=ntemp;

while (k!=j)

{while (r[k]key==) k;// 当前元素是兰色砾石指针左移

if (r[k]key==) // 当前元素是红色砾石

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==)

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+;}

//ij分别指向红白色砾石的后一位置

}//while

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

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

//最后红白兰色砾石的个数分别为: i;ji;nj+

}//结束QkSor算法

[算法讨论]若将j(上面指向白色)看作工作指针将r[j]作为红色r[jk]为白色r[kn]为兰色从j=开始查看若r[j]为白色则j=j+若r[j]为红色则交换r[j]与r[i]且j=j+i=i+若r[j]为兰色则交换r[j]与r[k];k=k算法进行到j>k为止

算法片段如下

int i=j=k=n;

while(j<=k)

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

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

else if (r[j]==) j++; //当前元素是白色

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

{temp=r[j]; r[j]=r[k]; r[k]=temp; k; }

对比两种算法可以看出正确选择变量(指针)的重要性

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []