數據結構考研分類復習真題 第十章 答案[41]

　　 void  QuickSort(rectype  r[n+]; int n)
　　// 對r[n]進行快速排序的非遞歸算法
　　{typedef struct
　　{ int lowhigh; }node
　　node s[n+]//棧容量足夠大
　　int quickpass(rectype r[]intint);  // 函數聲明
　　int top=; s[top]low=; s[top]high=n;
　　while (top>)
　　{ss=s[top]low; tt=s[top]high;  top;
　　if (ss<tt)
　　{k=quickpass(rsstt);
　　if (kss>) {s[++top]low=ss; s[top]high=k;}
　　if (ttk>) {s[++top]low=k+; s[top]high=tt;}
　　}
　　} // 算法結束
　　int quickpass(rectype r[];int st)
　　{i=s; j=t; rp=r[i]; x=r[i]key;
　　while (i<j)
　　{while (i<j && x<=r[j]key) j;
　　if (i<j) r[i++]=r[j];
　　while (i<j && x>=r[j]key) i++;
　　if (i<j) r[j]=r[i];;
　　]
　　r[i]=rp;
　　return  (i);
　　} // 一次劃分算法結束

　　[算法討論]可對以上算法進行兩點改進一是在一次劃分後先處理較短部分較長的子序列進棧二是用三者取中法改善快速排序在最壞情況下的性能下面是部分語句片段

　　int top=; s[top]low=; s[top]high=n;
　　ss=s[top]low; tt=s[top]high;  top; flag=true;
　　while (flag || top>)
　　{k=quickpass(rsstt);
　　if (kss>ttk)   // 一趟排序後分割成左右兩部分
　　{if (kss>) // 左部子序列長度大於右部左部進棧
　　{s[++top]low=ss; s[top]high=k; }
　　if (ttk>) ss=k+;  // 右部短的直接處理
　　else flag=false;  // 右部處理完需退棧
　　}
　　else if (ttk>) //右部子序列長度大於左部右部進棧
　　{s[++top]low=k+; s[top]high=tt; }
　　if (kss>) tt=k // 左部短的直接處理
　　else flag=false // 左部處理完需退棧
　　}
　　if (!flag && top>)
　　{ss=s[top]low; tt=s[top]high; top; flag=true;}
　　} // end of while (flag || top>)
　　} // 算法結束
　　int quickpass(rectype r[];int st)
　　// 用三者取中法進行快速排序的一次劃分
　　{ int  i=s j=t mid=(s+t)/;
　　rectype tmp;
　　if (r[i]key>r[mid]key) {tmp=r[i];r[i]=r[mid];r[mid]=tmp }
　　if (r[mid]key>r[j]key)
　　{tmp=r[j];r[j]=r[mid];
　　if (tmp>r[i]) r[mid]=tmp; else {r[mid]=r[i];r[i]=tmp }
　　}
　　{tmp=r[i];r[i]=r[mid];r[mid]=tmp }
　　// 三者取中最佳次比較次賦值最差次比較次賦值
　　rp=r[i]; x=r[i]key;
　　while (i<j)
　　{while (i<j && x<=r[j]key) j;
　　if (i<j) r[i++]=r[j];
　　while (i<j && x>=r[j]key) i++;
　　if (i<j) r[j]=r[i];;
　　]
　　r[i]=rp;
　　return  (i);
　　} // 一次劃分算法結束

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

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