多种排序算法动态演示软件的设计和开发

分类号 分类号 TP302 2TP302 2 U U D D C C D10621 408 2007 6181 0D10621 408 2007 6181 0 密密 级 公级 公 开开 编编 号 号 20028010062002801006 成成 都都 信信 息息 工工 程程 学学 院院 学学 位位 论论 文文 多种排序算法动态演示软件的设计与开发多种排序算法动态演示软件的设计与开发 论文作者姓名 论文作者姓名 张张 鹏鹏 申请学位专业 申请学位专业 网网 络络 工工 程程 申请学位类别 申请学位类别 工工 学学 学学 士士 指指导导教教师师姓姓名名 职职称称 郭郭 涛 讲师 涛 讲师 论文提交日期 论文提交日期 20072007 年年 0606 月月 1 1 日日 多种排序算法动态演示软件的设计与开发多种排序算法动态演示软件的设计与开发 摘摘 要要 随着计算机科学技术的不断提高和发展 其强大的运算功能已经逐渐融入 人类社会的各个领域 并且在各个领域中发挥越来越重要的作用 当然 高效 的运算速度并不代表无限快 在有限的资源空间里 要大大提高运算处理数据 的速率 就需要我们使用那些在时间和空间上体现出高效的算法 本系统是为 了演示在同一问题上 不同的算法在效率上存在的巨大差异 本系统采用 Visual C 6 0 中文版为开发工具 实现三种不同排序算法 即 冒泡排序算 法 选择排序算法和快速排序算法 以及这三种排序对同一问题的处理并且以 图形的形式给出快慢比较 实现排序算法的动态演示 其目的是为了让我们在 使用计算机处理规模越来越大的数据问题上 能够清楚什么样的算法适合当前 的处理系统 关键词关键词 Visual C 排序算法 动态演示 The Design and Development of Dynamic Sorting Algorithm Demo Abstract With computer science and technology improvement and development its powerful computing has gradually integrate into human society in various fields and play an increasingly important role Of course efficient computational speed does not mean unlimited fast and the limited resources of space Operators must significantly improve processing speed we need to use the time and space reflects efficient algorithms The system is to demonstrate on the same issues in different algorithm efficiency in the enormous difference The system uses Visual C 6 0 for the development of the Chinese version of tools to achieve three different sorting algorithms namely The Bubble Sorting Algorithm The Select Sorting Algorithm and The Quick Sorting Algorithm and three ranking on the same issue to deal with and the graphics are presented in the form of speed Sorting Algorithm to achieve the dynamic presentation Its purpose is that enable us to use computers to handle the increasingly large scale data problems to know what kind of algorithm is suitable for the current system Key words Visual C Sorting Algorithm Dynamic Demonstration 目录目录 论文总页数 21 页 1引言 1 1 1系统背景 1 1 2系统开发的意义 1 1 3系统开发的相关技术 1 1 4系统开发的相关概念 1 2系统需求及分析 2 2 1系统需求 2 2 2系统开发环境选择 2 2 3系统的总体规划 2 3系统设计思想 2 3 1冒泡算法及思想 2 3 2选择算法及思想 4 3 3快速算法及思想 5 4详细设计 8 4 1系统的文件的组织 8 4 2动态演示冒泡算法模块设计 8 4 3动态演示选择算法模块设计 11 4 4动态演示快速算法模块设计 13 4 5同时比较三种算法模块设计 16 4 6系统的测试 16 4 7系统的特点 18 结 论 19 参考文献 19 致 谢 20 声 明 21 第 1 页 共 21 页 1 1引言引言 1 11 1 系统背景系统背景 由于排序在计算机图形 计算机辅助设计 机器人 模式识别 基因排序 工程及统计学等领域具有广泛应用 所以对排序的研究既有理论上的重要意义 又有实际应用价值 再加上现在信息产业的迅速发展 信息的流通量越来越大 如此庞大并且杂乱无章的信息数据十分难以管理和查询 就更加需要一种十分 快捷而有效的编排手段来整理这些数据信息 让我们的工作效率得以提高 1 21 2 系统开发的意义系统开发的意义 在现代信息发达的今天 面对接受到大量的无序的信息 没有一个规则来 编排和查询 会给我们的工作和信息交流带来十分的不便 因此 利用计算机 的高速运用和计算能力 编写出一种合适的排序软件 能十分快捷的给我们在 信息交流和查询带来便利 例如在互联网上为了使人们能够快速的访问和检索 大量的信息 人们会运用许多快速并且优秀的算法对这些数据进行管理和操纵 优秀的算法还能帮助我们在互联网上快速找到最好的发送数据路线 以及怎么 用搜索引擎来快速地找到信息所在的页面 1 31 3 系统开发的相关技术系统开发的相关技术 本系统利用 Visual C 6 0 作为开发平台 利用它的可视化界面 在其 MFC 环境下开发的一个演示三种不同排序算法 利用画刷画出三种不同的排序 算法在排列随即产生的 0 70 个数的过程 并且能够对比这三种排序算法在相同 的条件下 排序速率的快慢 运用 VC 编程语言 把一个程序中的算法和程序框 架有效的结合起来 并且实现排序算法的动态演示 1 41 4 系统开发的相关概念系统开发的相关概念 首先我们要了解排序到底是什么 它的主要功能和目的是什么 简单的说 排序是利用一种算法 将一个无规则的序列排成一个有序序列的过程 而算法 则是以一组值或者一个值的集合作为输入 经过一系列计算得到的一组值作为 输出的过程 即是指那一系列将输入转化为输出的计算过程 排序的方法有很多种 但是没有一种排序算法是通用的 即在任何情况下 都能保持最快的排序速度 因此我们必须根据需要处理数据的特点来选择合适 的算法 在排序的过程中 我们一般需要用到的两个基本操作步骤是 比较两 个关键字的大小和将记录从一个位子移至另一个位子 即比较和交换 本系统 设定的情况为 记录关键字都为整数 排序的结果是从大到小的排列 用到的 三种排序算法为 冒泡排序法 选择排序法 快速排序法 第 2 页 共 21 页 2 2系统需求及分析系统需求及分析 2 12 1系统需求系统需求 本系统的硬件环境 CPU AMD 2800 内存 512M 以上 硬盘 80G 以上 本系统的软件环境 操作系统 Windows XP Visual C 6 0 中文版 2 22 2系统开发环境选择系统开发环境选择 本系统运用的是 Visual C 6 0 中文版 它是微软公司开发出的一种集成 开发环境 它拥有良好的可视化界面 它用来在 Windows 环境下开发应用程序 是一种功能强大 行之有效的可视化编程工具 在 Visual C 6 0 中能够进行 多种操作 它的特点就是能够把原来抽象的数字 表格 功能逻辑等用直观的 图形 图象的形式表现出来 排序算法本来就是一种抽象的逻辑功能 想要直 观的把它演示出来 选择利用 Visual C 6 0 的可视化编程是非常明智的 而 且本系统在开发过程中 能够用鼠标点击按钮和拖放图形化的对象 修改他们 的属性和行为过程 这种可视化的编程方法简单 易学 易用 可以大大提高 我们的工作效率 2 32 3系统的总体规划系统的总体规划 本系统的总体结构如图 2 1 所示 图 2 1 系统总体结构 3 3系统设计思想系统设计思想 3 13 1 冒泡算法及思想冒泡算法及思想 冒泡排序算法的基本思想 冒泡法的原理很简单 基本思想就是比较相临 的两个记录的关键字 若前者比后者小则交换 若前者比后者大则保持不变 先将第一个记录与第二个记录比较 然后是第二个与第三个比较 直到倒数第 二个与最后一个记录 比较一轮结束之后 关键字大的记录均向前移动 然后 开始新一轮的比较 知道一轮比较下来 不再有记录的交换发生为止 整个过 冒 泡 排 序 选 择 排 序 同 时 进 行 动态演示排序系统 快 速 排 序 第 3 页 共 21 页 程就有点象水中的气泡上升的过程 轻的往上浮 重的向下沉 这个算法的名 字也就由此得来 算法的步骤如下 1 假设要排序的数列为 A 1 A N 我们把相邻的两个数两两进行 比较 即把 A 1 和 A 2 比较 对比完后把 A 2 和 A 3 进行比较 直到 A N 1 和 A N 比较完为止 在相邻的两个数两两进行比较的过程中 如果前面 的一个数比后面一个数大 则把这两邻的两个数交换 也就是说 我们把较小 的数放在前面 把较大的数调到后面 即 如果在一次比较中 如果 A 1 比 A 2 大的情况下 把 A 1 和 A 2 交换 以此类推 直到一轮 A N 1 和 A N 比 较完 2 再次重复 1 直到相邻两数之间不再发生交换为止 例如 一组待排序数列为 685497 图 3 1 待排序组 根据算法思路 1 第一次对比后无变化 根据算法思路 1 第二次对比发生变化 由于 A 2 8 A 3 5 所以两 者交换 658497 图 3 2 第一次交换 根据算法思路 1 第三次对比发生变化 由于 A 3 8 A 4 4 所以两 者交换 654897 图 3 3 第二次交换 根据算法思路 1 第四次对比无变化 根据算法思路 1 第五次对比发生变化 由于 A 5 9 A 6 7 所有两 者交换 654879 图 3 4 第三次交换 第 4 页 共 21 页 到此第一轮的排序结束 根据算法思路 2 重新对以交换排列后的数列 进行排序直到没有变化为止 生成最后的序列 456789 图 3 5 最后有序序列 分析冒泡排序法的效率 若记录一开始就是从大到小排列 则一次循环就 能完成排序 若记录是 逆序 排列的 即是冲小到大的排列 则需 n 1 次循 环 n 为需要排序的记录总数 共 n n 1 2 次比较和交换 算法的负责度为 O n n 3 23 2 选择算法及思想选择算法及思想 选择排序算法的基本思想 每一趟 例如第 i 趟 i 0 1 n 2 在后面 n i 个待排序对象中选出关键码最小的对象 作为有序对象序列的第 i 个对象 待到第 n 2 趟作完 待排序对象只剩下 1 个 就不用再选了 我们选择一种把最小的数放在第一个位置上的选择排序算法 其思想是先 并不急于调换位置 先从第一个数开始逐个向后扫描整个序列 看哪个数最小 就记下该数所在的位置 等一趟扫描完毕 再把第一个数和在他后面最小对调 这时此无序序列中最小的数据就换到了最前面的位置 算法的步骤如下 1 先从 A 1 开始向后检查 检查出在 A 1 后面的最小数的位子 我 们设此位子为 A P 2 依次把 A P 和 A N A N 从 1 变化到 N 进行比较 每次比较时 若 A N 的数比 A P 中的数小 则把 N 的值赋给 P 使 P 总是指向当前所扫描过 的最小数的位置 也就是说 A P 总是等于所有扫描过的数最小的那个数 在依 次一一比较后 P 就指向 N 个数中最小的数所在位置 即 A P 就是 N 个数中最 小的那个数 3 把 A P 和 A 1 的数对调 那么最小的数就在 A 1 中去了 也就是 在最前面了 4 重复此算法 但每重复一次 进行比较的数列范围就向后移动一个 位置 即第二遍比较时范围就从第 2 个数一直到第 N 个数 在此范围内找最小 的数的位置 P 然后把 A P 与 A 2 对调 这样从第 2 个数开始到第 N 个数中最 小数就在 A 2 中了 第三遍就从第 3 个数到第 N 个数中去找最小的数 再把 A P 与 A 3 对调 此过程重复 N 1 次后 就把 A 数组中 N 个数按从小到大的 顺序排好了 例如 一组待排数据为 第 5 页 共 21 页 685497 图 3 6 待排序列 根据选择排序算法思路 1 从 A 1 6 向后检查 发现最小的数为 A 4 4 根据选择排序算法思路 2 把 A 1 和 A 4 进行比较 得出 A 1 6 A 4 4 所以把 A 4 和 A 1 对调 得到新的序列 485697 图 3 7 第一次交换 根据选择排序算法思路 3 即从 A 2 8 向后检查 从 A 3 A 6 从找到最小的数 A 3 5 把 A 2 8 和 A 3 5 进行比较 得出 A 2 8 A 3 5 所以把 A 2 和 A 3 对调 458697 图 3 8 第二次交换 重复选择排序算法思路 4 直到上面的排序工作不再有交换为止 得到 最后序列为 456 6 789 图 3 9 最终序列 分析选择排序算法效率 它实现的方式是 令 i 从 1 到 n 1 进行 n 1 次 选择操作 在选择排序算法的过程中 所需进行记录移动的造作次数比较少 但是 无论记录的初始排列如何 所需进行记录关键字间的比较次数均为 n n 1 2 因此选择排序算法的复杂度为 O n n 3 33 3 快速算法及思想快速算法及思想 快速排序算法的基本思想 采用分而治之的办法对一个表进行排序 任取 待排序对象序列中的某个对象 例如取第一个对象 作为基准 按照该对象的 不动 第 6 页 共 21 页 关键码大小 将整个对象序列划分为左右两个子表 low 和 high 1 左侧子序列 low 中所有对象的关键码都小于或等于基准对象的关键码 2 右侧子序列 high 中所有对象的关键码都大于或等于基准对象的关键 码 基准对象则排在这两个子序列中间 然后再按此方法对 low 和 high 两部分 数据分别进行快速排序 其整个过程可以递归进行 从而使整个数列变成有序 序列 假设要排序的数列为 A 1 A N 我们首先要取一个数据作为关键数据 一般情况下都是取第一个数据为关键数据 然后将所有小于它的数据放在它前 面 所有大于它的数放在它后面 这个过程就称为一趟快速排序 算法的步骤 如下 1 设置两个变量 int i j 在排序开始的时候 i 1 j N 2 以第一个数据为关键数据 定义为 key 即 key A 1 3 从变量 j 向前搜索 即由右至左的搜索 j j 1 找到小于 key 的 数据 两者交换 4 从变量 i 向后搜索 即由左至右的搜索 i i 1 找到大于 key 的 数据 两者交换 5 重复排序步骤 3 和 4 直到 i j 例如 一组待排序数据为 设初始关键数据 key 50 50396698761428 图 3 10 待排序列 根据步骤 3 进行第一次交换后 28396698761450 图 3 11 第一次交换 关键数据 key 50 和 28 发生交换 此时 j 6 根据步骤 4 进行第二次交换后 第 7 页 共 21 页 28395098761466 图 3 12 第二次交换 关键数据 key 50 和 66 发生交换 此时 i 4 根据步骤 5 将又一次执行算法 3 进行第三次交换 28391498765066 图 3 13 第三次交换 关键数据 key 50 和 14 发生交换 此时 j 5 根据步骤 5 又将执行一次算法 4 进行第四次交换 28391450769866 图 3 14 第四次交换 关键数据 key 50 和 98 发生交换 此时 i 5 此时我们可以看见 j i 所以此时结束此趟快速排序 在经过这趟快速排 序后的结果是 28391450769866 图 3 15 第五次交换 即所有大于初始关键数据 50 的数据全在其右边 所有小于初始关键数 据 50 的数据全部在其左边 以 50 为数轴 把原序列分成了两子序列 即 low 28 39 14 high 76 98 66 再递归的方法分别对前子表 low 和后 子表 high 进行类似的快速排序 从而完成所有数据序列的快速排序 最后把原 来这个无序的数据序列排列成为一组有序的序列 14283950667698 图 3 16 最终序列 分析快速排序算法的效率 如果每次划分对一个对象定位后 该对象的左 侧子序列与右侧子序列的长度相同 则下一步将是对两个长度减半的子序列进 第 8 页 共 21 页 行排序 这是最理想的情况 在 n 个元素的序列中 对一个对象定位所需时间 为 O n 若设 t n 是对 n 个元素的序列进行排序所需的时间 而且每次对 一个对象正确定位后 正好把序列划分为长度相等的两个子序列 此时 总的 计算时间为 T n cn 2 t n 2 c 是一个常数 Cn 2 cn 2 2t n 4 2cn 4t n 4 2cn 4 cn 4 2t n 8 3cn 8t n 8 Cn log2n nt 1 o n log2n 因此该算法的算法复杂度为 O n log2n 4 4详细设计详细设计 4 14 1 系统的文件的组织系统的文件的组织 本系统所含文件的组织如图 4 1 所示 创建视图框资源 添加新的菜单资源 创建视图框类 添加菜单响应函数 添加菜单中成员变量 源文件 添加全局指针 添加算法函数代码 修改构建函数实现演 示 头文件 添加定义常量 添加全局函数 4 24 2 动态演示冒泡算法模块设计动态演示冒泡算法模块设计 首先 本系统是在 Visual C 6 0 中文版下 MFC 环境下 设置的 MFC AppWizard exe 工程 工程名为 tt 相关的 ID 如表 4 1 4 2 所示 表 4 1 为工程添加 IDR MAINFRAME 的菜单选项 图 4 1 文件的组织 第 9 页 共 21 页 ID 说明文字功能描述 IDC SORT BUBBLE 冒泡法排序冒泡法排序 表 4 2 打开类向导 Class Wizard 对话框向视图类添加响应函数 Object IDMessages Messages 的描述函数名 IDC SORT BUBBLECOMMAND 选择该菜单 OnSortBubble 表 4 3 通过类查看 ClassView 选项卡 向视图类添加成员变量 变量类型变量名功能描述 intm SortBubble N 记录关键字 CRectm SortBubbleRect 动态演示矩形范围 BOOLIsSortBubble TRUE 表示进行冒泡排序 打开 ttView h 头文件 在文件开始部分定义两个常量 define N 70 设定排序的记录次数 define DELAY 3 每次交换操作所耗 define DELAY1 1 每次比较操作所耗的时间 并在其下声明冒泡排序的全局函数 UINT ThreadSortBubble LPVOID lp 由于开启多线程时 使用的都是全局函数 想要获得当前视图类中的数据 并实时更新试图的显示 就必须获取当前试图对象 所以本系统要定义一个全 局指针 打开 ttView cpp 构建函数中加入语句 CTtView pView 用来获取当 前视图 然后 系统在 ttView cpp 构建文件中添加实现冒泡排序算法的函数 ThreadSortBubble 代码为 UINT ThreadSortBubble LPVOID lp int data int i j key int tag data pView m SortBubble for i 0 ii j if data j data j 1 第 10 页 共 21 页 key data j data j data j 1 data j 1 key Sleep DELAY pView Invalidate TRUE tag Sleep DELAY1 if tag 0 break pView Invalidate TRUE return 0 在类中查看 Class View 选项 打开视图类 CTtView 在其中修改构 建函数 实现变量初始化 CTtView CTtView int i srand unsigned time NULL for i 0 i N i m SortBubble i 0 pView this IsSortBubble FALSE 为了让大家看清楚排序之间对比和交换的过程 修改响应函数 OnSortBubble 产生 0 70 随即整数来进行排序 void CTtView OnSortBubble for int i 0 iTextOut 250 200 冒泡排序演示 for i 0 iFillRect BlueBrush DeleteObject 4 34 3 动态演示选择算法模块设计动态演示选择算法模块设计 表 4 4 为工程添加 IDR MAINFRAME 的菜单选项 ID 说明文字功能描述 IDC SORT SELECT 选择法排序选择法排序 表 4 5 打开类向导 Class Wizard 对话框向视图类添加响应函数 Object IDMessages Messages 的描述函数名 IDC SORT SELECTCOMMAND 选择该菜单 OnSortSelect 表 4 6 通过类查看 ClassView 选项卡 向视图类添加成员变量 变量类型变量名功能描述 intm SortSelect N 记录关键字 CRectm SortSelectRect 动态演示矩形范围 BOOLIsSortSelect TRUE 表示进行选择排序 在 TtView h 头文件 声明选择排序的全局函数 UINT ThreadSortSelect LPVOID lp 然后 在 TtView cpp 构建文件中添加实现选择排序算法的函数 ThreadSortSelect 代码为 UINT ThreadSortSelect LPVOID lp int i j key tmp 第 12 页 共 21 页 int data data pView m SortSelect for i 0 i N 1 i key i for j i 1 jdata key key j pView Invalidate TRUE Sleep DELAY1 Sleep DELAY tmp data i data i data key data key tmp Sleep DELAY pView Invalidate TRUE return 0 在类中查看 Class View 选项 打开视图类 CTtView 在其中修改构 建函数 实现变量初始化 CTtView CTtView int i srand unsigned time NULL for i 0 i N i m SortSelect i 0 pView this IsSortSelect FALSE 修改响应函数 OnSortSelect 产生 0 70 随即整数来进行排序 void CTtView OnSortSelect for int i 0 iTextOut 50 200 选择排序演示 for i 0 iFillRect BlueBrush DeleteObject 4 44 4 动态演示快速算法模块设计动态演示快速算法模块设计 表 4 7 为工程添加 IDR MAINFRAME 的菜单选项 ID 说明文字功能描述 IDC SORT QUICK 快速法排序快速法排序 表 4 8 打开类向导 Class Wizard 对话框向视图类添加响应函数 Object IDMessages Messages 的描述函数名 IDC SORT QUICKCOMMAND 快速该菜单 OnSortQuick 表 4 9 通过类查看 ClassView 选项卡 向视图类添加成员变量 变量类型变量名功能描述 intm SortQuick N 记录关键字 CRectm SortQuickRect 动态演示矩形范围 BOOLIsSortQuick TRUE 表示进行选择排序 第 14 页 共 21 页 在 TtView h 头文件 声明选择排序的全局函数 UINT ThreadSortQuick LPVOID lp void QuickSort int data int s int t 在 TtView cpp 构建文件中添加实现快速排序算法的函数 ThreadSortSelect 和 QuickSort 代码为 void QuickSort int data int low int high int i low j high int tmp key if low high tmp data low while i j while i j if data j Invalidate TRUE while i tmp i Sleep DELAY1 else break 第 15 页 共 21 页 key data i data i data j data j key Sleep DELAY pView Invalidate TRUE QuickSort data low i 1 QuickSort data i 1 high UINT ThreadSortQuick LPVOID lp int data data pView m SortQuick pView Invalidate TRUE Sleep DELAY QuickSort data 0 N 1 return 0 打开类 Class View 中视图类 CTtView 在其中修改构建函数 实现 变量初始化 CTtView CTtView int i srand unsigned time NULL for i 0 i N i m SortQuick i 0 pView this IsSortQuick FALSE 修改响应函数 OnSortQuick 产生 0 70 随即整数来进行排序 void CTtView OnSortQuick for int i 0 iTextOut 450 200 快速排序演示 for i 0 iFillRect BlueBrush DeleteObject 4 54 5 同时比较三种算法模块设计同时比较三种算法模块设计 表 4 10 为工程添加 IDR MAINFRAME 的菜单选项 ID 说明文字功能描述 IDC SORT ALL 同时比较三种方法同时进行比较 表 4 11 打开类向导 Class Wizard 对话框向视图类添加响应函数 Object IDMessages Messages 的描述函数名 IDC SORT ALLCOMMAND 快速该菜单 OnSortAll 同时比较这三种排序 就是同时调用这三种排序演示线程 修改响应函数 OnSortAll void CTtView OnSortAll TODO Add your command handler code here OnSortBubble1 OnSortQuick1 OnSortSelect1 第 17 页 共 21 页 4 64 6 系统的测试系统的测试 每一个红色 同时排序的蓝色 的竖条都代表一个随即数 以下相同 1 冒泡排序的动态演示开始 冒泡排序的动态演示结束 图 4 2 冒泡演示开始 图 4 3 冒泡演示结束 2 选择排序的动态演示开始 选择排序的动态演示结束 图 4 4 选择演示开始 图 4 5 选择演示结束 3 快速排序的动态演示开始 快速排序的动态演结束 图 4 6 快速演示开始 图 4 7 快速演示结束 同时演示三种排序 比较他们的排序过程的快慢 第 18 页 共 21 页 1 开始 图 4 8 同时比较三种排序开始 2 第一个排序 快速排序完毕 图 4 9 快速排序结束 3 第二个排序 选择排序完毕 图 4 10 选择排序结束 4 最后一个排序 冒泡排序完毕 图 4 11 冒泡排序结束 第 19 页 共 21 页 4 74 7 系统的特点系统的特点 在运行本系统的时候 选择不同的菜单选项 能够清楚的看出各种排序过 程的变化 例如 1 选择 冒泡法排序 时 可以看见绿色的长条逐渐向左移动 完全验 证了冒泡排序算法的思想 2 选择 选择法排序 时 可以看见绿色的长条是被交换到左边的过程 这个也完全证明了选择排序算法的思想 3 选择 快速法排序 时 可以看见整个序列在经过 i j 的过程后 被 分成了 2 个子序列 再排列两个子序列后完成排序 这个也验证了快速排序算 法的思想 4 选择 同时排序 时 可以清楚的看