基于分治和递归策略的排序算法及实现.doc

基于分治和递归策略的排序算法及实现孙义欣(潍坊工程职业学院继续教育学院，山东 青州 262500)摘 要：对关键字数量远少于记录数量的排序问题进行了研究，提出了基于分治和递归策略的有效算法。经与选择排 序算法比较，该算法在各种情况下的交换次数均明显少于经典的选择排序算法。关键词：排序；关键字；分治；递归中图分类号：TP312文献标志码：A文章编号：1006-8228（2012）01-27-02Sorting algorithm based on divide-and-conquer strategy and recursive strategy and its realizationSun Yixin（College of Further Education, Weifang Engineering Vocational College, Qingzhou, Shandong 262500, China） Abstract：The sorting problem for the number of keywords far less than that of records is researched, and an effective algorithm based on divide-and-conquer and recursive strategies is put forward. Compared with selection sorting algorithm, the exchangingfrequency of this algorithm is obviously less than that of classic selection sorting algorithm under various circumstances.Key words：sorting；keyword；divide and conquer；recursion0 引言递归技术经常用在算法设计之中，并由此产生许多结构清 晰、可读性强的算法。一个函数、过程、概念或数据结构，如果 在其定义内部或说明内部直接或间接地出现其自身的引用，或 者是为了描述某一问题的状态，必须用到它的上一状态，而描 述上一状态又必须用到它的再上一状态这种用自己来定 义自己的方法，称之为递归或者递归定义。在程序设计中，函 数直接或间接调用自己，就称为递归调用。若调用自己，称之 为直接递归。若函数 p 调用函数 q，而 q 又调用 p，则称之为间接 递归。要使用递归技术编程，首先要确定求解问题的递归模 型，然后再转换成对应的用某种语言编写的函数或过程。递归 模型反映了一个递归问题的递归结构。以 Fibonacci 数列为例，它可以递归定义为：归分解不是随意地分解，递归分解要保证“大问题”与“小问题”规模不同但模型相似。任何一个可以用计算机求解的问题所需的求解时间都与 其规模有关。问题的规模越小，解题所需的计算时间往往也越 少，从而也更加容易处理。但有时候要想直接解决一个较大的 问题，可能是比较困难的。分治法的设计思想是，将一个难以 直接解决的大问题，分割成一些规模较小的问题，分割出的各个小问题与原问题类型相同但规模较小，这样便于各个处理，分而治之。如果原问题可分割成 k 个子问题，11F(0)=1 和 F(1)=1 给出了递归的终止条件，我们称为递归出口；F(n)=F(n-1)+F(n-2)给出了 F(n)与其前两项的关系，我们称 之为递归体。一般地，一个递归模型是由递归出口和递归体两 部分构成的，前者确定递归到何时结束，后者确定递归的方 式。递归设计是把一个不能或不好直接求解的“大问题”转化 为一个或几个“小问题”，再把这些“小问题”进一步分解为更小 的“小问题”来解决，即通过分解使问题的规模逐渐降低，直至 每个小问题都可以直接解决（此时分解到递归出口）。当然，递收稿日期：2011-10-20作者简介：孙义欣（1968-），男，山东寿光人，教师，硕士，主要研究方向：最优化理论，算法设计与分析。用 backMin 来记录该位置，其初始值为 high；if afrontMaxabackMin then afonrtMax aBackMin;exchangeNum = exchangeNum+1;if 没有交换 then /分别在数组的前半部分和后半部分中进行递归处理；exchangeNum+=前半部分的处理所需的交换次数+后半部 分的处理所需的交换次数；果我们在排序交换时尽可能地做到使两条记录同时到位，则交换次数肯定会减少。 若要将序列排成非递减序列，关键字小的记录则最终应该处在序列的前半部分，而关键字大的记录最终应该处在序列的 后半部分。我们先对待排序序列处理一遍，将整个序列分成两 部分，即关键字小的记录都在第一部分中，关键字大的记录都 在第二部分中，即将原序列分为两个较小的序列。这样，原序 列经过分治处理后就变成了两个相似序列，而两个序列的规模 都变小了，这一就可以对前后两部分进行递归处理。为此，我们可以按如下方法进行排序：假设 alowhigh是 一维数组，让变量 mid=(low+high)/2；指针 i、j 作为控制搜索的 变量，指针 i 用来在记录的前半部分搜索，指针 j 用来在记录的 后半部分搜索；指针 frontMax 用来记录数组前半部分中关键字 值最大的位置，每次搜索其初始值都为 low，指向第一个记录位 置；指针 backMin 用来记录数组后半部分中关键字值最小的位 置，每次搜索时其初始值都为 high，指向最后一个记录的位置； 为了考查算法的效率，我们设置了变量 exchangeNum 用来记录 发生交换的次数，其初始值为 0。排序的具体过程为：首先从序列的开始（第 low 条记录）在 序列的前半部分搜索关键字值最大的记录，用变量 frontMax 来 记录在前半部分中找到的关键字值最大的位置；从序列的最后 开始（第 high 条记录）在序列的后半部分中搜索关键字值最小 的记录，用变量 backMin 记录在序列后半部分中找到的关键字 值最小的位置。搜索完一遍后用 frontMax 指示的记录的关键 字值 afrontMax和 backMin 指示的记录的关键字值 abackMin 进行比较，若 afrontMax abackMin，说明这两个位置上的 记录都不在正确的位置上，则这两个位置的记录要做一次交 换，同时将交换次数 exchangeNum 增加 1。由于序列关键字的 数量是有限的，这样进行一次交换就有可能使两条记录同时到 位，从而可以有效地减少记录交换的次数；若在搜索完成后没 有发生交换，说明前半部分中所有记录的关键字值都不大于后 半部分中所有记录的关键字值，则结束本次搜索过程。然后将 整个序列分为前后两个部分 alowmid和 amid+1high,即 采取分治策略，在这两个部分中再分别执行上述过程，也就是 对 两 部 分 分 别 进 行 递 归 调 用 ，而 交 换 次 数 也 相 应 的 为 exchangeNum=exchangeNum+前半部分交换的次数+后半部分 交换的次数。3 算法实现 我们给出实现上述过程的算法如下： 输入：n 个元素的数组a0.n-1。输出：按非降序排列的数组 a0.n-1，排序需要的元素交 换次数 exchangeNum。exchangeNum=0;/初始交换次数为 0else/数组中的元素个数等于 2if(alowahigh) then alow ahigh;exchangeNum+;return exchangeNum; /将交换次数返回该方法操作示意图如下：backMin示意图的序列上经过、步的交换之后，序列变成了 下面的情况：在本例中，我们发现只经过了三次交换序列就已经变成了非递减排序，而交换次数比使用选择法排序少一次。如果待排 序的数据比较多，或者数据的原始位置不和上面所举例子一 样，则很可能经过第一遍的操作之后整个序列还没有完全达到要求，那么就可以采取分治策略，将整个数组分为前后两部分，然后在两部分中分别实施上述过程，即进行递归处理。4 与使用选择法排序的比较下面给出使用本算法和使用选择法进行处理的几组对照 数据，从中可以看出，在任何情况下使用本算法排序在交换次 数上都少于或等于使用选择法排序所需的交换次数。最好情况是数据本身就有序的情况，这时两种方法的交换 次数都是 0。第一组：最差情况，所有数据都不在正确位置上。 初始数据：90 90 75 60 60 90 60 75 75 75用选择法的交换次数：7；使用本算法的交换次数：6。 第二组：随机情况。初始数据：60 90 60 75 90 90 75 60 60 75 用选择法的交换次数：6； 使用本算法的交换次数：4。 第三组：随机情况。初始数据：90 75 60 75 75 90 60 75 90 60(下转第 30 页)if数组中的元素个数大于两个 thenmid=(low+high)/2;/mid 为中间元素的位置while (记录还没有搜索完成) 在数组的前半部分搜索关键字值最大的记录位置； 用 frontMax 来记录该位置，其初始值为 low； 在数组的后半部分中搜索关键字值最小的记录位置；60606060757575909090frontMax90759060757560906060frontMaxbackMinbackMinfrontMax绘制图形时，特别要注意 x、y 的长度需一致。所绘折线功如图 1 所示。通过图形也可看出：MATLAB 默认的极坐标的显 示格式是每隔 30 度显示一条径向线，并进行角度标注。如果不 能自定义径向线的角度和名称标注，将不能借此表达雷达图的 多元参数信息。若要对参数进行修改，就要修改 MATLAB 的系统函数 pola（r 极坐标绘制函数）。为避免发生意外错误，建议对该系统 函数 polar 进行复制修改，如复制再生成一个系统函数 mypolar。在 matlab 命令窗口键入： edit mypolar.m2.1 绘制径向线进入 mypolar 函数，找到%plot spokes（绘制径向线）：th = (1:6)*2*pi/12;cst = cos(th); snt = sin(th);cs = -cst; cst; sn = -snt; snt; line(rmax*cs,rmax*sn,linestyle,ls,color,tc,linewidth,1,.handlevisibility,off,parent,cax)程序中 th 表示两条径向线以 30 度为间隔，只要对其进行修 改即可自定义分配径向线的个数与夹角。如修改为 th = (1:8)*2*pi/16，则圆上分布 16 条径向射线，间隔为 22.5 度。然后，要 对程序中随后出现的夹角参数进行相应修改（30 改为22.5）。2.2 径向线标注的修改我们不仅需要修改径向线的个数与夹角，还要修改其标 注，将角度标注修改为用户所需要的雷达图（比如：方向 E、W、 S、N等）。修改仍需要在 polar.m 中进行。% annotate spokes in degrees（标注）rt = 1.1*rmax;for i = 1:length(th)text(rt*cst(i),rt*snt(i),int2str(i*22.5),. %int2str(i*22.5)是关键horizontalalignment,center,.handlevisibility,off,parent,cax);程序中 text 表示在某个指定的位置(rt*cst(i),rt*snt(i)进行 标注，也可以自行定义字符向量对其进行替换即可。2.3 方向的修改3从图 1 可见，该图的 0 度从东向(X 轴的正向)开始，且以逆 时针方向为正方向。为了将方向修改为以顺时针为正向，以及定义北向或其他角度为 0 度，可以通过图片窗口的工具栏的Rotate 对图 1 进行旋转，旋转成用户所需要的结果。这样做的 缺点是有可能会存在误差，不精确，甚至有可能雷达图给转成 椭圆状。为此可以使用视角函数 view（x,y），其中参数 x,y 用度 数表示，这样，改变一下用户的视角就可能得到想要的任何角 度 。 图 1 生 成 的 默 认 视 角 为 view（0，90）。 如 设 置 为 view（0，-90），则以顺时针方向为正方向；如设置为 view（90，-90），则可以将北向改为 0度。通过视角函数 view 对雷达图的方向进行设置，明显比通过 手工 Rotate 调节更为方便。2.4 其他修改3除上述修改外，还可以对雷达图进行其他设置，如：标题位 置，标注大小，线的宽细线宽修改示例：set(findobj(get(gca,Children),LineWidth,0.5),LineWidth,2);在多图显示时，如用 subplot(m,n,p)在一个窗口生成多个雷 达图时，可通过 position 对每个子图的大小、位置进行设置，使 整体的图片布局更为合理。3 结束语本文的研究表明，用 MATLAB 绘制雷达图比用 EXCEL 可 塑性更强。在 MATLAB 中通过修改系统函数 polar，然后运用新的 polar 函数绘制雷达图，再运用函数 view、函数 position，以及修改其他的属性参数，这样得到的雷达图更能满足用户的需求。MATLAB 的绘图功能是非常强大的，我们希望在今后的 使用和学习过程中，能够挖掘出更多实用的技巧。参