算法设计与分析（王佳）03分治策略.pptVIP

5.5.1? 分治法求解 设原表长度为n，假定经过一趟分划，分成两个左右子表，其中左子表是主元及其左边元素的子表，设其长度为p，右子表是主元右边元素的子表。那么，若k=p，则主元就是第k小元素；否则若kp ，第k小元素必定在左子表中，需求解的子问题成为在左子表中求第k小元素；若kp，则第k小元素必定在右子表中，需求解的子问题成为在右子表中求第k-p小元素。 5.5.2? 随机选择主元 随机选主元算法 假定表中元素各不相同，并且随机选择主元，即在下标区间[left,right]中随机选择一个下标r，以该下标处的元素为主元。 【程序5－13】Select函数 template class T ResultCode SortableListT::Select1(T x,int k) { if(n=0||kn||k=0) return OutOfBounds; int left=0, right=n; l[n] = INFTY; do { int j=rand()% (right-left+1)+left; Swap(left,j); j=Partition(left, right); if (k==j+1) {x=l[j];return Success;} else if (kj+1) right=j; else left=j+1; } while (true); } 定理5－8 程序5－13的Select算法的平均时间A(n)=O(n)。 算法的最坏情况时间复杂度O(n2) 。 5.5.3? 线性时间选择算法 改进的选择算法采用二次取中法(median of medians rule)确定主元 一个较好的基准划分步骤 步骤（如图所示）： 将n个输入元素划分成?n/5?个组，每组5个元素，只可能有一个组不是5个元素。用任意一种排序算法，将每组中的元素排好序，并取出每组的中位数，共?n/5?个。 递归调用select来找出这?n/5?个元素的中位数。如果?n/5?是偶数，就找它的2个中位数中较大的一个。以这个元素作为划分基准。 说明： 设所有元素互不相同。在这种情况下，找出的基准x至少比3(n-5)/10个元素大，因为在每一组中有2个元素小于本组的中位数，而n/5个中位数中又有(n-5)/10个小于基准x（如图）。同理，基准x也至少比3(n-5)/10个元素小。而当n≥75时，3(n-5)/10≥n/4所以按此基准划分所得的2个子数组的长度都至少缩短1/4。 图2-7 选择划分基准 其中，n个元素用小圆点表示， 　　　空心圆点为每组元素的中位数； 　　　x为中位数的中位数； 　　　箭头由较大元素指向较小元素。 只要等于基准的元素不太多，利用这个基准来划分的两个数组的大小就不会相差太远。 aix n/5+(n/5-1)/2 3(n-5)/10 aix n/5+(n/5-1)/2 3(n-5)/10 【程序5－14】 线性时间选择算法 ResultCode SortableListT::Select(T x,int k) { if(n=0||kn||k=0) return OutOfBounds; int j=Select(k,0,n-1,5); x=l[j];return Success; } template class T int SortableListT::Select(int k, int left,int right,int r) { int n=right-left+1; if (n=r){ InsertSort(left,right); return left+k-1; } for (int i=1;i=n/r;i++){ InsertSort(left+(i-1)*r,left+i*r-1); Swap(left+i-1, left+(i-1)*r+Ceil(r,2)-1); } int j=Select(Ceil(n/r,2),