logo资料库

各种排序算法的策略模式实现.docx

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：0.95M 资料格式：docx 举报 版权申诉
第1页 / 共23页
第2页 / 共23页
第3页 / 共23页
第4页 / 共23页
第5页 / 共23页
第6页 / 共23页
第7页 / 共23页
第8页 / 共23页
资料共23页，剩余部分请下载后查看
    1 引言
    2 策略模式
    2.1 策略模式概述
    2.2 问题
    2.3 解决方案
    2.4 策略模式适用性
    2.5 策略模式结构
    2.6 策略模式组成
    2.8 策略模式缺点
    3 冒泡、快速、归并三种排序算法分析比较
    3.1冒泡排序（Bubble Sort）
    3.2快速排序（Quick Sort）
    3.3 归并排序（Merge Sort）
    4 基于策略模式的排序算法切换UML类图
    5 基于策略模式的排序算法代码实现及结果
    5.1代码结构
    5.2 运行结果
    5.2.1手动输入
    5.2.2选择文件
    6 结束语
    参考文献
    策略模式实现冒泡、快排、归并三种算 法，并比较其排序时间
    摘 要 对于算法，我们现在不仅只是注重算法功能的实现，而越来越看重算法的时 间复杂度，空间复杂度，健壮性，低耦合高内聚等性质。通常我们认为算法是指 解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系 统的方法描述解决问题的策略机制。设计模式是一套被反复使用、多数人知晓的、 经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代 码更容易被他人理解、保证代码可靠性。但是他们都是旨在对于一个问题最优的 解决方案。不同的只是不在一个层面上。算法更具体一些，而设计模式则比较关 注大局。本论文将算法和设计模式中的策略模式结合，实现冒泡、快速、归并三 种排序算法的切换，并比较其排序时间，使得算法的时间复杂度更低，效率更高， 同时提高了代码的可移植性，灵活性。 关键词 策略模式 冒泡 快速 归并 时间复杂度
    just the algorithm,we can not Abstract: For focus on achieving arithmetic functions,and increasingly value the time complexity of the algorithm, space complexity,robustness, low coupling and high cohesion and more.Usually we think algorithm means that accurate and complete description of the program and a series of clear instructions to solve the problem, the algorithm represents a systematic approach to problem-solving strategies describe mechanisms.Design patterns are a set of experience of code designing to be used repeatedly,most people know , after cataloging.Use of design patterns is to reuse code, ensure the reliability of the code and make the code easier to understood .But they are all aimed at a perfect solution of problems, just in different levels .Algorithm is more specific, and design patterns are more concerned about the overall situation.In this paper, algorithms and strategy pattern which is a kind of design patterns are combined to achieve bubble sort, fast sort and merge sort three sorting algorithms,and compare their sorting time .so algorithm can be less time complexity ,more efficient. At the same time,the portability and flexibility of code can be improved. Keywords: strategyPattern bubble quick merge timeComplexity
    目 录 1 引言........................................................................................................................... 1 2 策略模式................................................................................................................... 1 2.1 策略模式概述................................................................................................ 1 2.2 问题................................................................................................................ 2 2.3 解决方案........................................................................................................ 2 2.4 策略模式适用性............................................................................................ 3 2.5 策略模式结构................................................................................................ 3 2.6 策略模式组成................................................................................................ 4 2.8 策略模式缺点................................................................................................ 4 3 冒泡、快速、归并三种排序算法分析比较........................................................... 5 3.1 冒泡排序（Bubble Sort）........................................................................... 5 3.2 快速排序（Quick Sort）............................................................................. 6 3.3 归并排序（Merge Sort）.............................................................................. 9 4 基于策略模式的排序算法切换 UML 类图............................................................. 11 5 基于策略模式的排序算法代码实现及结果......................................................... 12 5.1 代码结构....................................................................................................... 12 5.2 运行结果...................................................................................................... 13 5.2.1 手动输入............................................................................................ 13 5.2.2 选择文件............................................................................................ 16 6 结束语..................................................................................................................... 17 参考文献..................................................................................................................... 18
    武汉理工大学研究生《算法分析与理论》课程论文 1 引言 设计模式是可复用面向对象软件的基础，设计模式提供了观察分析和设计的更 高视角使用设计模式可以更加方便地构建软件的体系结构。提高软件的可扩展性、 可靠性和灵活性。 策略模式属于对象行为型模式，主要针对一组算法，将每一个算法封装到具有共同接口的 独立的类中，从而使得它们可以相互替换。策略模式使得算法可以在不影响 到客户端的情 况下发生变化。通常，策略模式适用于当一个应用程序需要实现一种特定的服务或者功能， 而且该程序有多种实现方式时使用。 排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元 素（或记录）的任意序列，重新排列成一个关键字有序的序列。冒泡排序，快速 排序，归并排序是比较常见的三种排序，时间复杂度也各不相同。 2 策略模式 2.1 策略模式概述 在软件开发中也常常遇到类似的情况，实现某一个功能有多种算法或者策 略，我们可以根据环境或者条件的不同选择不同的算法或者策略来完成该功能。 如查找、排序等，一种常用的方法是硬编码(Hard Coding)在一个类中，如需要提 供多种查找算法，可以将这些算法写到一个类中，在该类中提供多个方法，每一 个方法对应一个具体的查找算法；当然也可以将这些查找算法封装在一个统一的 方法中，通过 if…else…或者 case 等条件判断语句来进行选择。这两种实现方法 我们都可以称之为硬编码，如果需要增加一种新的查找算法，需要修改封装算法 类的源代码；更换查找算法，也需要修改客户端调用代码。在这个算法类中封装 了大量查找算法，该类代码将较复杂，维护较为困难。如果我们将这些策略包含 1
    武汉理工大学研究生《算法分析与理论》课程论文 在客户端，这种做法更不可取，将导致客户端程序庞大而且难以维护，如果存在 大量可供选择的算法时问题将变得更加严重。 2.2 问题 以出门旅游为例：我们可以有几个策略可以考虑：可以骑自行车，汽车，做火 车，飞机。每个策略都可以得到相同的结果，但是它们使用了不同的资源。选择 策略的依据是费用，时间，使用工具还有每种方式的方便程度 。 图 2.1 策略模式旅游出行例子 那么问题来了：如何让算法和对象分开来，使得算法可以独立于使用它的客户而 变化？ 2.3 解决方案 策略模式(Strategy 模式）：定义一系列的算法,把每一个算法封装起来, 并且 使它们可相互替换。本模式使得算法可独立于使用它的客户而变化。也称为政策 模式(Policy)。（Definea family of algorithms,encapsulate each one, andmake them interchangeable. Strategy lets the algorithmvary independently from clients that use it. ） 策略模式把对象本身和运算规则区分开来，其功能非常强大，因为这个设计 模式本身的核心思想就是面向对象编程的多形性的思想。 2
    武汉理工大学研究生《算法分析与理论》课程论文 2.4 策略模式适用性 当存在以下情况时使用 Strategy 模式 (1) 许多相关的类仅仅是行为有异。“策略”提供了一种用多个行为中的一个行为 来配置一个类的方法。即一个系统需要动态地在几种算法中选择一种。 (2) 需要使用一个算法的不同变体。例如，你可能会定义一些反映不同的空间 / 时间权衡的算法。当这些变体实现为一个算法的类层次时 ,可以使用策略模式。 (3) 算法使用客户不应该知道的数据。可使用策略模式以避免暴露复杂的、与算 法相关的数据结构。 (4) 一个类定义了多种行为 , 并且这些行为在这个类的操作中以多个条件语句 的形式出现。将相关的条件分支移入它们各自的 Strategy 类中以代替这些条件语 句。 2.5 策略模式结构 图 2.2 策略模式结构图 3
    武汉理工大学研究生《算法分析与理论》课程论文 2.6 策略模式组成 (1) 环境类(Context):用一个 ConcreteStrategy 对象来配置。维护一个对 Strategy 对象的引用。可定义一个接口来让 Strategy 访问它的数据。 (2) 抽象策略类(Strategy):定义所有支持的算法的公共接口。 Context 使用这个 接口来调用某 ConcreteStrategy 定义的算法。 (3) 具体策略类(ConcreteStrategy):以 Strategy 接口实现某具体算法。 2.7 策略模式优点 （1） 相关算法系列 Strategy 类层次为 Context 定义了一系列的可供重用的算法 或行为。 继承有助于析取出这些算法中的公共功能。 （2） 提供了可以替换继承关系的办法： 继承提供了另一种支持多种算法或行 为的方法。你可以直接生成一个 Context 类的子类，从而给它以不同的行为。但 这会将行为硬行编制到 Context 中，而将算法的实现与 Context 的实现混合起来, 从而使 Context 难以理解、难以维护和难以扩展，而且还不能动态地改变算法。 最后你得到一堆相关的类 , 它们之间的唯一差别是它们所使用的算法或行为。 将算法封装在独立的 Strategy 类中使得你可以独立于其 Context 改变它，使它易 于切换、易于理解、易于扩展。 （3）消除了一些 if else 条件语句 ：Strategy 模式提供了用条件语句选择所需的 行为以外的另一种选择。当不同的行为堆砌在一个类中时 ,很难避免使用条件语 句来选择合适的行为。将行为封装在一个个独立的 Strategy 类中消除了这些条件 语句。含有许多条件语句的代码通常意味着需要使用 Strategy 模式。 （4） 实现的选择 Strategy 模式可以提供相同行为的不同实现。客户可以根据不 同时间/空间权衡取舍要求从不同策略中进行选择。 2.8 策略模式缺点 (1) 客户端必须知道所有的策略类，并自行决定使用哪一个策略类: 本模式有一 个潜在的缺点，就是一个客户要选择一个合适的 Strategy 就必须知道这些 Strategy 4
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料