數據結構考研分類復習真題 第十章 答案[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; }

　　對比兩種算法可以看出正確選擇變量(指針)的重要性

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

From:http://tw.wingwit.com/Article/program/sjjg/201311/23170.html