合并排序算法论文

《合并排序算法论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、合并排序算法研究1(1•河南大学计算机与信息工程学院，河南开封475004)摘要：分治法是一种非常重耍的解题方法，K基本思想是将•-个规模为N的问题分解为K个规模较小的子问题，这些子问题互相独立且与原问题相同，递归的了解这些子问题，然后将各子问题的解合并得到原问题的解。合丼排序算法即站运川分治策略来实现对N个元索进行排序的算法。文章论述的日的足逑立迕分治法的基础上，采川递归，非递归和自然合并排序三种方法來实现的合并排序算法，同时通过三种方法的时间复杂度和空间复杂度对三种力法的计算过程进行深入的探讨和研究，在仔细分析三种算法的优点和缺点并进

2、行比较之后，最终得出对于所给的n元素数组己排序好序的极端情况，采用H然合并排序77法实现的合并排序算法明显优于非递归和递归77法实现的合并排序算法，因为它的合并过程中所需的合并次数较少时间复杂度最低。关键词：合并排序：递归；分治法；非递归ResearchonmergesortalgorithmDUANXiao-yu1"(CollegeofComputerScienceandInformationEngineering,HenanUniversity，Kaifeng475004,China)Abstract:Themethodisavery

3、importantproblemsolvingmethod，thebasicideaistobeaproblemofsizeNKisdecomposedintosmallersubproblems，theseproblemsareindependentofeachotherandwiththesameproblem，recursiveunderstandingoftheseproblems，andthencombinetheirsolutionstosolvetheoriginalthesolutionoftheproblem.Merge

4、sortalgorithmisusedtodivideandconquerstrategytoachievesortofNelementalgorithm.Thisarticleaimstoestablisharecursivedivideandconquerbasedonmergesortalgorithm,nonrecursivemergesortandnaturalthreewaystorealizethein-depthdiscussionandresearchcarriedoutatthesametimethroughtheth

5、reemethodsoftimeandspacecomplexityofthethreemethodsofthecalculationprocess，aftercarefulanalysisadvantagesanddisadvantagesofthesethreealgorithmswerecompared,obtainedfornelementstothearrayissortedbytheextremesituation,naturalmergesortmergesortalgorithmimplementationmethodis

6、obviouslybetterthanthemergesortalgorithmnonrecursiveandrecursivemethodtorealize，becausetherequiredinthecourseofitsmergerwithfewertheminiinumtimecomplexity.Keywords:mergesorl；Recursion：Divideandconquermethod：non-recursive0引言分治策略是一种在排序算法屮应川最多的方法之一，之前的研究当屮都是对合并排序进行递归和非递归的研究似

7、并未对A然合并排序进行详细的研究比较，本文的目的即对三种方法进行探W并通过时间£杂度和空间£杂度来比较并得出结论。1分治法概述1.1分治法的描述所谓分治法，是指对一个输人规模为n的问题，用某种可行的方法把输人分割成1个子^(l

8、方法，基木思路是：“如果一个人问题比较复杂，就可以将这个问题分解，然后各个击破。”分治从字面上包含了“分”和“治”两层含义，那么如何分，分后又如何“治”就成为我们解决问题的关键之处。通常并不是