排序 - 交換排序 - 快速排序 （二）

　　劃分算法Partition

　　() 簡單的劃分方法

　　① 具體做法

　　第一步(初始化)設置兩個指針i和j它們的初值分別為區間的下界和上界即i=lowi=high;選取無序區的第一個記錄

　　R[i](即R[low])作為基准記錄並將它保存在變量pivot中;

　　第二步令j自high起向左掃描直到找到第個關鍵字小於pivotkey的記錄R[j]將R[j])移至i所指的位置上這相當於

　　R[j]和基准R[i](即pivot)進行了交換使關鍵字小於基准關鍵字pivotkey的記錄移到了基准的左邊交換後R[j]中相當於是

　　pivot;然後令i指針自i+位置開始向右掃描直至找到第個關鍵字大於pivotkey的記錄R[i]將R[i]移到i所指的位置上這

　　相當於交換了R[i]和基准R[j]使關鍵字大於基准關鍵字的記錄移到了基准的右邊交換後R[i]中又相當於存放了pivot;接著令指

　　針j自位置j開始向左掃描如此交替改變掃描方向從兩端各自往中間靠攏直至i=j時i便是基准pivot最終的位置將

　　pivot放在此位置上就完成了一次劃分

　　②一次劃分過程

　　一次劃分過程中具體變化情況【 參見動畫演示 】

　　③劃分算法

　　int Partition(SeqList Rint iint j)

　　{//調用Partition(Rlowhigh)時對R[lowhigh]做劃分

　　//並返回基准記錄的位置

　　ReceType pivot=R[i]; //用區間的第個記錄作為基准

　　while(i

　　while(i=pivot.key) //pivot相當於在位置i上

　　j--; //從右向左掃描，查找第1個關鍵字小於pivot.key的記錄R[j]

　　if(i

　　R[i++]=R[j]; //相當於交換R[i]和R[j]，交換後i指針加1

　　while(i

　　i++; //從左向右掃描，查找第1個關鍵字大於pivot.key的記錄R[i]

　　if(ipivot.key

　　R[j--]=R[i]; //相當於交換R[i]和R[j]，交換後j指針減1

　　} //endwhile

　　R[i]=pivot; //基准記錄已被最後定位

　　return i;

　　} //partition

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