|
划分算法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 |
