算法分析与设计-第05章.pptVIP

快速排序经过一趟分划，原序列被分成三部分：主元和左、右两个子序列：(Kp(0),Kp(1),...Kp(j-1))Kp(j)(Kp(j+1),Kp(j+2),Kp(n-1))通过分划操作，原序列的排序问题被分解成了两个性质相同、相互独立的子问题，分别对两个子序列进行排序。当子序列为空序列或只有一个元素的序列时，无须进行任何处理，它们自然是有序的。分划操作演示i向右扫描，寻找l[i]≥l[left]的元素j向左扫描，寻找l[j]≤l[left]的元素48687236481202leftrightij∞0123456736不大于等于主元,所以继续扫描找到大于主元的元素68,扫描暂停;准备和l[j]交换;left和right是待排序元素序列的下、上界；left和right是待排序元素序列的下、上界；()()此时,ij,扫描结束;把l[left]和l[j]交换,实现了各元素按“左边小右边大”的原则分布在主元两侧。如果ij,则交换l[i]和l[j],继续各自的扫描。其目的是把较主元小的元素放到左边,较主元大的元素放到右边;找到小于主元的元素02,准备和l[i]交换;接下来会分别把主元两侧的两个子序列作为排序对象递归执行快速排序算法(过程略)【程序5-11】分划函数templateclassTintSortableListT::Partition(intleft,intright){//前置条件：left?rightinti=left,j=right+1;do{doi++;while(l[i]l[left]);doj--;while(l[j]l[left]);if(ij)Swap(i,j);}while(ij);Swap(left,j);returnj;}快速排序算法初始序列:48366872124802第1趟:(12360248)48(7268)第2趟:(02)12(3648)48(7268)第3趟:021236(48)48(7268)第4趟:02123648486872【程序5－12】快速排序templateclassTvoidSortableListT::QuickSort(){QuickSort(0,n-1);}templateclassTvoidSortableListT::QuickSort(intleft,intright){if(leftright){intj=Partition(left,right);QuickSort(left,j-1);QuickSort(j+1,right);}}分划操作是快速排序的核心。分划操作中最简单的选择主元的方法：选择序列的第一个元素。程序5-11快速排序算法（分划函数—Partition）intPartition(intleft,intright){ //调用本函数的前置条件：leftright；主元为第一个元素l[left]。 inti=left,j=right+1; do{ doi++;while(l[i]l[left]); //从l[left+1]开始比较 //i右移，直到遇到一个不小于主元的元素停止 doj--;while(l[j]l[left]); //从l[right]开始比较 //j左移，直到遇到一个不大于主元的元素停止 if(ij)Swap(i,j); //交换l[i]和l[j]两个元素 }while(ij); //只要i仍小于j Swap(left,j); //最后将主元l[left]与l[j]交换，结束一趟分划操作 returnj; //返回当前主元的位置}初始序列{72,26,57,88,42,80,72,48,60,∞}{72,26,57,88,42,80,72,48,60,∞}i++;j--;{72,