排序算法比较系统

一．         项目计划书

1.     项目的选题意义

随着计算机科学技术的快速发展，排序成为了计算机程序设计中的一种重要操作。它在计算机图形、计算机辅助设计、机器人、模式识别及统计学等领域具有广泛应用。在实际应用当中比如数据统计等方面都会用到。而且对一组数据进行排序也方便了后面对数据查找的操作。要知道在一个有序数组中查找和在一个随机无序数组中的查找的时间复杂度和系统消耗是有天壤之别的。它的的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。由于排序法很多，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都有各自的优缺点，适合在不同的的环境下使用。一般情况下，采用不同的排序算法效率会不一样。因此，在不同的环境下选择相对效率最高的排序算法，能够有效加快工程实施的进度。为了方便大家了解不同排序算法的时间效率，特建立一种排序算法比较系统，实现比较不同排序算法效率的目的。

2.     项目的主要内容和目标

排序算法比较系统主要实现的下列十种功能:

一．简单选择排序；

二．折半插入排序；

三．直接插入排序；

四．冒泡排序；

五．希尔排序；

六．快速排序；

七．归并排序；

八．堆排序；

九．清屏；

十．退出系统；

  3．项目的技术基础、特点及实施的条件

该项目可用C语言实现，适于在单机环境下运行。小组成员均已学习过C语言程序设计、数据结构、算法等课程，具有一定的开发能力。

4.项目人员分工

   所有人都参与了项目的选题、设计、实现及测试工作，项目负责人归纳整理小组成员

讨论成果，并确定最终方案。在实践阶段，按照功能模块具体分工如下：

   项目组负责人：李齐，构建模型、设计算法、设计界面、实现功能二、四、五、六、七、十

   项目组成员：刘运皇，初始化数据、实现功能一、三、八、九

二．    设计方案

1. 算法思想的选择与设计

   此项目来源于实际问题。通常，在排序的过程中需进行下列两种基本操作：（1）比较两个关键字的大小；（2）将记录从一个位置移动至另一个位置。待排序的记录序列可以用顺序存储结构进行存储，即待排序的一组记录存放在地址连续的一维数组中。在这种存储方式中，记录之间的次序关系由其存储位置决定，则实现排序必须移动记录。因为我们目的要对一系列的正整数进行排序，因此选择顺序存储的方式简洁明了，易于让人理解。

而在功能实现过程中，在排序算法比较系统中，要用到递归和分治的思想，以便于算法的设计与实现。我们用库函数来随机生成一系列的正整数，进而选择不同排序算法进行排序比较。其具体实现如下：

#include<time.h>

srand((unsigned)time(NULL));

          for(long i=0;i<20000;i++)

           {

            a[i]=rand()%20000;

           }

2. 总体设计方案

首先构建模型初始化数据；其次，为十种功能设计算法并实现；最后，设计界面，完善系统的人机交互功能。

3. 详细设计方案

（1）算法设计及流程图

  第一种功能是简单选择排序。其算法思想是对于第一趟，搜索整个数组，寻找出最小的，然后放置在数组的0号位置；对于第二趟，搜索数组的n-1个记录，寻找出最小的（对于整个数组来说则是次小的），然后放置到数组的第1号位置。在第i趟时，搜索数组的n-i+1个记录，寻找最小的记录（对于整个数组来说则是第i小的），然后放在数组i-1的位置（注意数组以0起始）。可以看出，选择排序显著的减少了交换的次数。此种算法的流程图如图1。

第二种功能是折半插入排序。其算法思想：基本思想与直接插入排序思想相似，唯一的不同点在于找出插入位置，直接插入排序用的是依次查找，而折半插入排序是用折半查找。此种算法的流程图如图2。

第三种功能是直接插入排序。其算法思想是在要排序的一组数中，假设前面(n-1) [n>=2] 个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。此种算法流程图如图3。

第四种功能是冒泡排序。其算法思想是在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。此种算法的流程图如图4。

     第五种功能是希尔排序。其算法思想是算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。此种算法的流程图如图5。

    第六种功能是快速排序。其算法思想是通过一趟扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理它左右两边的数，直到基准点的左右只有一个元素为止。此种算法的流程图如图6。

第七种功能是归并排序。其算法思想是是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。此种算法的流程图如图7。

第八种功能是堆排序。其算法思想是堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。此种算法的流程图如图8。

 

1.简单选择排序算法流程图

   

（2）界面的设计

 *****************************************************

               排序算法比较系统

 ******************************************************

               1.简单选择排序

———————————————————————————

              2.折半插入排序

———————————————————————————

              3.直接插入排序

———————————————————————————

              4.冒泡排序

———————————————————————————

              5.希尔排序

———————————————————————————

              6.快速排序

———————————————————————————

              7.归并排序

———————————————————————————

              8.堆排序

———————————————————————————

              9.清屏

———————————————————————————

             10.退出系统

================================================

4.项目测试方案

项目负责人  李齐：单元测试、集成测试

项目组成员  刘运皇：系统重构、黑盒测试

三．         参考文献

[1]谭浩强。《C程序设计》清华大学出版社，2005

[2]严蔚敏，吴伟民. 《数据结构（C语言版）》. 清华大学出版社，2007

[3]许秀林，董杨琴. 《程序设计基础教程（C语言与数据结构）（第二版）》. 中国电力出版社，2009

