找最大和最小元素

1、4 找最大和最小元素如果要在含有n个不同元素的集合中同时找出它的最大和最小元素(元素类型为elemType，可比较大小)，最简单的方法是将元素逐个进行比较。这种直接算法可初步描述如下。算法4.1 直接找最大和最小元素void StraitMaxMin(elemType a，int n，elemType &Max，elemType &Min) / 将A(1：n)中的最大元素置于max中，最小元素置于min中。int i；Max=Min=a1；For(i=2；i=n；+i) if(ai>max) Max=ai；if(ai<max) Min=ai；/for/ Strait

2、MaxMin分析这个算法的时间复杂度时，只需将元素比较次数求出即可。这不仅是因为算法中的其它运算与元素比较有相同数量级的频率计数，而且更重要的是，当A(l：n)中的元素是多项式、向量、非常大的数或字符串时，一次元素比较所用的时间比其它运算的时间多得多。容易看出过程StraitMaxMin在最好、平均和最坏情况下均需要作2(n-l)次元素比较。另外，只要考察一下算法4.1就可发现，只有当A(i)>max为假时，才有必要比较A(i)<min，因此，可用下面的语句代替for循环中的语句：if(ai>max) Max=ai；elseif(ai<Min) Min=ai；在作以上改

3、进后，最好情况将在元素按递增次序排列时出现，元素比较数是n-1；最坏情况将在递减次序时出现，元素比较数是2(n-1)；至于平均情况，A(i)将有一半的数据比max大，因此平均比较数是3*(n-1)/2（即上述两种情况的平均值）。能否找到更好的算法呢？下面用分治策略的思想来设计一个算法与直接算法作比较。使用分治策略设计是将某一实例I=(n，A(l)，A(n)分成一些较小的实例来处理。例如，可以把I分成两个实例：I1=(n/2，A(1)，A(n/2)和I2=(n-n/2，A(n/2+1)，A(n)。如果Max(I)和 Min(I)是I中的最大和最小元素，则Max(I)等于Max(I1)和Max(I

4、2)中的较大者，而Min(I)等于Min(I1)和Min(I2)中的较者。如果I只包含一个元素，则不需要作任何分割，直接就可得到其解。算法4.2依据以上方法所编写的函数，它是在元素集合A(i)，A(i1)，A(j)中找最大和最小元素的递归过程。函数对于集合中含有一个元素(i=j)和两个元素(i=j-1)的情况分别作了处理，而对含有多于两个元素的集合，则确定其中点(正如在二分检索中那样作分割)，并且产生两个新的子问题。当分别找到这两个子问题的最大和最小值后，再比较这两个最大值和两个最小值，最终得到此全集合的解。Max和Min被看成是两个内部函数，它们分别求取两个元素的大者和小者，并认为每次调用其

5、中的一个函数都只需作一次元素比较。算法4.2 递归求取最大和最小元素VOID MaxMin(int i，int j，elemType &fmax，elemType &fmin) / A(1：n)是含有n个元素的数组，参数i，j是整数（1i，jn）/该函数把A(i，j)中的最大和最小元素分别赋给fmax和fmin。int A，n； /n和数组A（1，n）说明成全程变量。if(i=j) fmax=fmin=ai；return fmax，fmin；if(i=j-1) if(ai<aj) fmax=aj；fmin=ai；else fmax=ai；fmin=aj；return fm

6、ax，fmin；/ifmid = (i+j) 2；MaxMin(i，mid，gmax，gmin)；MaxMin(mid+1，j，hmax，hmin)；fmax=max(gmax，hmax)；fmin=min(gmin，hmin)；return fmax，fmin；/MaxMin这个函数过程最初由调用MaxMin(l，n，x，y)实现。为加深对这个过程的理解，请看下面的例子。例4.1 在下述九个元素上模拟函数过程MaxMin。a1.9：l 2 3 4 5 6 7 8 922 13 -5 -8 15 60 17 31 471,91,51,31,23,34,58,96,76,91，9，60，-86，

7、9，60，178，9，47，316，7，60，171，5，22，-84，5，15，-81，3，22，-53，3，-5，-51，2，22，13图4.1 表示MaxMin递归调用的树mid=5mid=3mid=2mid=7用一棵树来描述递归调用的轨迹是很清晰的，其中的一个结点表示一次递归调用，每作一次新的调用就增加一个结点。对于这个程序来说，每个结点有四项信息：i，j，fmax，fmin。根据上面的数组 a，就可画出图4.1所示的树。图中，根结点的1和9是最初调用MaxMin的i，j值。本次调用产生对MaxMin的两次新的调用，其中i，j的值分别有1，5和6，9。这样就把集合分成了大小基本相同的两

8、个子集。由4.1所示的树可以直接看到递归的最大深度是4（包括第一次调用），每个结点左上方圆圈中的数字表示给fmax和fmin赋值的次序。 0 n=1T(n)= 1 n=2 T(n/2) + T(n/2) n>2MaxMin需要的元素比较数是多少呢？如果用T(n)表示这个数，则可导出的递归关系式:当n是2的幂时，即对于某个正整数k，n=2k，有T(n) = 2T(n/2) + 2= 2(2T(n/4) + 2) + 2= 4T(n/4) + 4 + 2= 2i0ik-2= 2k-1T(2) + 3= 2k-1 + 2k 2= 3n/2-2注意：当 n是2的正整数幂时，3n/2-2是最好，平

9、均及最坏情况的比较。它和直接算法的比较次数2n-2相比，减少了25。可以证明，任何一种以元素比较为基础的找最大和最小元素的算法的比较下界均为3n/2-2。因此，函数MaxMin在这种意义上是最优的。那末，这是否意味着此算法确实比较好呢？不一定。其原因有如下两个。一是MaxMin要求的存储空间比直接算法多。给出n个元素就有log2n+1级的递归，而每次递归调用需要保留到栈中的有 i，j，fmax，fmin和返回地址五个值。虽然可用前面介绍的递归化迭代的规则去掉递归，但所导出的迭代模型还需要一个其深度为log2n数量级的栈。 2 n=2C(n)= 2C(n/2) + 3 n>2二是当元素ai

10、和aj的比较时间与i和j的比较时间相差不大时，MaxMin并不可取。为说明问题，假设元素比较与 i和 j间的比较时间相同，又设MaxMin的频率计数为C(n)，n=2k，k是某个正整数，并且对i=j和i=j-1用ij-1的比较代替，这样，只需对i和 j-l作一次比较就足以实现其功能。于是MaxMin的频率计数为：解此关系式可得：C(n) = 2C(n/2) + 3= 4C(n/4) + 6 + 3= 2i0ik-2= 2k-1C(2) + 3 = 2k + 3*2k-1-3= 5n/2 3 。而StraitMaxMin的比较数是3(n1)(包括实现for循环所要的比较)。尽管它比5n/2-3大

11、一些，但由于递归算法中i，j，fmax，fmin的进出栈所带来的开销，因此MaxMin在这种情况下反而比直接比较算法StraitMaxMin还要慢一些。根据以上分析可以得出结论：如果a的元素间的比较的复杂程度远比整型变量的比较代价大，则分治方法产生效率较高(实际上是最优)的算法；反之，就得到一个效率较低的程序。因此，分治策略只能看成是一个较好的然而并不总是能成功的算法设计指导。算法4.3是找最小元素和最大元素的非递归算法，请读者分析并验证其时间复杂度。Void MinMax(elemType w，int n，int &Min，int &Max) /寻找w0：n-1中的最小和最大

12、元素。如果少于1个元素，则返回false否则返回true/且Min保存最小元素的下标；Max保存最大元素的下标。if(n<1) return false； /对n1，做特殊处理。if(n=1) Min = Max = 0；return true； /当n=1时，最大和最小元素的下标都为0。int s； /对Min和Max进行初始化并定义循环起点if(n2) Min = Max = 0；S = 1；/当n为奇数时；设最大和最小元素的下标为0。/并设循环起点s=1。else /当n为偶数时，比较w0和w1，设定最大和最小元素，并设循环起点s=2。if(w0>=w1) Min = 1；M

13、ax = 0；else Min = 0；Max = 1；S = 2；/比较余下的偶数个数据元素（成对比较）for(i=s；i<n；i+=2) /寻找wiwi+1的较大者并与wMax进行比较，确定新Max。/寻找wiwi+1的较小者并与wMin进行比较，确定新Min。if(wi>wi+1) if(wi>wMax) Max = i；if(wi+1<wMin) Min = i+1；else if(wi+1>wMax) Max = i+1；if(wi<wMin) Min = i；/forreturn true；/MinMax复杂度分析：当n为偶数时，循环中的比较次数

14、为3(n/2-1)；总比较次数为3n/2-2。当n为奇数时，循环中的比较次数为3(n-1)/2；总比较次数为3(n-1)/2。取n=16和n=17验证上述分析。5 归并分类（归并排序） 5.1 基本方法给定一个含有n个元素(又叫关键字)的集合，如果要把它们按一定的次序分类(本节中自始至终假定按非递减分类)，最直接的方法就是插入法。对A(1：n)中元素作插入分类的基本思想是：for(j=2；n；+j)将Aj放到已分类集合A1：j-1的正确位置上；从中可以看出，为了插入A(j)，有可能移动A(1：j-1)中的所有元素，因此可以预计该算法在时间特性上不会太好，算法具体描述如下：算法5.1 直接插入分

15、类void InsertionSort(elemType a，int n) /将A(l：n)中的元素按非递减分类。n1int i；for(j=2；n；+j) /A(l:j-l)已分类。a0=aj；i = j - 1；while (a0<ai) /0ij，a0作为哨兵元素，这是一种编程技术。ai+l = ai；i = i - 1；/whileai+1 = a0；/for/ InsertionSortwhile循环中的语句可能执行0j次(j=2，3，n)，因此，这函数过程的最坏情况限界是：j=(n(n+1)/2)-l=(n2)2jn如果输入数据本来就是按非递减排列的，则根本不会进入while

16、的循环体，这就是最好情况，计算时间是(n)。如果用分治策略来设计分类算法，则可使最坏情况时间变为(nlog2n)。这样的算法称为归并分类算法。其基本思想是：将A(1)，A(n)分成两个集合A(1)，A(n/2)和A(n/2+1)，A(n)。对每个集合单独分类，然后将已分类的两个序列归并成一个含n个元素的分好类的序列。这种思想是典型的分治设计思想。函数过程MergeSort通过使用递归和调用把两个已分类集合归并在一起的子函数过程Merge，非常简洁地刻画了这一处理过程。算法5.2 归并分类void MergeSort(int low，int high) /A(low：high)是一个全局数组，它

17、有high-low+l0个待分类元素且High，low大于0。int mid；if(low<high) mid = (low + high) / 2； /求这个集合的分割点。MergeSort(low，mid)； /将一个子集合分类MergeSort(mid+1，high)； /将另一个子集合分类Merge(low，mid，high)； /归并两个已分类的子集合；/if/ MergeSort算法5.3 使用辅助数组，归并两个已分类的集合void Merge(int low，int mid，int high) /A(low：high)是一个全程数组，它含有两个放在A(low，mid)和A(

18、mid+l，high)中的/已分类的子集合。目标是将已分类的两个集合归并成一个集合并存放到A(low：high)中。/算法中使用了一个辅助数组B(low：high)int h，i，j，k； /lowmidhighelemType alow：high； /alow：high定义成全程变量elemType blow：high；h = low；i = low；j = mid + 1；while(h<=mid) and (j<=high) /当两个集合都没取处理完时继续进行。if(ah<=aj) bi = ah；+h；else bi = aj；+j；+i；/whileif(h>

19、mid) for(k=j；k=high；+k) bi = ak；+i； /处理剩余的元素else for(k=h；k=mid；+k) bi = ak；+i； /处理剩余的元素；/iffor(k=low；k=high；+k) /将已归并的集合复制到Aak=bk；/for/Merge在函数过程MergeSort开始前，这n个元素应放在A(1：n)中。使用MergeSort(1，n)语句将使关键字重新排列成非递减序列而存于A中。例5.1 用归并分类算法，将含有十个元素的数组A=(310,285,179,652,351,423,861,254,450,520)按非递减分类。函数过程MergeSort首

20、先把A(1：10)分成两个各有五个元素的子集合，然后把A(1：5)分成大小为3和2的两个子集合，再把A(1：3)分成大小为2和1的子集合，最后将A(1：2)分成各含一个元素的两个子集合，至此就开始归并。此时的状态可排成下列形式：(310|285|179|652，351|423，861，254，450，520)其中，直线表示子集合的边界线。归并A(1)和A(2)得：(285，310|179|652，351|423，861，254，450，520)再归并A(1：2)和A(3)得：(179，285，310|652，351|423，861，254，450，520)然后将A(4：5)分成两个各含一个元素

21、的子集合，再将两个子集合归并得：(179，285，310|351，652|423，861，254，450，520)接着归并A(1：3)和A(4：5)得：(179，285，310，351，652|423，861，254，450，520)此时算法就返回到MergeSort首次递归调用的后继语句的开始处，即准备执行第二条递归调用语句。又通过反复地递归调用和归并，将A(6：10)分好类，其结果如下：(179，285，310，351，652|254，423，450，520，861)这时就有了两个各含5个元素的已分好类的子集合。经过最后的归并得到整个分好类的结果：(179，254，285，310，351，

22、423，450，520，652，861)图5.1所示的是在n=10的情况下，由MergeSort所产生的一系列递归调用的树的表示。每个结点中的一组值是参变量low和high的值。注意：集合的分割一直进行到产生出只含单个元素的子集合为止。图5.2所示的则是一棵表示MergeSort对函数过程Merge调用的树型结构。每个结点中的值依次是参变量low，mid和high的值。例如，含有值1，2，3的结点表示A(1：2)和A(3)中元素的归并。1,1,21,2,31,3,51,5,104,4,5图5.2 Merge调用过程的树型表示6,6,76,7,89,9,106,8,101,101,51,31,2

23、1,14,54,45,53,32,26,106,86,76,67,7图5.1 MergeSort(1,10)调用过程的树型表示10,109,99,108,8 a n=1，a是常数T(n)= 2T(n/2) + cn n>1，c是常数如果归并运算的时间与n成正比，则归并分类的计算时间可用递归关系式描述如下：当 n是2的正整数幂，即n=2k时，可以通过逐次代入求出其解：T(n) = 2(2T(n/4) + cn/2) + cn= 4T(n/4) + 2cn= 4(2T(n/8) + cn/4) + 2cn= = 2kT(1) + kcn= an + cnlog2n如果2kn2k+1，易于看出

24、T(n)T(2k+1)。因此T(n)(nlog2n)。5.2 改进的归并分类算法尽管算法5.2相当充分地反映了使用分治策略对数据对象分类的长处，但仍存在着一些明显的不足，从而限制了分类效率的进一步提高。下面来逐一分析这些不足之处，并提出相应的改进措施，以期能给出一个更有效的归并分类模型。在使用例5.1的数据集模拟执行MergeSort的过程中，可以看到，每当集合被分成只含两个元素的子集合时，还需要使用二次递归调用将这子集合分成单个元素的集合。这表明该算法执行到将集合分成含元素相当少的子集合时，很多时间不是用在实际的分类而是消耗在处理递归上。如果不让递归一直进行到最低一级，就可对这种情况做出改进

25、。从抽象化控制过程来看，只要使Small(p,q)在输入规模q-p+1适当小时取真值，而在这种情况下采用另一个能在小规模集合上有效工作的分类算法就能克服低层递归调用所带来消耗过大的问题。本节开始所给出的插入分类算法尽管时间复杂度为(n2)，但当 n很小(譬如小于16)时却能极快地工作，因此，将它作为归并分类算法中处理小规模集合情况的子过程是很适宜的。另外，归并分类算法使用了辅助数组B(1：n)，这是一个明显的不足之处。但是，由于不可能在两个已分类集合的原来的位置上进行适当的归并，所以这n个位置的附加空间对于本算法是必需的。而且算法还必须在这附加空间上竭力地工作，在每次调用Merge时，把存放在

26、B(low：high)中的结果复制到A(low：high)中去。不过，使用一个以整数表示的链接信息数组Link(l：n)来代换暂时存放元素的辅助数组B可以节省一些附加空间。这个链接数组在1，2，n的范围内取值。这些整数看成是A的元素的指针，在分类表中它指向下一个元素所在的下标位置。因此，分类表就成了一个指针的序列，而分类表的归并则不必移动元素本身，只要改变相应的链值即可进行。用0表示表的结束。下面是Link值的一个集合，它包含了两个已分类子集合的元素链接信息表。Q和R分别表示两个表的起始位置，这里Q=2，R=5。Link (1) (2) (3) (4) (5) (6) (7) (8)6 4 7

27、 1 3 0 8 0Q=2的表是(2，4，1，6)，R=5的表是(5，3，7，8)。这两个表分别描述了A(1：8)中两个已分类子集合，它们有A(2)A(4)A(1)A(6)和A(5)A(3)A(7)A(8)。下面是采取了以上两种改进措施的归并分类模型。算法5.3 使用了链接的归并分类模型。Void MergeSort1(int low，int high，int p) /利用辅助数组Link(low，high)，将全程数组A(low：high)按非递减分类。Link中值表示/按分类次序给出A下标的表，并把P置于指示这表的开始处elemType alow：high； /alow：high定义成全程

28、变量int Linklow：high；if(high-lOW+1)16 InsertionSort(a，Link，low，high，p)；else mid=(low + high)/2；MergeSort1(low，mid，q)； /返回q表MergeSort1(mid+1，high，r)； /返回 r表Merge1(q，r，p)； /将表q 和r归并成表p/MergeSort1在初次调用MergeSort1时，把要分类的元素(即关键字)先放到A(1：n)中，并且将Link(l：n)置成0。初次调用语句为MergeSort1(1，n，p)，p作为按分类次序给出 A中元素的指示表的指针返回。这里

29、的MergeSort算法5.1的改型，它把对A(low：high)的分类表变成起始点在P的链接信息表。每当被分类的项数小于16时就调用它。修改过的归并过程如下：算法5.4 使用链接表归并已分类的集合。Void Merge1(q，r，P)/q和r是全程数组Link(1：n)中两个表的指针。这两个表可用来获得全程数组A(1：n)中/已分类元素的子集合。此算法执行后构造出一个由p所指示的新表，利用此表可以得到/按非递减把A中元素分好类的元素表，同时q和r所指示的表随之消失。假定Link(0) /被定义，且假定表由0所结束。ElemType an，Linkn；int n；/定义成全局变量int i，j

30、，k；i=q；j=r；k=0； /新表在Link(O)处开始while(i!=0 and j!=0) /当两表皆非空时作if(ai<=aj) /找较小的关键字Linkk=i；k=i；i=linki； /加一个新关键字到Link中else Linkk=j；k=j；j=linkj；/whileif(i=0) Linkk=j；else Linkk=i；P=Link0；/Merge1为了帮助理解这个新的归并分类模型，下面来看一个例子。例5.1 假设要对下述 8个元素序列(50，10，25，30，15，70，35，55)分类。要求使用新算法模拟执行。这里略去在少于16个元素时应使用Insertio

31、nSort分类的要求。Link数组初始化为 0。表5.1显示了在每一次调用MergeSort1结束后Link数组的变化情况。各行上的P值分别指向最近一次Merge1结束时所产生的Link中的那个表。右边是这些表所表示的相应的已分类元素子集合。例如，在最后一行，P=2表示链表(2，5，3，4，7，1，8，6)在2处开始，而此链表意味着A(2)A(5)A(3)A(4)A(7)A(1)A(8)A(6)。表5.1 例5.1中Link数组的变化过程a(0)(1)(2)(3)(4)(5)(6)(7)(8)-5010253015703555Link000000000Q r p1 2 2201000000(1

32、0,50)3 4 3301400000(10,50),(25,30)2 3 2203410000(10,25,30,50)5 6 5503416000(10,25,30,50),(15,70)7 8 7703416080(10,25,30,50),(15,70) ,(35,55)5 7 5503417086(10,25,30,50),(15,35,55,70)2 5 2285473016(10,15,25,30,35,50,55,70)除了以上改进之外，还可采用由底向上的方式设计算法，从而取消对栈空间的需要。5.3 以比较为基础分类的时间下界尽管作了以上改进，但不难看出，新归并分类算法的时间复

33、杂度在最坏情况下仍为(nlog2n)。事实上，任何以关键字比较为基础的分类算法，它的最坏情况的时间下界都为(nlog2n)，因此，从数量级的角度上来看，归并分类算法是最坏情况的最优算法。利用第3小节所描述的二叉比较树，也很容易给出以比较为基础的分类算法时间下界的证明。在这里，假设参加分类的n个关键字A(l)，A(n)各不相同，因此任意两个关键字A(i)和A(j)的比较必导致A(i)A(j)或者A(i)A(j)的结果。在描述算法各种可能执行的比较树中，每个内结点用比较对“i：j”来代表A(i)和A(j)的比较，A(i)A(j)时进入左分枝，A(j)A(j)时进入右分枝。各外部结点表示此算法的终止

34、。从根到外结点的每一条路径分别与一种唯一的排列相对应。由于n个关键字有n！种排列，而每种排列可以是某种特定输入下的分类结果，因此比较树必定至少有n！个外部结点，每个外结点表示一种可能的分类序列。图5.3给出了对三个关键字分类的一棵二叉比较树。边上的不等式表示此条件成立时控制的转向。1:21,2,32:31:32:31:31,3,23,1,22,1,32,3,13,2,1a(1)<a(2)图5.2 对3个关键字分类的比较树a(1)>a(2)a(3)>a(2)a(3)<a(2)a(2)<a(3)a(2)>a(3)a(1)<a(3)a(1)>a(3)a

35、(1)<a(3)a(1)>a(3) 对于任何一个以比较为基础的算法，在描述其执行的那棵比较树中，由根到某外部结点的路径长度表示生成该外部结点中那个分类序列所需要的比较次数。因此这棵树中最长路径的长度(即此树的高度)就是该算法在最坏情况下所作的比较次数。从而，要求出所有以比较为基础的对n个关键字分类的算法最坏情况下界，只需求出这些算法对应的比较树的最小高度，设它为T(n)。如果一棵二叉树的所有内部结点的级数均小于或等于k，对k进行归纳可以证得该树至多有2k个外部结点(比内部结点数多1)。令T(n)=k,则n！2T(n)而当n1时有n！n(n-1)(n-2)(n/2)(n/2)n/2因

36、此，对于n4有T(n)(n/2)log2(n/2) (n/4)log2n。故以比较为基础的分类算法的最坏情况的时间下界为(nlog2n)。 6 快速分类6.1 快速分类算法子文件中的所有元素都小于或等于另一子文件的任何一个元素。这是通过重新整理A(1：n)中元素的排列顺序来达到的，其实现的基本思想如下：选取A的某个元素，譬如说t=A(S)，然后将其它元素重新排列，使 A(1：n)中所有在t以前出现的元素都小于或等于t，而所有在t后面出现的元素都大于或等于t。文件的这种重新整理叫做划分(Partitioning)，元素t称为划分元素(Partition element)。因此，所谓快速分类就是通

37、过反复对产生的文件进行划分来实现的。函数Partition完成对文件A(m：P-1)的划分。在过程中，假定第一个元素A(m)是划分元素(这种假定是非本质的，仅仅是为了方便而已。后面将会看到，选择其它元素作为划分元素比选第一项要好些)。A(p)不属于文件A(m：P-1)，且假定A(P)A(m)，引进A(p)是为了在特殊情况下能控制程序顺利进行。因此，在对Partition初次调用，即m=1，p-1=n时，则必须将A(n+1)定义成大于或等于A(l：n)的所有元素（假定为+）。函数InterChange(x，y)实现x和y的交换功能。算法6.1 用A(m)划分集合A(m：P-1)void Part

38、ition(m，p)/在A(m)，A(m+1)，A(p-1)中的元素按如下方式重新排列：如果最初t=A(m)，/则在重排完成之后，对于m和p-l之间的某个q，有A(q)=t，并使得对于mkq，/有A(k)t，而对于qkP，有A(k)t/退出过程时，p带着划分元素所在的下标位置，即q的值返回。ElemType an； /定义为全局变量int m，p，i；v=am；i=m； /A(m)是划分元素while(i<p) do i=i+1； while(ai<v) /i由左向右移，至少做一次。do p=p-1； while(ap>v ) /p由右向左移，至少做一次。if(i<p)

39、 InterChange(ai，ap)； /A(i)和A(p)换位；/whileam=ap；ap=v； /划分元素在位置p/ Partition为有助于理解Partition的工作情况，下面来看一个例子。例6.1 用过程Partition来划分下面含九个元素的数组。这函数最初由Partition(1，10)所调用。用水平虚线连结的竖杠指示为产生下一行而交换的两个元素。A(1)=65是划分元素，最终(在第六行)确定它是此数组中的第五小元素。要指出的是，在Partition执行完毕之后，除划分元素之外的所有元素相对于A(5)=65也是被划分了的。(1) (2) (3) (4) (5) (6) (7

40、) (8) (9) (10)ip操作65 70 75 80 85 60 55 50 45 +29交换A(2)和A(9)65 45 75 80 85 60 55 50 70 +38交换A(3)和A(8)65 45 50 80 85 60 55 75 70 +47交换A(4)和A(7)65 45 50 55 85 60 80 75 70 +56交换A(5)和A(6)65 45 50 55 60 85 80 75 70 +65交换A(1)和A(5)60 45 50 55 65 85 80 75 70 +第一趟分类的结果有了划分集合A(m：P-1)的算法，使用分治策略可以设计出一个算法来对n个元素进行

41、分类。随着对函数Partition的一次调用，就会产生出两个这样的集合S1和S2，S1的所有元素小于或等于S2的任何元素。因此S1和S2可独立分类。重复使用过程Partition，每个集合都将被分类。算法6.2描述了这种分类的全过程。算法6.2快速分类void QuickSort(p，q)/将全程数组A(1：n)中的元素A(p)，A(q)按非递减的方式分类。认为A(n+1)已被/定义，且大于或等于A(p：q)的所有元素，即假定A(n+1)为机器最大数。int p，q；elemType an；int n； /定义成全程变量if(q<q) j=q+1；Partition（p,j）；Quick

42、Sort(p,j-1)； /j是划分元素的位置QuickSort(j+1,q)；/if/QuickSort6.2 快速分类分析要分析QuickSort，只需计算出它的元素比较次数C(n)即可。容易看出，其它运算的频率计数和C(n)有相同的数量级。现作如下假定： 参加分类的n个元素各不相同； Partition中的划分元素v是随机选取的。假设对于分析平均情况是必需的。为了能随机选出划分元素v，可先假定有一个在区间i，j中生成随机整数的函数Random(i，j)，然后用下列语句i=Random(m，p-1)；v=ai；ai=am；i=m来代换Partition(m，p)中的赋值语句v=am；i=m

43、。首先要获取C(n)在最坏情况下的值Cw(n)。容易证明，在Partition(m，p)的每一次调用中元素的比较数至多是p-m+1。设r是在任一级递归上对Partition(m，p)的所有调用的元素总数。在一级只有一次调用，执行Partition(1，n+1)，且r=n；在二级至多作两次调用，且r=n-l(在第一级调用时选择的划分元素已经找到了它的确切位置)，等等。在递归的任意一级上，所有的Partition共作(r)次元素比较，而每一级的r，由于删去了前一级的划分元素，故比前一级的r至少要少1。因此Cw(n)=r，即Cw(n)=C(n2)。2rnC(n)的平均值CA(n)比 CW(n)小得多

44、。在上面那些假定下，调用Partition(m，p)时，所取划分元素v是A(m：p-l)中第i个元素，lip-m，具有相等的概率。因此所留下待分类的两个子文件 A(m：j-1)和A(j+l：P-1)的概率是l/(P-m)，mjp。由此，可以得到递归关系式CA(n) = n+1 + (CA(k-1) + CA(n-k)/n (6.1)1knn+1是Partition第一次被调用时所需要的元素比较数。CA(0)=CA(1)=0。用n乘(2.11)式两边，得:nCA(n) = n(n+1) + 2(CA(0)+CA(1) + + CA(n-1) (6.2)用n-1代换(6.2)式中的n，得:(n-1

45、)CA(n-1) = n(n-1) + 2(CA(0) + + CA(n-2) （相当于递推）用(6.2)式减去上式，得:（目的是为了求CA(n)）nCA(n) - (n-1)CA(n-1) = 2n + 2CA(n-1)即CA(n)/(n+1) = CA(n-1)/n + 2/(nl)反复用这个等式去代换CA(n-1)，CA(n-2)，得到CA(n)/(n+1) = CA(n-2)/(n-1) + 2/n + 2/(n+1)= CA(n-3)/(n-2) + 2/(n-1) + 2/n + 2/(n+l)= = CA(1)/2 +2*1/k= 2*1/k3kn+1 3kn+1由于 1/k n

46、+1 dx/x log2(n+1) (6.3)3kn+1 2因此由(6.3)式得出:CA(n)2（n+1)loge(n+1)=(nlogn)由以上分析可知，快速分类算法的最坏情况时间是(n2)，而平均情况时间是(nlogn)。现在来考察递归所需要的栈空间大小，在最坏情况下，递归的最大深度可以达到n-1，因此，所需的栈空间是(n)。例如，当对partition的每一次调用，在其划分元素是A(m：P)中的最小元素时（有序或基本有序），就会出现最坏情况。使用一个快速分类的迭代模型可以使所需的栈空间总量减至(logn)。在这个迭代模型中，当partition把文件A(p：q)分成两个子文件A(p：j-

47、l)和A(j+1：q)之后，总是先对其中长度较小的那个子文件分类。第二条递归调用语句则用几条赋值语句和一条跳转到loop开始处的代码来代替，作了以上修改后，快速分类算法就呈现算法6.3的形式。算法6.3 QuickSort的迭代模型void QuickSort2(p，q)intStack sqStack；elemType a；int j；push(sqStack,p)；push(sqStack,q)；while(!EmptyStack(sqStack) pop(sqStack,q)；pop(sqStack,p)；while(p<q) j=q+1；partition(p，j)；if(j-p

48、)<(q-j) push(sqStack,j+l)；push(sqStack,q)；q=j-1；else push(sqStack,p)；push(sqStack,j-1)；p=j+1；/while对较小的子文件先进行分类。；while/QuickSort2 2 + S(n-1)/2) n1S(n)= 0 n1现在来证明此算法所需的最大栈空间是(logn)。设所需最大栈空间是S(n)，它遵从如果每趟排序都将分类序列划分成两个长度相近的子序列，则根据二分检索的结果知，S(n)2logn。如同第5节所述，InsertionSort在n小于16的情况下执行是相当快的，因此，QuickSort2

49、可以在每当q-p小于16时用InsertionSort来加速。QuickSort和mergeSort的平均情况时间都是(logn)，在平均情况下哪个更快一些呢？这里不给出其理论证明，而是给出一组在IBM370158机上测试的数据来作近似的比较。这两个算法都是用 PL1编程的递归模型，对于QuickSort，partition中划分元素采用了三者取中的规则(即划分元素是A(m)，A(m+p-1)2)和A(p-l)中值居中者)。输人数据集由(0，10000)的随机整数组成。表6.1记录了以毫秒为单位的实际平均计算时间。研究这个表立即就可看出，对应于n的所有取值，QuickSort都比MergeSo

50、rt快。而且还可看到，每当 n值增加500，QuickSort大致增加250ms；MergeSort则不规则一些，n每增加500，其平均计算时间大约增加350ms。表6.1 分类算法的平均计算时间（ms）n10001500200025003000350040004500MergeSortQuickSort500400750060010508501400105016501300200015502250180026502050n50005500600065007000750080008500MergeSortQuickSort290023003450265035002800385030004250

51、33504550370049503900520041007 选择问题上述partition算法也可用来求选择问题的有效解。在这一问题中，给出n个元素A(1：n)，要求确定第k小的元素（由小到大排序的第k个位置上的元素），如果划分元素v是A(j)，则说明有j-1个元素不大于A(j)，而其余n-j个元素都不小于A(j)。因此，若k<j，则第k小元素在A(1：j-1)中；若k=j，则第k小元素为A(j)；若k>j，则第k小元素在A(j+1：n)中的第k-j小元素。根据这一思路倒出的算法7.1如下。此函数把第k小元素放在A(k)，并划分剩余元素使得A(i)A(k)，1ik且 A(i)A(k)，kin。7.1 选择问题算法算法7.1 找第k小的元素void Select(elemType a，int n，int &k) /在数组A(1：n)找第k小的元素s并存放在A(k)中（1kn），即A(k)=s。/将剩余元素按如下形式重新排列，使得A(m)A(k)，1mk且 A(m)A(k)，kmn。/假设A(n+1)=+。int k，m，r，j，t；m = 1