计算机时代２０１２年第１期 ・ ２７ ・ 基于分治和递归策略的排序算法及实现 孙义欣 （潍坊工程职业学院继续教育学院，山东青州２６２５００） 摘要：对关键字数量远少于记录数量的排序问题进行了研究，提出了基于分治和递归策略的有效算法。经与选择排 序算法比较，该算法在各种情况下的交换次数均明显少于经典的选择排序算法。 关键词：排序；关键字；分治；递归 中图分类号：ＴＰ３１２ 文献标志码：Ａ 文章编号：１００６—８２２８（２０１２）０１—２７—０２ Ｓｏｒｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｉｖｉｄｅ—ａｎｄ－ｃｏｎｑｕｅｒ ｓｔｒａｔｅｇｙ ａｎｄ ｒｅｃｕｒｓｉｖｅ ｓｔｒａｔｅｇｙ ａｎｄ ｉｔｓ ｒｅａｌｉｚａｔｉｏｎ Ｓｕｎ Ｙｉｘｉｎ （Ｃｏｌｌｅｇｅ ｏｆ Ｆｕｒｔｈｅｒ Ｅｄｕｃａｔｉｏｎ，Ｗｅ扣ｎｇ Ｅｎｇｉｎｅｅｒｉｎｇ Ｖｏｃａｔｉｏｎａｌ Ｃｏｌｌｅｇｅ，Ｑｉｎｇｚｈｏｕ，Ｓｈａｎｄｏｎｇ ２６２５００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｓｏｒｔｉｎｇ ｐｒｏｂｌｅｍ ｆｏｒ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｋｅｙｗｏｒｄｓ ｆａｒ ｌｅｓｓ ｔｈａｎ ｔｈａｔ ｏｆ ｒｅｃｏｒｄｓ ｉｓ ｒｅｓｅａｒｃｈｅｄ，ａｎｄ ａｎ ｅｆｆｅｃｔｉｖｅ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｄｉｖｉｄｅ—ａｎｄ—ｃｏｎｑｕｅｒ ａｎｄ ｒｅｃｕｒｓｉｖｅ ｓｔｒａｔｅｇｉｅｓ ｉｓ ｐｕｔ ｆｏｒｗａｒｄ．Ｃｏｍｐａｒｅｄ ｗｉｔｈ ｓｅｌｅｃｔｉｏｎ ｓｏｒｔｉｎｇ ａｌｇｏｒｉｔｈｍ，ｔｈｅ ｅｘｃｈａｎｇｉｎｇ ｆｒｅｑｕｅｎｃｙ ｏｆ ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｉｓ ｏｂｖｉｏｕｓｌｙ ｌｅｓｓ ｔｈａｎ ｔｈａｔ ｏｆ ｃｌａｓｓｉｃ ｓｅｌｅｃｔｉｏｎ ｓｏｒｔｉｎｇ ａｌｇｏｒｉｔｈｍ ｕｎｄｅｒ ｖａｒｉｏｕｓ ｃｉｒｃｕｍｓｔａｎｃｅｓ． Ｋｅｙ ｗｏｒｄｓ：ｓｏｒｔｉｎｇ；ｋｅｙｗｏｒｄ；ｄｉｖｉｄｅ ａｎｄ ｃｏｎｑｕｅｒ；ｒｅｃｕｒｓｉｏｎ ０引言 归分解不是随意地分解，递归分解要保证“大问题”与“小问题” 递归技术经常用在算法设计之中，并由此产生许多结构清 规模不同但模型相似。 晰、可读性强的算法。一个函数、过程、概念或数据结构，如果 任何一个可以用计算机求解的问题所需的求解时间都与 在其定义内部或说明内部直接或间接地出现其自身的引用，或 其规模有关。问题的规模越小，解题所需的计算时间往往也越 者是为了描述某一问题的状态，必须用到它的上一状态，而描 少，从而也更加容易处理。但有时候要想直接解决一个较大的 述上一状态又必须用到它的再上一状态……这种用自己来定 问题，可能是比较困难的。分治法的设计思想是，将一个难以 义自己的方法，称之为递归或者递归定义。在程序设计中，函 直接解决的大问题，分割成一些规模较小的问题，分割出的各 数直接或间接调用自己，就称为递归调用。若调用自己，称之 个小问题与原问题类型相同但规模较小，这样便于各个处理， 为直接递归。若函数Ｐ调用函数ｑ，而ｑ又调用Ｐ，则称之为问接 分而治之。如果原问题可分割成ｋ个子问题，ｌ＜ｋ≤ｎ，且这些 递归。要使用递归技术编程，首先要确定求解问题的递归模 子问题都可解，并可以利用这些子问题的解求出原问题的解， 型，然后再转换成对应的用某种语言编写的函数或过程。递归 那么这种分治法就是可行的。由分治法产生的子问题往往是 模型反映了一个递归问题的递归结构。 原问题的较小模式，这就为使用递归技术提供了方便。 以Ｆｉｂｏｎａｃｃｉ数列为例，它可以递归定义为： １问题的提出 ｌ ｉｆ ｎ＝０ 在实际问题中我们经常会遇到这样的情况，即要求排序的 Ｆ（ｎ）＝ ｌ 记录的关键字数量相对于记录数来说是较少的。例如，要对某 Ｆ（ｎ一１）＋Ｆ（ｎ一２） ｉｆ ｎ＞ｌ 次考试的考生按考试成绩排名，考试成绩按百分制，参加考试 Ｆ（Ｏ） 和Ｆ（１）＝１给出了递归的终止条件，我们称为递归出 的考生可能有几百人甚至上千人或更多，这种情况下记录关键 口；Ｆ（ｎ）＝Ｆ（ｎ—１）＋Ｆ（ｎ一２）给出了ＦＣｎ）与其前两项的关系，我们称 字的数量相对于记录数来说就非常有限。对于这种具有特殊 之为递归体。一般地，一个递归模型是由递归出口和递归体两 性质的记录进行排序，用原有的一些经典的排序算法实现效率 部分构成的，前者确定递归到何时结束，后者确定递归的方 不一定高。对一些特殊问题的处理我们可以在经典排序算法 式。递归设计是把一个不能或不好直接求解的“大问题”转化 的基础上进行改进并实现。 为一个或几个“小问题”，再把这些“小问题”进一步分解为更小 的“小问题”来解决，即通过分解使问题的规模逐渐降低，直至 ２算法分析 每个小问题都可以直接解决（此时分解到递归出口）。当然，递 考虑到关键字的数量较少，而记录数较多的特殊情况，如 收稿日期：２０１卜１Ｏ一２Ｏ 作者简介：孙义欣（１９６８一），男，山东寿光人，教师，硕士，主要研究方向：最优化理论，算法设计与分析。 ・ ２８ ・ Ｃｏｍｐｕｔｅｒ Ｅｒａ Ｎｏ．１ ２０１２ 果我们在排序交换时尽可能地做到使两条记录同时到位，则交 换次数肯定会减少。 用ｂａｃｋＭｉｎ来记录该位置，其初始值为ｈｉｇｈ； ｉｆ ａ［ｆｒｏｎｔＭａｘ］＞ａ［ｂａｃｋＭｉｎ】ｔｈｅｎ ｛ａ［ｆｏｎｒｔＭａｘ】Ｈ ａ［ＢａｃｋＭｉｎ］； ｅｘｃｈａｎｇｅＮｕｍ ｅｘｃｈａｎｇｅＮｕｍ＋ｌ： 若要将序列排成非递减序列，关键字小的记录则最终应该 处在序列的前半部分，而关键字大的记录最终应该处在序列的 后半部分。我们先对待排序序列处理一遍，将整个序列分成两 部分，即关键字小的记录都在第一部分中，关键字大的记录都 在第二部分中，即将原序列分为两个较小的序列。这样，原序 列经过分治处理后就变成了两个相似序列，而两个序列的规模 都变小了，这一就可以对前后两部分进行递归处理。 一） Ｉｆ没有交换ｔｈｅｎ ｛Ｉ１￣＇１在数组的前半部分和后半部分中进行递归处理； ｅ×ｃｈａｎｇｅＮｕｍ＋＝前半部分的处理所需的交换次数＋后半部 分的处理所需的交换次数： ） ） ｅｌｓｅ 为此，我们可以按如下方法进行排序：假设ａ［１ｏｗ…ｈｉｇｈ］是 维数组，让变量ｍｉｄ＝（１ｏｗ＋ｈｉｇｈ）／２；指针ｉ、ｊ作为控制搜索的 变量，指针ｉ用来在记录的前半部分搜索，指针Ｊ用来在记录的 ｛ ／／数组中的元素个数等于２ ｉｆ（ａ【ｌｏｗ】＞ａ【ｈｉｇｈ】）ｔｈｅｎ （ａ［Ｉｏｗ】一） ） ａ［ｈｉｇｈ］； ｅｘｃｈａｎｇｅＮｕｍ＋＋； 后半部分搜索；指针ｆｒｏｎｔＭａｘ用来记录数组前半部分中关键字 值最大的位置，每次搜索其初始值都为ｌｏｗ，指向第一个记录位 置；指针ｂａｃｋＭｉｎ用来记录数组后半部分中关键字值最小的位 置，每次搜索时其初始值都为ｈｉｇｈ，指向最后一个记录的位置； 为了考查算法的效率，我们设置了变量ｅｘｃｈａｎｇｅＮｕｍ用来记录 发生交换的次数，其初始值为０。 排序的具体过程为：首先从序列的开始（第ｌｏｗ条记录）在 序列的前半部分搜索关键字值最大的记录，用变量ｆｒｏｎｔＭａｘ来 记录在前半部分中找到的关键字值最大的位置；从序列的最后 ｒｅｔｕｍ ｅｘｃｈａｎｇｅＮｕｍ；／，将交换次数返回 该方法操作示意图如下： ① ｆｒｏｎｔＭａｘ ｂａｃ 开始（第ｈｉｇｈ条记录）在序列的后半部分中搜索关键字值最小 ９ｏ ｌ ７５ ｌ ９０ ｌ ６ｏ ｌ ７５ ｌ ７５ ｌ ６０ ｌ ９ｏ ｌ ６０ ｌ砷 的记录，用变量ｂａｃｋＭｉｎ记录在序列后半部分中找到的关键字 值最小的位置。搜索完一遍后用ｆ￣ｏｎｔＭ＝指示的记录的关键 ｆｒｏｎｔＭ￣ ③ ② ｌ ｂａｃｋＭｉｎ ｂａｃｋＭｉｎ ｛ｆｒｏｎｔＭａｘ 字值ａ［ｆｒｏｎｔＭａｘ］和ｂａｃｋＭｉｎ指示的记录的关键字值ａ［ｂａｃｋＭｉｎ】 记录都不在正确的位置上，则这两个位置的记录要做一次交 示意图的序列上经过①、②、③步的交换之后，序列变成了 ６０ Ｉ ６０ ｌ ６０ ｌ ６０ ｌ ７５ Ｉ ７５ Ｉ ７５【９０｛９０ ｊ ９０ 进行比较，若ａ［ｆｒｏｎｔＭａｘ】＞ａ［ｂａｃｋＭｉｎ］，说明这两个位置上的 下面的情况：换，同时将交换次数ｅｘｃｈａｎｇｅＮｕｍ增加ｌ。由于序列关键字的 在本例中，我们发现只经过了三次交换序列就已经变成了 而交换次数比使用选择法排序少一次。如果待排 数量是有限的，这样进行一次交换就有可能使两条记录同时到 非递减排序，位，从而可以有效地减少记录交换的次数；若在搜索完成后没 序的数据比较多，或者数据的原始位置不和上面所举例子一 则很可能经过第一遍的操作之后整个序列还没有完全达到 有发生交换，说明前半部分中所有记录的关键字值都不大于后 样，那么就可以采取分治策略，将整个数组分为前后两部分， 半部分中所有记录的关键字值，则结束本次搜索过程。然后将 要求，整个序列分为前后两个部分ａ［１ｏｗ…ｍｉｄ］和ａ［ｍｉｄ＋１．一ｈｉｇｈ］，即 然后在两部分中分别实施上述过程，即进行递归处理。 采取分治策略，在这两个部分中再分别执行上述过程，也就是 ４与使用选择法排序的比较 对两部分分别进行递归调用，而交换次数也相应的为 下面给出使用本算法和使用选择法进行处理的几组对照 ｅｘｃｈａｎｇｅＮｕｍ＝ｅｘｃｈａｎｇｅＮｕｍ＋前半部分交换的次数＋后半部分 交换的次数。 数据，从中可以看出，在任何情况下使用本算法排序在交换次 数上都少于或等于使用选择法排序所需的交换次数。 最好情况是数据本身就有序的情况，这时两种方法的交换 次数都是０。 ３算法实现 我们给出实现上述过程的算法如下： 第一组：最差情况，所有数据都不在正确位置上。 ９０ ９０ ７５ ６０ ６０ ９０ ６０ ７５ ７５ ７５ 输出：按非降序排列的数组ａ［０．．ｎ一１］，排序需要的元素交 初始数据：用选择法的交换次数：７；使用本算法的交换次数：６。 换次数ｅｘｃｈａｎｇｅＮｕｍ。 ｅｘｃｈａｎｇｅＮｕｍ＝０； ／／初始交换次数为０ 输入：ｎ个元素的数组ａ［Ｏ．．１１—１】。 第二组：随机情况。 初始数据：６０ ９０ ６０ ７５ ９０ ９０ ７５ ６０ ６０ ７５ 用选择法的交换次数：６；使用本算法的交换次数：４。 第三组：随机Ｉ青况。 初始数据：９０ ７５ ６０ ７５ ７５ ９０ ６０ ７５ ９０ ６０ （下转第３０页） ｉｆ数组中的元素个数大于两个ｔｈｅｎ ｛ ｍｉｄ＝（Ｉｏｗ＋ｈｉｇｈ），２： ／／ｍｉｄ为中间元素的位置 ｗｈｉｌｅ（记录还没有搜索完成） ｆ在数组的前半部分搜索关键字值最大的记录位置； 用ｆｒｏｎｔＭａｘ来记录该位置，其初始值为ｌｏｗ； 在数组的后半部分中搜索关键字值最小的记录位置； ・ ３０ ・ Ｃｏｍｐｕｔｅｒ Ｅｒａ Ｎｏ．１ ２０１２ 绘制图形时，特别要注意Ｘ、Ｙ的长度需一致。所绘折线功 定义北向或其他角度为０度，可以通过图片窗口的工具栏的 如图ｌ所示。通过图形也可看出：ＭＡＴＬＡＢ默认的极坐标的显 Ｒｏｔａｔｅ对图１进行旋转，旋转成用户所需要的结果。这样做的 不精确，甚至有可能雷达图给转成 示格式是每隔３０度显示一条径向线，并进行角度标注。如果不 缺点是有可能会存在误差，能自定义径向线的角度和名称标注，将不能借此表达雷达图的 椭圆状。为此可以使用视角函数ｖｉｅｗ（ｘ，Ｙ），其中参数ｘ，Ｙ用度 多元参数信息。 数表示，这样，改变一下用户的视角就可能得到想要的任何角 若要对参数进行修改，就要修改ＭＡＴＬＡＢ的系统函数 度。图ｌ生成的默认视角为ｖｉｅｗ（０，９０）。如设置为ｖｉｅｗ ｐｏｌａｒ（极坐标绘制函数）。为避免发生意外错误，建议对该系统 函数ｐｏｌｒ进行复制修改，ａ如复制再生成—个系统函数ｍｙｐｏｌａｒ。 在ｍａｔｌａｂ命令窗口键入： ＞＞ｅｄｉｔ ｍｙｐｏｌａｒ ｍ （０，一９０），则以顺时针方向为正方向；如设置为ｖｉｅｗ（９０，一９０）， 则可以将北向改为０度。 通过视角函数ｖｉｅｗ对雷达图的方向进行设置，明显比通过 手２１２Ｒｏｔａｔｅ调节更为方便。 ２．４其他修改 ２．１绘制径向线 进．ｋ．ｍｙｐｏｌａｒ函数，找￣ｌＪ％ｐｌｏｔ ｓｐｏｋｅｓ（绘制径向线）： ｔｈ＝（１：６） ２ ｐｉｌｌ ２： ｃｓｔ＝ｃｏｓ（ｔｈ）；ｓｎｔ＝ｓｉｎ（ｔｈ）； ＣＳ＝【一ｃｓｔ；ｃｓｔ］； 除上述修改外，还可以对雷达图进行其他设置，如：标题位 置，标注大小，线的宽细…… 线宽修改示例：ｓｅｔ（ｆｉｎｄｏｂｊ（ｇｅｔ（ｇｃａ，’Ｃｈｉｌｄｒｅｎ’）， ＬｉｎｅＷｉｄｔｈ’， ０．５），’ＬｉｎｅＷｉｄｔｈ’，２）； ｓｎ＝【－ｓｎｔ；ｓｎｔ］； ｌｉｎｅ（ｒｍａｘ ＣＳ，ｒｍａｘ ＳＲ，’ｌｉｎｅｓｔｙｌｅ。，Ｉｓ，’ｃｏｌｏｒ’，ｔｃ，‘ｌｉｎｅｗｉｄｔｈ。，１，… ’ｈａｎｄｌｅｖｉｓｉｂｉｌｉｔｙ＇，’ｏｆｆ＇，’ｐａｒｅｎｔ’，ｃａｘ） 在多图显示时，如用ｓｕｂｐｌｏｔ（ｍ，ｎ，ｐ）在一个窗Ｅｌ生成多个雷 达图时，可通过ｐｏｓｉｔｉｏｎ对每个子图的大小、位置进行设置，使 整体的图片布局更为合理。 程序中ｔｈ表示两条径向线以３０度为间隔，只要对其进行修 改即可自定义分配径向线的个数与夹角。如修改为ｔｈ＝（１：８） ３结束语 ＂２＂ｐｉ／１６，则圆上分布ｌ６条径向射线，间隔为２２．５度。然后，要 本文的研究表明，用ＭＡＴＬＡＢ绘制雷达图比用ＥＸＣＥＬ可 对程序中随后出现的夹角参数进行相应修改（３０改为２２．５）。 塑性更强。在ＭＡＴＬＡＢ中通过修改系统函数ｐｏｌｒ，然后运用 ａ２．２径向线标注的修改 新的ｐｏｌａｒ函数绘制雷达图，再运用函数ｖｉｅｗ、函数ｐｏｓｉｔｉｏｎ， 我们不仅需要修改径向线的个数与夹角，还要修改其标 以及修改其他的属性参数，这样得到的雷达图更能满足用户 注，将角度标注修改为用户所需要的雷达图（比如：方向Ｅ、ｗ、 的需求。 Ｓ、Ｎ等）。 ＭＡＴＬＡＢ的绘图功能是非常强大的，我们希望在今后的 修改仍需要在ｐｏｌｒ．ａｍ中进行。 ％ａｎｎｏｔａｔｅ ｓｐｏｋｅｓ ｉｎ ｄｅｇｒｅｅｓ（标注） ｒｔ＝１．１ ｒｍａｘ； 使用和学习过程中，能够挖掘出更多实用的技巧。 参考文献： 【１】东方人毕．Ｏｆｆｉｃｅ２０００中文版入门和提高【Ｍ】．清华大学出版社， ２００４． ｆｏｒ ｉ＝１：ｌｅｎｇｔｈ（ｔｈ１ ｔｅｘｔ（ｒｔ ｃｓｔ（ｉ），ｒｔ ｓｎｔ（ｉ），ｉｎｔ２ｓｔｒ（ｉ ２２．５），…％ｉｎｔ２ｓｔｒ（ｉ ２２．５）是关键 ｈＯｒｉｚ０ｎｔａＩａＩｉｇｎｍｅｎｔ＇，＇ｃｅｎｔｅｒ。．．．． 【２】清源计算机工作室，ＭＡＴＬＡＢ６．０基础反应用【Ｍ】．机械工业出版社， ２００１． ｈａｎｄｌｅｖｉｓｉｂｉｌｉｔｙ＇，＇ｏｆｆ＇，’ｐａｒｅｎｔ‘，ｃａｘ）； 【３ｌ徐东艳．孟晓刚．ＭＡＴＬＡＢ函数库查询辞典【Ｍ】．中国铁道出版社， ２００６． 程序中ｔｅｘｔ表示在某个指定的位置（ｒｔ＊ｃｓｔ（ｉ），ｒｔ＊ｓｎｔ（ｉ））进行 标注，也可以自行定义字符向量对其进行替换即可。 【４】张威．ＭＡＴＬＡＢ基础与编程入门【Ｍ】．西安电子科技大学出版社， ２．３方向的修改 ２００４． ５】刘卫国．ＭＡＴＬＡＢ程序设计教程【Ｍ】．水利水电出版社，２００５． 从图１可见，该图的０度从东向（ｘ轴的正向）开始，且以逆 【时针方向为正方向。为了将方向修改为以顺时针为正向，以及 （上接第２８页） 用选择法的交换次数：５；使用本算法的交换次数：３。 第四组：随机情况。 初始数据：７５ ６０ ９０ ９０ ７５ ７５ ６Ｏ ６０ ７５ ６０ 文提出的问题而言，使用该算法实现交换次数确实少了很多， 因而也说明该算法是有效的。 参考文献： 【１】严蔚敏，吴伟民．教据结构（Ｃ语言版）【Ｍ】．清卑大学出版社，１９９７． 用选择法的交换次数：５；使用本算法的交换次数：４。 第五组：随机情况 初始数据：７５ ７５ ９０ ９Ｏ ６０ ７５ ９０ ６０ ６０ ７５ 用选择法的交换次数：７；使用本算法的交换次数：５。 【２】Ｍ．Ｈ．Ａｌｓｕｗａｉｙｅｌ著，吴伟，方世昌等译算法设计技巧与分析【Ｍ】．电子 工业出版社．２００４． 【３】李春葆，数据结构习题与解析【Ｍ】．（第二版）清华太学出版社，２００５． 【４】王晓东，计算机算法设计与分析【Ｍ】．（第２版）电子工业出版社 ２００６． ５结束语 通过该算法和选择排序算法的对照，我们可以看出，就本
