算法与程序设计：第2章 分治法.ppt

快速排序示例初始 [722657884280724860]1：[26574248]60[80728872]2：[2642]48[57]60[80728872]3：[26]42485760[80728872]4：2642485760[72]72[8088]5：2642485760[72]72[80]886：[264248576072728088]快速排序可能会对相等值的记录改变相对顺序，所以是不稳定排序算法。*2.3.1二叉查找算法【实例】已知序列A={5，7，12，25，34，37，43，46，58，80，92，105}，要求查找v=46。第一步：设定i=1，j=12mid=└(i+j)/2┘=6v=46A[mid]=37第二步：设定i=7,j=12mid=└(i+j)/2┘=9v=46A[mid]=58第三步:设定i=7,j=8mid=└(i+j)/2┘=7v=46A[mid]=43第四步：设定i=8,j=8mid=└(i+j)/2┘=8v=46=A[mid]=46返回8，找到。下取整若要查找35呢？【例1】二叉查找算法伪代码BinarySearch描述算法：BinarySearch(A,v,low,high)whilelow=highdomid←(low+high)/2ifv=A[mid]thenreturnmidelseifvA[mid]thenlow←mid+1elsehigh←mid-1returnNIL算法复杂度分析*【例1】二叉查找算法A={5，7，12，25，34，37，43，46，58，80，92，105}二叉查找算法的运行过程可以形成是一棵二叉判定树。试一下运行过程，查找v=25v=5763124597128101158374392468010512572534在含有n个不同元素的集合中同时找出最大值和最小值。MAXMIN(A)max←min←A[1]fori←2tondoifA[i]maxthenmax←A[i]elseifA[i]minthenmin←A[i]returnmaxmin2.3.2找最大值与最小值【例2】【问题】最好情况下，最坏情况下，时间复杂度是？【例2】找最大值与最小值将分治策略应用于此问题，每次将问题分解为大致相等的两部分，分别找出最大最小值，再将这两个子问题的解组合成原问题的解。当每个子序列只含有1个或2个元素时，视为分解结束。子序列依次两两合并找出较长序列的最大最小值，直到合并成原始序列。【例2】找最大值与最小值给定元素集A={5，4，6，3，8}用分治算法找出最大值和最小值。第一步：i=1,j=5mid=(1+5)/2=3第二步：i=1,j=3mid=(1+3)/2=2第三步：i=1,j=2比较一次得到gmax=5,gmin=4第四步：i=3,j=3得到hmax=hmin=6边界第五步：i=1,j=3比较gmax和hmax比较gmin和hmin得到fmax=6，fmin=4第六步：i=4，j=5比较一次，得到hmax=8,hmin=3第七步：i=1，j=5比较得到全序列fmax=8，fmin=3【例2】找最大值与最小值