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

《基于分治和递归策略的排序算法及实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于分治和递归策略的排序算法及实现孙义欣(潍坊工程职业学院继续教育学院，山东青州262500)摘要：对关键字数量远少于记录数量的排序问题进行了研究，提出了基于分治和递归策略的有效算法。经与选择排序算法比较，该算法在各种情况下的交换次数均明显少于经典的选择排序算法。关键词：排序；关键字；分治；递归中图分类号：TP312文献标志码：A文章编号：1006-8228（2012）01-27-02Sortingalgorithmbasedondivide-and-conquerstrategyandrecursivestrategyanditsrealization

2、SunYixin（CollegeofFurtherEducation,WeifangEngineeringVocationalCollege,Qingzhou,Shandong262500,China）Abstract：Thesortingproblemforthenumberofkeywordsfarlessthanthatofrecordsisresearched,andaneffectivealgorithmbasedondivide-and-conquerandrecursivestrategiesisputforward.Comparedwit

3、hselectionsortingalgorithm,theexchangingfrequencyofthisalgorithmisobviouslylessthanthatofclassicselectionsortingalgorithmundervariouscircumstances.Keywords：sorting；keyword；divideandconquer；recursion0引言递归技术经常用在算法设计之中，并由此产生许多结构清晰、可读性强的算法。一个函数、过程、概念或数据结构，如果在其定义内部或说明内部直接或间接地出现其自身的引用，

4、或者是为了描述某一问题的状态，必须用到它的上一状态，而描述上一状态又必须用到它的再上一状态……这种用自己来定义自己的方法，称之为递归或者递归定义。在程序设计中，函数直接或间接调用自己，就称为递归调用。若调用自己，称之为直接递归。若函数p调用函数q，而q又调用p，则称之为间接递归。要使用递归技术编程，首先要确定求解问题的递归模型，然后再转换成对应的用某种语言编写的函数或过程。递归模型反映了一个递归问题的递归结构。以Fibonacci数列为例，它可以递归定义为：归分解不是随意地分解，递归分解要保证“大问题”与“小问题”规模不同但模型相似。任何一个可以用计算机

5、求解的问题所需的求解时间都与其规模有关。问题的规模越小，解题所需的计算时间往往也越少，从而也更加容易处理。但有时候要想直接解决一个较大的问题，可能是比较困难的。分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的问题，分割出的各个小问题与原问题类型相同但规模较小，这样便于各个处理，分而治之。如果原问题可分割成k个子问题，1

6、即要求排序的记录的关键字数量相对于记录数来说是较少的。例如，要对某次考试的考生按考试成绩排名，考试成绩按百分制，参加考试的考生可能有几百人甚至上千人或更多，这种情况下记录关键字的数量相对于记录数来说就非常有限。对于这种具有特殊性质的记录进行排序，用原有的一些经典的排序算法实现效率不一定高。对一些特殊问题的处理我们可以在经典排序算法的基础上进行改进并实现。2算法分析考虑到关键字的数量较少，而记录数较多的特殊情况，如1ifn=0F(n)=F(n-1)+F(n-2)ifn>1F(0)=1和F(1)=1给出了递归的终止条件，我们称为递归出口；F(n)=F(n-1

7、)+F(n-2)给出了F(n)与其前两项的关系，我们称之为递归体。一般地，一个递归模型是由递归出口和递归体两部分构成的，前者确定递归到何时结束，后者确定递归的方式。递归设计是把一个不能或不好直接求解的“大问题”转化为一个或几个“小问题”，再把这些“小问题”进一步分解为更小的“小问题”来解决，即通过分解使问题的规模逐渐降低，直至每个小问题都可以直接解决（此时分解到递归出口）。当然，递收稿日期：2011-10-20作者简介：孙义欣（1968-），男，山东寿光人，教师，硕士，主要研究方向：最优化理论，算法设计与分析。用backMin来记录该位置，其初始值为hi

8、gh；ifa[frontMax]>a[backMin]then{a[fonrtM