【毕业学位论文】（Word原稿）基于VB多种排序方法的探究性实践-计算机科学

基于 种排序方法的探究性实践 作者：北京陈经纶中学 研究学科：计算机科学 指导老师： 北京 陈经纶中学 目 录 摘要 . 1 关键词 . 1 . 1 . 1 1 引言 . 2 究题目的产生 . 2 前高中阶段对排序知识介绍的现状 . 2 2 本实践方法的整体概述 . 2 3 分阶段探索的过程与数据采集 . 3 步摸索阶段 . 3 近指标阶段 . 6 成指标，并获较大提升阶段 . 7 服数据量再增大的局限 . 9 试再拓展阶段 . 10 4 全部方法的数据整合与分析 . 14 5 存在的不足与改进方向 . 16 参考文献 . 17 致谢 . 17 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 1 基于 种排序方法的探究性实践 北京市陈经纶中学 高 二 11班 田欣宇 摘要 本 研究在计算机老师的一个“ 限时 1 秒对 N 个 1,10000的 随机整数 排序 ”命题基础上，采用 10 种排序方法逐一进行了探究性实践，从中获取了相关的实践数据和分析图表，比较分析了各种方法优势与弱点，通过实践不但圆满完成了命题要求，重要的是此过程中拓展了思维，体验了新的算法，提高了编程能力，是对学生自主性学习进行的一次有益的尝试。 关键词 序；探究实践 on a a 1,10000 up by my an to 0 by of of it is me to my is a s B; 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 2 1 引言 究题目的产生 上学期， 在 学校 开展的 “ 生 动课堂 ” 活动 中 ，计算机的 老师给出一个“ 限时 1 秒对 N 个 1,10000的 随机整数 排序 ”命题。起初，自己与班上的同学都认为：当今的计算机性能优越，像在 将一列数据从小到大（ 序，只要一 点，眨眼的功夫瞬间搞定。但 老师说， N 是一个自然数，要多大有多大？你能用 已 学到的 计算机编程方法 解决该命题，给出确切的 N 的值吗？ 到底 在 1秒钟内 能够达到多少 ？ （ 100； 1000； 10000； 100000； 1000000 ） 希望至少达一万以上为优。 至此，大家 谁也不 能给出准确的答案， 都 感觉应该不少，但具体的数量级和数值谁也拿不出来 ，我做为班上的课代表 对这个题目亦产生了兴趣，就跃跃欲试起来 前高中阶段 对排序知识介绍的现状 在目前的 普通 高中计算机课程 中，信息技术基础必修教材未涉及排序算法的知识， 在 选修 1：算法与程序设计 模块中，介绍了 言和冒泡法排序。 2 本 实践 方法 的 整体 概述 在接受计算机老师的挑战题目 时，我们的计算机课还未讲排序算法，当时无法下手，后在查找教材资料和与指导老师 沟通后，选 定 为实验编程的语言，搭建了 必要 的实践环境，即在 利用随即函数产生 N（ N 由人工输入） 个 1,10000整数，并将其写入一个顺序文件（ 中，随后进入排序部分程序之前，设置记时变量记住当时的时间后，让程序进入 某 一具体的排序 算法程序 完成排序后，再次将当时的时间写入记时变量 ，前后两次记时变量的差值就是排序所用时间，之后将排好的数据依次输出到另一个顺序文件（ 待查。 接下来实践了 10 种不同的排序算法，逐一记录了各个方法在不同数据量下的排序时间 ，为比较分析之用。 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 3 3 分阶段 探索 的过程 与数据采集 步摸索阶段 第一次 摸索 ，采用了的冒泡法和比较交换法做了尝试 其 冒泡法（起泡法） 算法 的 步骤 是：对于 n 个数据 来说 ，依次确定 1 到 数据。首先确定 1 号位置上应该放哪个数据，方法是将n 至 2 号位置上的数据依次与前一个位置上的数据相比较，如果后 面位置上的数据小于前面位置上的数据，则交换这两个位置上的数据。 经 一轮比较之后， 就将n 个数据中最大的沉到底部，而比其小的数据浮到了上边，故称起泡法（冒泡法），之后 再确定 2 号位置上应该放哪个数据，依此类推。 经 n 轮后，所有数据均以排好。 比较 （ 交换 ） 法 算法 的 步骤 是：对于 n 个数据，依次确定 1 到 位置上分别应该放哪 些 数据。首先确定 1 号位置上应该放哪个数据，方法是将 2至 n 号位置上的数据依次与 1 号位置上的数据相比较，谁比当前 1 号位置上的数还小，谁就与 1 号位置上的数对换。一轮比较之后，再确定 2 号位置上应该放哪个数据，依 此类推。 按这两种算法思想，我进行了相应的编程实践，在 操作系统 P 编程软件 2300 存 时：秒 数据量 N= 冒泡法 比较法 1000 000 000 000 000 0000 3 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 4 图 3泡法完成 10000 个数据下排序耗时 ，比较交换法完成 10000个数据下排序耗时 。经多次测试，冒泡法 完成 2900 个数据的排序，比较交换法用 完成 2900 个数据的排序。从实践的结果上看，这两种方法的排序效率离命题的要求相距甚远。 要想提高速度，就要在算法上加以改进。 第 二次摸索，改进 比较交换法 ， 考虑比较交换法中两两比较时，一旦发现 后边的元素的数据比前边的大就马上交换，使可能的交换次数接近 n；次数过多。但若在比较时先记住后边小的元素的位置，当一轮比较都完成后，再进行一次交换 ，从而 在内循环中减少实际的交换次数， 由接近 n 次下降为最多 1 次 , 这便是选择法的算法思路 ,具体步骤为 ：对于 n 个数据，依次确定 1 到 位置上分别应该放哪 些 数据。首先确定 1 号位置上应该放哪个数据，方法是假设 1 号位置上的数据最小，所以记录 1 号为最小数所在位置号。将 2 至 n 号位置上的数据依次与最小数位置号上的数据相比较，如果比最小数位置号上的数据还小，则记录该数据所在的位置 号为最小数位置号。一轮比较之后，将最终确定的最小数位置号上的数据与 1 号位置上的数据对换 ， 然后再确定 2 号位置上应该放哪个数据，依此类推。 经改进过的选择法排序程序，在 集成开发环境下运行测试的结果为： 0 2 4 6 8 10 12 14 0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 冒泡法 比较法 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 5 操作系统 P 编程软件 2300 存 时：秒 数据量 N= 比较法 选择法 1000 000 000 000 000 0000 3 3实践结果（表 3图 3出，因改善了算法，选择法与比较交换法相比较，显著地减少了耗时， 1 秒大约可以进行 4000 个数据的排序，效率有所提高，但要完成 10000 个数据的排序仍大约需要 5 秒多的时间，还无法完成命题的指标。看来直接运用结构简单的排序方法直接运用到大数据量的排序工作时，耗时仍相当可观，不可不计；要提高效率达标，只得另选途径。 0 1 2 3 4 5 6 7 8 9 10 11 0 2000 4000 6000 8000 10000 比较法 选 择法 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 6 近指标阶段 在经过两轮的编程实践后，特别是改进了算法仍无法达标时，及时地与指导老师进行了沟通，老师肯定了前边的工作并提示能否考虑采用编译运行方式提高速度，这样就将上述的三种排序方法的 序生成了可直接运行的 序，再次测试结果如下： 操作系统 P 编程软件 2300 存 译 法运行用时：秒 数据量 N= 冒泡法 比较法 选择法 1000 000 000 000 000 0000 3 3况有了非常显著的改善，以选择法为例两种运行方式的对比数据如下： 0 0 2000 4000 6000 8000 10000 冒泡法 比较法 选择法 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 7 操作系统 P 编程软件 2300 存 择法用时：秒 数据量 N= 解释法运行 编译法运行 1000 000 000 000 000 0000 3 3实践数据分析得知， 编译执行可以大大提高运行速度，在数据量大的低效排序程序中反映得很突出。整体效率大幅提高，（见表 3 3择法排序程序在编译执行状态下完成 10000 个随机整数的用时为 左右，是三种方法中最接近题目的要求的。 成指标，并获较大提升阶段 在进行上述三种排序方法的实践中，也进行了算法优化并改进了运行方式，但离题目的要求仍存在距离，正在无法继续下去的时候，编程过程中无意涉及到列表框控件的属性中，看到 想若将数据放入列表框 将该 性设置为 就可以让 我们排序了0 1 2 3 4 5 6 0 2000 4000 6000 8000 10000 解释法运行 编译法运行 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 8 吗？接着的编程实践证实，该思路可行，而且效率不低，首次达到了命题的指标。列表框排序法运行的实践数据如下： 操作系统 P 编程软件 2300 存 表框法用时：秒 数据量 N= 运行 1000 000 000 000 000 0000 0000 3000 10000 15000 20000图 3实践数据得知，列表框 序（即 身所带的排序）方法效率蛮高，对 10000 个随机整数仅需约 的时间，放到 1 秒时，大约可以排 18000左右的数据量，较好的达到命题要求，并略有余量。 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 9 服数据量 再增大的 局限 刚解决了效率问题，列表框排序法虽然可以达到原题目的指标要求，但随之也产生了新的问题，微软 的 件列表（ 身容量为 32768 列（等于整型变量的上限值） ,这就是说，用其实现的排序程序最多可以完成 32768 个数据的排序任务，只要一超过此上限，程序便会中断执行，给出溢出错误。这就给更大数据量的排序实践设定了局限性，这时指导老师也提示我，让我自己通过查找资料，看一看，探索一下有无解决方法？ 在经过一番的查找资料和上网搜索后，我锁定了真对列表框 数容量限制的解决方案，即用 件代替 件，而 件的列表容量高达 2147483647，较 高很多，从而再次编程实践，验证了其可用性，实践数据为： 操作系统 P 编程软件 2300 存 用时：秒 数据量 N= 运行 10000 0000 0000 0000 0000 00000 00000 3上实验数据得知，虽然数据量较前表 3成倍增长 ,序法所用时间大大缩短，即使数据量达到 20 万时，程序仍可正常运行。 在我完成了 的程序后，指导老师建议从另一个思维考虑，既然一个列表框对于大数据量有局限，能否在程序上想办法，采用双列表框法，把要 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 10 排序的数据分成两部分，一半存入列表框 1，另 一半存入列表框 2，两者分别排序，最后一道输出，完成整个的排序任务。按照此思路，我又实践了双列表框的编程，结果令人满意，超过 32768 的数据量也可以排了，实践数据为： 操作系统 P 编程软件 2300 存 列表框法用时：秒 数据量 N= 运行 5000 0000 0000 0000 0000 0000 3试 再 拓展 阶段 在完成上述几种排序程序的设计实践后， 大致梳理 一下：三种简单的排序方法在数据量小（ 3000）时耗时尚可；单列表框和双列表框法及 直接利用了 件自身的排序机制，时间快，数量大，程序简单。但从程序设计角度上无法探究其内部的程序设计理念和算法结构，只是将其视为黑盒，仅关心输入与输出结果，而不研究其内部机理。若只从完成命题来说，表面上可以达到，但实际仍感到欠缺。故没有止步，继续尝试新的拓展，实践能 否在成开发环境下直接用新的更优的算法，更快的程序完成题目要求的指标。其间与指导老师再次交流后，老师也十分支持我的想法，让我再多试一下，看看解决命题的 新途径 。 确定方向后，我看到一本 C 程序设计的书上有插入法排序的介绍，但只有大致的算法介绍与 C 语言的参考程序段，于是我就参看其程序，并仔细分析了算法原理和步骤，着手新的程序调试，用 语言逐句逐步的构建 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 11 测试插入法排序的程序，并用前边搭好的随机数生成器，时间控制语句等程序段测试新的程序，得到的数据结果为： 操作系统 P 编程软件 2300 存 时：秒 数据量 N= 选择法 运行 插入法运行 1000 000 000 000 000 10000 3 3实践结果看，插入法与选择法接近，比其略好一些，但整体数量级上未有明显的提高。这条路不行，再找，在网上搜到一大堆排序的算法，如快排序、希尔排序、堆排序、桶排序、基数排序、归并排序、 鸽巢 排序、 等等等，有的声称可以达到每秒百万级的速度，让我看得为之心动，很不得马上实践一下，但到真的要实际编写程序时发现，这些算法不只是程序复杂，多数是用 C 语言或 C+写成的，有的用描述语言写的大致思路，有的只是算法的介绍，关键的0 1 2 3 4 5 6 0 2000 4000 6000 8000 10000 选择法 插入法 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 12 是其都与数据结构知识相关，如堆、桶、队、树、散列、递推、递归等等，而我们高中的课程上还没有涉及 这方面的知识介绍（即未讲过 C，也没有数据结构）从而使得理解起来十分吃力，且毫无头绪，无从下手。真正感到思维拓展面临的就是挑战。由初学到提高必需迈过一道又一道坎，面对困难，我没有放弃，在指导老师的鼓励下，我找了相关的参考书，并借助网络资源，从基础学起，一点一滴地理解算法，不断整理思路，反复的分析结构，编写代码，推翻，再编写，再推翻，一次一次地推到重来，一次一次地总结存在的问题，一次一次地探索前进，一次一次地逼近目标，一次一次地测试，一次一次地统计数据 在这段探索的阶段，使我对排序算法的认识产生了崭新的提高 ，理解到快排序的思想是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都小，然后再依次按这样的方法对这两部分的数据分别进行快排的过程，即整个过程采用递归进行，直到全部数据变成有序序列为止。在大块上来看，其像冒泡法排序形式，但一趟不是做一个数据的上升和沉底，而是做一整部分的分割，同时由于引入了递归的思想，将整体数据分割之治 ，逐步细化，从而最大限度的减少了比较和移动次数，大大提高了效率；而希尔排序排序是插入法的改进型，即把整体数据分成若干个小组，所有距离成倍数的数据放在 同一组中，先在各组内进行直接插入法排序，然后改变分组再排序，直至所有数据放在同一组中进行直接插入排序为止；堆排序是将所有的数据看做是一颗完全二叉树的结构，其性质是树中的任一非叶结点的值均不大于其左右孩子的值，而整个排序的过程就是构造堆的过程，将原无序的数据调整为堆对应的完全二叉树的结构，再遍历输出即可。在理解算法的基础上，经反复调试程序，得到的实践数据表明 的快排序、希尔排序和堆排序的程序的运行速度比前边的方法有了大幅成倍的 显著 提高，具体结果如下： 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 13 操作系统 P 编程软 件 2300 存 时：秒 数据量 N= 快排序 希尔排序 堆排序 5000 0000 0000 0000 00000 00000 3 3 50000 100000 150000 200000 快排序 希尔排序 堆排序 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 14 4 全部方法的数据整合与分析 现将实践中的数据结果整合在一起，直观的表现各种算法的数据量与耗时的情况： （各种排序程序均以编译后运行的数据进行比较） 操作系统 P 编程软件 2300 存 时：秒 N= 冒泡 比较 选择 插入 双列表 排 希尔 堆 桶 1000 000 000 000 000 000 7000 8000 10000 20000 30000 50000 100000 150000 200000 表 4 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 15 0000 40000 60000 80000 100000 120000 140000 160000 180000 200000冒泡 比较 选择 插入双列表 排 希尔堆 桶图 4上数据分析和程序测算，各种方法在 1 秒钟完成的排序数据量大致如下： （硬件参数同表 7描述） 方法 数据量 冒泡法 4846 比较法 5015 选择法 6210 插入法 7500 双列表框法 30500 78000 快排序 215000 希尔法 155000 堆排序 109000 桶排序 4190 表 4 基于 种排序方法的探究性实践 作者：北京陈经纶中学 田欣宇 16 图 4合分析本次 实践 中 的 10 种排序 ，若仅 时间上看，冒泡法、比较法和 选择法（包括桶排序）属于慢速一大类，其算法的特点是程序简单，一般是 5代码行，结构直观，容易理解，即采用两两交换或固定一个，比较一个，马上或找到位置后交换等，程序上多用双层循环即可，其慢速的原因就是在比较和交换的次数多，存在一定的重复，导致效率低，但这类方法当数据量小的时候，耗时还在可以接受的范畴之内，对付小型量的数据排序尚可；当数据量达 5000速排序的方法就显得无能为力了，此时，双列表框， 能较好的解决，而当数据量再大达 10000 以上时，快排序、希尔排序和堆排序就可以 大显身手了，采用分组，分割之治，二叉树遍历等减少了数据的比较和移动，从