[4]李建学，李光元，吴春芳. 《数据结构课程设计案例精编（用C/C++描述）》. 清华大学出版社，2007

[5]王晓东。《计算机算法设计与分析》电子工业出版社，2007

四．课程设计体会

本次课程设计题目是“排序算法比较系统”，是由我们这个小组的两名同学通过结合实际生活共同选定的。刚开始做这个系统的时候，感到完全无从下手，甚至让我觉得这次课程设计根本无法完成。在查阅了各种资料以及参考文献并和小组其他成员进行大量的讨论之后终于对系统的开发过程与方法有了一些思路，于是我们决定按照C语言程序设计来完成该系统的开发。通过对实际问题的思考和分析，我们将各部分的算法构建成数学模型，并通过递归与分治两种算法思想来完成对该系统模型的构建。最后完成了对各种排序算法的效率比较。

在该系统的开发过程中，我们遇到了一些困难，如无法统计各排序算法的时间，后来经过查阅资料及同学讨论，找到了相应的解决办法。在测试时又发现了很多问题，主要原因是编写代码时考虑不周，经常出现一些语法错误，但通过同学间的帮助最终都解决了问题。

在本次课程设计中，我明白了理论与实践相结合的重要性，并提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能以及合作能力。这次课程设计同样提高了我的综合运用所学知识的能力。并对C语言有了更深入的了解。《算法》是一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个环节。因此，在《算法》的学习过程中，必须严格按照实验大纲的要求，主动地、积极地、认真地做好每一个实验，以不断提高自己的编程能力与专业素质。同时，在学习《算法》之前，必须要复习C/C++语言，要对指针和结构体的相关知识进行深入学习并上机实践以提高编程能力。

本系统的创新之处是实现了对多种内部排序算法的效率比较，但是也有许多不足之处，如：没有实现对数据的排序过程的应用，无法确定系统是否稳定，并且，系统缺少健壮性。

总的来说，这次课程设计让我获益匪浅，在项目实施过程中，提高了分析问题和解决问题的能力，更加强了实践操作能力。对《算法》也有了进一步的理解和认识。在课程设计的一周里，我与团队其他成员积极协作，有效沟通，圆满地设计并实现了排序算法比较系统。课程设计让我对团队精神的重要性有了深刻认识，在工作生活当中，个人力量往往显得有限，只有加强合作才能顺利完成任务。

 

第二篇：冒泡排序算法的程序及调试实验报告

1113240118 黄奕毅

冒泡排序算法的程序及调试大作业

单击“开始”→“所有程序”→“Microsoft Visual Basic 6.0中文版”→“Microsoft Visual Basic 6.0中文版”

在已经打开的界面内双击打开“标准EXE”如下图：

点击工具箱窗口的“Frame”在窗体窗口中添加“Frame1”和“Frame2”

分别点击工具箱窗口的“Label”和“Command Button” 在“Frame1”和“Frame2”中添加“Label1” 、“Label2” 、“Label3” 、“Label4”和“Command1” 、“Command2” 利用Visual Basic提供的对齐、布局等功能调整控件的位置，使之对齐并美观

在属性窗口中更改控件设置：

将“Frame1”改为“初始数据”

将“Frame2”改为“排序结果”

将“Label1”改为“姓名（张三，李四，王五，刘六，贾七，李一，秦八，赵二，程九，王

十）”

将“Label2”改为“成绩（12，7，49，78，19，33，66，50，51，80）”

将“Label3”改为“姓名”

将“Label4”改为“成绩”

将“Command1” 、“Command2”分别改为“排序” 、“退出”

点击“排序”

1113240118 黄奕毅

在光标处输入程序代码：

'冒泡程序

Dim sName, Grade

Dim Temp As Integer

Dim Temp1 As String

sName = Array("张三", "李四", "王五", "刘六", "贾七", "李一", "秦八", "赵二", "程九", "王十") Grade = Array(12, 7, 49, 78, 19, 33, 66, 50, 51, 80)

For i = 0 To 9

For j = 0 To 9 - i

If Grade(j) < Grade(j + 1) Then

'交换程序

Temp = Grade(j + 1)

Grade(j + 1) = Grade(j)

Grade(j) = Temp

'交换姓名

Temp1 = sName(j + 1)

sName(j + 1) = sName(j)

sName(j) = Temp1

End If

Next j

Next i

'排序后姓名按照成绩的由高到低输出

Dim eName As String

eName = ""

For k = 0 To 9

eName = eName & " " & sName(k)

Next k

Label3.Caption = "姓名(" & eName " )"

1113240118 黄奕毅

'排序后姓名按照成绩的由高到低输出

Dim eScore As String

eScore = ""

For s = 0 To 9

eScore = eScore & " " & Str(Grade(s))

Next s

Label4.Caption = "分数(" & eName " )"

点击“运行”→“启动”，开始启动程序

单击“排序”按钮会出现错误，信息提示为“下标越界”

单击“调试”， “If Grade(j)<Grade(j+1)Then”处出现了黄色背景提示

将“For i=0 To 9”和“For j=0 To 9-i”两处的“9”改为“8”

点击“运行”→“重新启动”

单击“排序”，得出最终结果，如下图：

另外，还可点击“调试”对程序进行“设置断点调试” 、“单步调试”等操作

1113240118 黄奕毅