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

　　 [題目分析]保存劃分的第一個元素以平均值作為樞軸進行普通的快速排序最後樞軸的位置存入已保存的第一個元素若此關鍵字小於平均值則它屬於左半部否則屬於右半部

　　int partition (RecType r[]int lh)
　　{ int i=lj=havg=;
　　for(;i<=h;i++) avg+=R[i]key;
　　i=l; avg=avg/(hl+);
　　while (i<j)
　　{ while (i<j &&R[j]key>=avg) j;
　　if (i<j) R[i]=R[j];
　　while (i<j &&R[i]key<=avg) i++;
　　if (i<j) R[j]=R[i];
　　}
　　if(R[i]key<=avg) return  i; else return  i;
　　}
　　void quicksort (RecType R[]int ST);
　　{if (S<T)
　　{k=partition (RST);
　　quicksart (RSk);
　　quicksart (Rk+T);}
　　}

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

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