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

1、多种排序算法动态演示软件的设计与开发摘要随着计算机科学技术的不断提高和发展，其强大的运算功能已经逐渐融入 人类社会的各个领域，并且在各个领域中发挥越来越重要的作用。当然，高效 的运算速度并不代表无限快，在有限的资源空间里，要大大提高运算处理数据 的速率，就需要我们使用那些在时间和空间上体现出高效的算法。本系统是为 了演示在同一问题上，不同的算法在效率上存在的巨大差异。本系统采用Visual C+ 6.0中文版为开发工具，实现三种不同排序算法，即：冒泡排序算法、选 择排序算法和快速排序算法，以及这三种排序对同一问题的处理并且以图形的 形式给出快慢比较，实现排序算法的动态演示。其目的是为了让我们在

2、使用计 算机处理规模越来越大的数据问题上，能够清楚什么样的算法适合当前的处理 系统。关键词：Visual C+ ;排序算法；动态演示The Design and Development of Dynamic SortingAlgorithm DemoAbstractWith computer scie nee and tech no logy improveme nt and developme nt, its powerful computing has gradually integrate into human society in various fields, and play an

3、 increasingly important role. Of course, efficient computational speed does not mean unlimited fast, and the limited resources of space, Operators must sig nifica ntly improve process ing speed, we n eed to use the time and space reflects efficie nt algorithms. The system is to dem on strate on the

4、same issues in differe nt algorithm efficiency in the enormous differenee. 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 Algori

5、thm, 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 dyn amic prese ntati on .Its purpose is that en able us to use computers to han dle the increasingly large scale data problems, to know what kind of algorithm i

6、s suitable for the curre nt system.Key words： Visual C + ; Sort ing Algorithm; Dyn amic Dem on strati on目录论文总页数：21页 TOC o 1-5 h z 弓I言 1 HYPERLINK l bookmark8 o Current Document 系统背景 1 HYPERLINK l bookmark10 o Current Document 系统开发的意义 1 HYPERLINK l bookmark12 o Current Document 系统开发的相关技术 1 HYPERLINK

7、l bookmark14 o Current Document 系统开发的相关概念 1 HYPERLINK l bookmark16 o Current Document 系统需求及分析 2 HYPERLINK l bookmark18 o Current Document 系统需求 2 HYPERLINK l bookmark20 o Current Document 系统开发环境选择 2 HYPERLINK l bookmark22 o Current Document 系统的总体规划 2 HYPERLINK l bookmark24 o Current Document 系统设计思想 2

8、 HYPERLINK l bookmark26 o Current Document 冒泡算法及思想 2 HYPERLINK l bookmark34 o Current Document 选择算法及思想 4 HYPERLINK l bookmark40 o Current Document 快速算法及思想 5 HYPERLINK l bookmark42 o Current Document 详细设计 8 HYPERLINK l bookmark44 o Current Document 系统的文件的组织 8 HYPERLINK l bookmark46 o Current Document

9、 动态演示冒泡算法模块设计 8 HYPERLINK l bookmark48 o Current Document 动态演示选择算法模块设计 11 HYPERLINK l bookmark50 o Current Document 动态演示快速算法模块设计 13 HYPERLINK l bookmark52 o Current Document 同时比较三种算法模块设计 16 HYPERLINK l bookmark54 o Current Document 系统的测试 16 HYPERLINK l bookmark66 o Current Document 系统的特点 18 HYPERLIN

10、K l bookmark68 o Current Document 结论 19 HYPERLINK l bookmark70 o Current Document 参考文献 19 HYPERLINK l bookmark72 o Current Document 致谢 20 HYPERLINK l bookmark74 o Current Document 声明 21第 页共21页1 引言1.1系统背景由于排序在计算机图形、计算机辅助设计、机器人、模式识别、基因排序 工程及统计学等领域具有广泛应用，所以对排序的研究既有理论上的重要意义， 又有实际应用价值。再加上现在信息产业的迅速发展，信息的流

11、通量越来越大, 如此庞大并且杂乱无章的信息数据十分难以管理和查询，就更加需要一种十分 快捷而有效的编排手段来整理这些数据信息，让我们的工作效率得以提高。1.2系统开发的意义在现代信息发达的今天，面对接受到大量的无序的信息，没有一个规则来 编排和查询，会给我们的工作和信息交流带来十分的不便。因此，利用计算机 的高速运用和计算能力，编写出一种合适的排序软件，能十分快捷的给我们在 信息交流和查询带来便利。例如在互联网上为了使人们能够快速的访问和检索 大量的信息，人们会运用许多快速并且优秀的算法对这些数据进行管理和操纵。 优秀的算法还能帮助我们在互联网上快速找到最好的发送数据路线，以及怎么 用搜索引擎

12、来快速地找到信息所在的页面。1.3系统开发的相关技术本系统利用Visual C+ 6.0 作为开发平台，利用它的可视化界面，在其 MFC环境下开发的一个演示三种不同排序算法，利用画刷画出三种不同的排序 算法在排列随即产生的0-70个数的过程，并且能够对比这三种排序算法在相同 的条件下，排序速率的快慢。运用 VC编程语言，把一个程序中的算法和程序框 架有效的结合起来，并且实现排序算法的动态演示。1.4系统开发的相关概念首先我们要了解排序到底是什么？它的主要功能和目的是什么？简单的 说，排序是利用一种算法，将一个无规则的序列排成一个有序序列的过程。而 算法则是以一组值或者一个值的集合作为输入，经过

13、一系列计算得到的一组值 作为输出的过程，即是指那一系列将输入转化为输出的计算过程。排序的方法有很多种，但是没有一种排序算法是通用的，即在任何情况下 都能保持最快的排序速度。因此我们必须根据需要处理数据的特点来选择合适 的算法。在排序的过程中，我们一般需要用到的两个基本操作步骤是：比较两 个关键字的大小和将记录从一个位子移至另一个位子，即比较和交换。本系统 设定的情况为，记录关键字都为整数，排序的结果是从大到小的排列，用到的 三种排序算法为：冒泡排序法、选择排序法、快速排序法。2系统需求及分析2.1系统需求本系统的硬件环境：CPU AMD 2800+内存512M以上，硬盘80G以上。 本系统的软

14、件环境：操作系统 Win dows XP,Visual C+ 6.0 中文版。2.2系统开发环境选择本系统运用的是Visual C+6.0中文版，它是微软公司开发出的一种集成 开发环境，它拥有良好的可视化界面，它用来在Windows环境下开发应用程序， 是一种功能强大、行之有效的可视化编程工具。在Visual C+6.0中能够进行多种操作，它的特点就是能够把原来抽象的数字、表格、功能逻辑等用直观的 图形、图象的形式表现出来。排序算法本来就是一种抽象的逻辑功能，想要直 观的把它演示出来，选择利用 Visual C+6.0的可视化编程是非常明智的。而 且本系统在开发过程中，能够用鼠标点击按钮和拖放

15、图形化的对象，修改他们 的属性和行为过程。这种可视化的编程方法简单、易学、易用，可以大大提高 我们的工作效率。2.3系统的总体规划本系统的总体结构如图2-1所示：图2-1系统总体结构3系统设计思想3.1冒泡算法及思想冒泡排序算法的基本思想：冒泡法的原理很简单，基本思想就是比较相临 的两个记录的关键字，若前者比后者小则交换，若前者比后者大则保持不变。 先将第一个记录与第二个记录比较，然后是第二个与第三个比较，直到倒数第 二个与最后一个记录。比较一轮结束之后，关键字大的记录均向前移动。然后 开始新一轮的比较，知道一轮比较下来，不再有记录的交换发生为止。整个过程就有点象水中的气泡上升的过程，轻的往上

16、浮，重的向下沉，这个算法的名 字也就由此得来。算法的步骤如下：（1）假设要排序的数列为 A1 , AN，我们把相邻的两个数两两进行比较。即把A1和A2比较，对比完后把A2和A3进行比较，”直到 AN-1 和AN比较完为止。在相邻的两个数两两进行比较的过程中，如果前面的一个 数比后面一个数大，则把这两邻的两个数交换，也就是说，我们把较小的数放 在前面，把较大的数调到后面。即，如果在一次比较中，如果A1比A2大的情况下，把A1和A2交换，”以此类推，直到一轮AN-1和AN比较完。（2）再次重复（1），直到相邻两数之间不再发生交换为止。例如：一组待排序数列为：E E E E E E图3-1待排序组根

17、据算法思路（1）第一次对比后无变化；A2=8 A3=5, 所以两根据算法思路（1）第二次对比发生变化：由于者交换58图3-2第一次交换根据算法思路（1）第三次对比发生变化：由于A3=8 A4=4, 所以两者交换图3-3第二次交换根据算法思路（1）第四次对比无变化；根据算法思路（1）第五次对比发生变化：由于 A 5=9 A6=7 ，所有两 者交换叵叵E叵FJ图3-4第三次交换到此第一轮的排序结束，根据算法思路（2），重新对以交换排列后的数列进行排序直到没有变化为止，生成最后的序列:E E E E E E图3-5最后有序序列分析冒泡排序法的效率，若记录一开始就是从大到小排列，则一次循环就 能完成排

18、序；若记录是“逆序”排列的，即是冲小到大的排列，则需n-1次循环(n为需要排序的记录总数)，共n(n-1)/2次比较和交换。算法的负责度为03.2选择算法及思想选择排序算法的基本思想：每一趟(例如第i趟，i = 0, 1, ,n-2)在后面n-i个待排序对象中选出关键码最小的对象，作为有序对象序列的第i个对象。待到第n-2趟作完，待排序对象只剩下1个，就不用再选了。我们选择一种把最小的数放在第一个位置上的选择排序算法，其思想是先 并不急于调换位置，先从第一个数开始逐个向后扫描整个序列，看哪个数最小 就记下该数所在的位置，等一趟扫描完毕，再把第一个数和在他后面最小对调， 这时此无序序列中最小的数

19、据就换到了最前面的位置。算法的步骤如下：、先从A1开始向后检查，检查出在 A1后面的最小数的位子，我 们设此位子为AP。、依次把AP和AN (AN从1变化到N)进行比较，每次比较时，若AN的数比AP中的数小，则把N的值赋给P,使P总是指向当前所扫描过 的最小数的位置，也就是说 AP总是等于所有扫描过的数最小的那个数。在依 次比较后，P就指向N个数中最小的数所在位置，即 AP就是N个数中最小的那个数；、把AP和A1的数对调，那么最小的数就在 A1中去了，也就是 在最前面了。、重复此算法，但每重复一次，进行比较的数列范围就向后移动一个 位置。即第二遍比较时范围就从第 2个数一直到第N个数，在此范围

20、内找最小 的数的位置P,然后把AP与A2对调，这样从第2个数开始到第N个数中最 小数就在A2中了，第三遍就从第3个数到第N个数中去找最小的数，再把AP 与A3对调,此过程重复 N-1次后，就把A数组中N个数按从小到大的顺序 排好了。例如，一组待排数据为：E E E E E E图3-6待排序列根据选择排序算法思路（1）,从A1=6向后检查，发现最小的数为A4=4 ; 根据选择排序算法思路（2），把A1和A4进行比较，得出：A1=6 A4=4，所以把A4和A1对调，得到新的序列：4856图3-7第一次交换根据选择排序算法思路（3）:即从A2=8向后检查，从 A3-A6从找到最小的数 A3=5，把A

21、2=8 和A3=5进行比较，得出：A2=8 A3=5 ，所以把A2和A3对调0 0 0 0 0 0图3-8第二次交换重复选择排序算法思路（4）,直到上面的排序工作不再有交换为止，得到最后序列为：叵叵叵E叵叵图3-9最终序列分析选择排序算法效率，它实现的方式是：令 i从1到n-1，进行n-1次 选择操作。在选择排序算法的过程中，所需进行记录移动的造作次数比较少， 但是，无论记录的初始排列如何，所需进行记录关键字间的比较次数均为 n（n-1）/2。因此选择排序算法的复杂度为 0（n x n）.3.3快速算法及思想快速排序算法的基本思想：采用分而治之的办法对一个表进行排序，任取 待排序对象序列中的某

22、个对象（例如取第一个对象）作为基准，按照该对象的 关键码大小，将整个对象序列划分为左右两个子表 low和high :（1）左侧子序列low中所有对象的关键码都小于或等于基准对象的关键 码；（2）右侧子序列high中所有对象的关键码都大于或等于基准对象的关键 码。基准对象则排在这两个子序列中间。然后再按此方法对low和high两部分 数据分别进行快速排序，其整个过程可以递归进行，从而使整个数列变成有序 序列。假设要排序的数列为A1 ,AN,我们首先要取一个数据作为关键数据，一般情况下都是取第一个数据为关键数据。然后将所有小于它的数据放在它前 面，所有大于它的数放在它后面，这个过程就称为一趟快速排

23、序。算法的步骤 如下：（1） 、设置两个变量int=i ，j，在排序开始的时候，i=1,j=N ；（2）、以第一个数据为关键数据，定义为 key，即key=A1；（3） 、从变量j向前搜索，即由右至左的搜索（j:=j-1），找到小于key的 数据，两者交换；（4） 、从变量i向后搜索，即由左至右的搜索（i:=i+1），找到大于key的 数据，两者交换；（5）、重复排序步骤（3）和（4），直到i=j 0例如，一组待排序数据为：（设初始关键数据：key=50）| 50| 39| 66| 98| 76| 14| 28图3-10待排序列根据步骤（3）进行第一次交换后:（关键数据key=50和28发生交

24、换，此时j=6 ） 根据步骤（4）进行第二次交换后：图3-12第二次交换（关键数据key=50和66发生交换，此时i=4 ）根据步骤（5）将又一次执行算法（3）进行第三次交换:图3-13第三次交换（关键数据key=50和14发生交换，此时j=5）根据步骤（5）又将执行一次算法（4）进行第四次交换:图3-14第四次交换（关键数据key=50和98发生交换，此时i=5 ）此时我们可以看见j=i ，所以此时结束此趟快速排序。在经过这趟快速排 序后的结果是：图3-15第五次交换即所有大于初始关键数据“ 50”的数据全在其右边，所有小于初始关键数 据“50”的数据全部在其左边。以“ 50”为数轴，把原序

25、列分成了两子序列， 即：low28 39 14,high76 98 66,再递归的方法分别对前子表low和后子表high进行类似的快速排序，从而完成所有数据序列的快速排序，最后把原来这个无序的数据序列排列成为一组有序的序列：分析快速排序算法的效率，如果每次划分对一个对象定位后，该对象的左 侧子序列与右侧子序列的长度相同，则下一步将是对两个长度减半的子序列进 行排序，这是最理想的情况。在n个元素的序列中，对一个对象定位所需时间为0（n）。若设t（n）是对n个兀素的序列进行排序所需的时间，而且每次对一个对象正确定位后，正好把序列划分为长度相等的两个子序列，此时，总的计算时间为：T( n) cn +

26、 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)J J JCn Iog2n + nt(1) = o(n Iog2n )因此该算法的算法复杂度为0(n Iog2n )4详细设计4.1系统的文件的组织本系统所含文件的组织如图4-1所示：图4-1文件的组织4.2动态演示冒泡算法模块设计首先，本系统是在 Visual C+ 6.0 中文版下MFC环境下，设置的“ MFCAppWizard(exe) ”工程，工程名为：“tt ”。相关的ID如表

27、4_1,4_2所示表4-1为工程添加IDR MAINFRAM的菜单选项ID说明文字功能描述IDC_SORT_BUBBLE冒泡法排序冒泡法排序表4-2打开类向导(Class Wizard )对话框向视图类添加响应函数Object IDMessagesMessages的描述函数名IDC_SORT_BUBBLECOMMAND选择该菜单OnSortBubble表4-3通过类查看(ClassView )选项卡，向视图类添加成员变量变量类型变量名功能描述intm_SortBubbleN记录关键字CRectm_SortBubbleRect动态演示矩形范围BOOLIsSortBubbleTRUE表示进行冒泡排

28、序打开ttView.h头文件，在文件开始部分定义两个常量:设定排序的记录次数每次交换操作所耗每次比较操作所耗的时间 TOC o 1-5 h z #defi ne N 70II#defi ne DELAY 3II#defi ne DELAY1 1II并在其下声明冒泡排序的全局函数：UINT ThreadSortBubble(LPVOID Ip);由于开启多线程时，使用的都是全局函数，想要获得当前视图类中的数据， 并实时更新试图的显示，就必须获取当前试图对象。所以本系统要定义一个全 局指针，打开ttView.cpp构建函数中加入语句“ CTtView *pView ”用来获取当 前视图。然后，系统

29、在ttView.cpp 构建文件中添加实现冒泡排序算法的函数:ThreadSortBubble,代码为:UINT ThreadSortBubbIe(LPVOID Ip) int * data;int i,j,key;int tag;data=pView-m_SortBubbIe; for(i=0;ii;j-)if(datajdataj-1)key=dataj; dataj=dataj-1; dataj-1=key;Sleep(DELAY);pView-l nv alidate(TRUE); tag+;Sleep(DELAY1);if(tag=0) break;pView-l nv alidat

30、e(TRUE);return 0;在类中查看(Class View)选项，打开视图类CTtView，在其中修改构 建函数，实现变量初始化：CTtView:CTtView()int i;sran d( un sig ned)time(NULL);for(i=0;iN;i+)m_SortBubblei =0;pView=this;IsSortBubble=FALSE;为了让大家看清楚排序之间对比和交换的过程，修改响应函数 OnSortBubble ” ,产生0-70随即整数来进行排序：void CTtView:O nSortBubble()for(int i=0;iTextOut(250,200,

31、冒泡排序演示);/ for(i=0;iFillRect(&m _SortBubbleRect，&BlueBrush); _BlueBrush.DeleteObject();4.3动态演示选择算法模块设计表4-4为工程添加IDR MAINFRAM的菜单选项ID说明文字功能描述IDC_SORT_SELECT选择法排序选择法排序表4-5打开类向导(Class Wizard )对话框向视图类添加响应函数Object IDMessagesMessages的描述函数名IDC_SORT_SELECTCOMMAND选择该菜单OnSortSelect表4-6通过类查看(ClassView )选项卡，向视图类添加

32、成员变量变量类型变量名功能描述intm_SortSelectN记录关键字CRectm_SortSelectRect动态演示矩形范围BOOLIsSortSelectTRUE表示进行选择排序在TtView.h头文件，声明选择排序的全局函数:UINT ThreadSortSelect(LPVOID lp);然后，在TtView.cpp构建文件中添加实现选择排序算法的函数：ThreadSortSelect,代码为：UINT ThreadSortSelect(LPVOID lp)int i,j,key,tmp;int *data;data=pView-m_SortSelect;for(i=0;iN-1;

33、i+) key=i;for(j=i+1;jdatakey)key=j;pView-l nv alidate(TRUE);Sleep(DELAY1);Sleep(DELAY);tmp=datai;datai=datakey;datakey=tmp;Sleep(DELAY);pView-l nvalidate(TRUE);return 0;在类中查看(Class View)选项，打开视图类CTtView，在其中修改构 建函数，实现变量初始化：CTtView:CTtView()int i;sran d( un sig ned)time(NULL);for(i=0;iN;i+)m_SortSelect

34、i =0;pView=this;IsSortSelect=FALSE;修改响应函数“ OnSortSelect ” ,产生0-70随即整数来进行排序：void CTtView:O nSortSelect()for(int i=0;iTextOut(5O,2OO,选择排序演示); for(i=0;iFillRect(&m _SortSelectRect,&BlueBrush); _BlueBrush.DeleteObject();4.4动态演示快速算法模块设计表4-7为工程添加IDR MAINFRAM的菜单选项ID说明文字功能描述IDC_SORT_QUICK快速法排序快速法排序表4-8打开类向导

35、(Class Wizard )对话框向视图类添加响应函数Object IDMessagesMessages的描述函数名IDC_SORT_QUICKCOMMAND快速该菜单OnSortQuick表4-9通过类查看(ClassView )选项卡，向视图类添加成员变量变量类型变量名功能描述intm_SortQuickN记录关键字CRectm_SortQuickRect动态演示矩形范围BOOLIsSortQuickTRUE表示进行选择排序在TtView.h头文件，声明选择排序的全局函数: UINT ThreadSortQuick(LPVOID lp);void QuickSort(i nt * dat

36、a,i nt s,i nt t);在TtView.cpp 构建文件中添加实现快速排序算法的函数：ThreadSortSelect 和 Quicksort,代码为：void QuickSort(i nt * data,i nt low,i nt high)int i=low,j=high;int tmp,key;if(lowvhigh)tmp=datalow;while(ij)while(ij)if(datajl nv alidate(TRUE);while(i=tmp)i+;Sleep(DELAY1);elsebreak;key=datai;datai=dataj;dataj=key;Slee

37、p(DELAY);pView-l nv alidate(TRUE);QuickSort(data,low,i-1);QuickSort(data,i+1,high);UINT ThreadSortQuick(LPVOID lp)int * data;data=pView-m_SortQuick;pView-I nv alidate(TRUE);Sleep(DELAY);QuickSort(data,0,N-1);return 0;打开类(Class View)中视图类CTtView，在其中修改构建函数，实现变量初始化：CTtView:CTtView()int i;sran d( un sig

38、ned)time(NULL);for(i=0;iN;i+)m_SortQuicki =0;pView=this;IsSortQuick=FALSE;修改响应函数“ OnSortQuick ” ,产生0-70随即整数来进行排序：void CTtView:O nSortQuick()for(int i=0;iTextOut(45O,2OO,快速排序演示);/ for(i=0;iFillRect(&m _SortQuickRect,&BlueBrush); _BlueBrush.DeleteObject();4.5同时比较三种算法模块设计表4-10 为工程添加IDR MAINFRAM的菜单选项ID说

39、明文字功能描述IDC_SORT_ALL同时比较三种方法同时进行比较表4-11打开类向导（Class Wizard ）对话框向视图类添加响应函数Object IDMessagesMessages的描述函数名IDC_SORT_ALLCOMMAND快速该菜单OnSortAll同时比较这三种排序，就是同时调用这三种排序演示线程，修改响应函数On SortAll:void CTtView:O nSortAII()/ TODO: Add your comma nd han dler code hereOn SortBubble1();On SortQuick1();On SortSelect1();4.6

40、系统的测试每一个红色（同时排序的蓝色）的竖条都代表一个随即数（以下相同）(1)冒泡排序的动态演示开始冒泡排序的动态演示结束冒泡排序演示图4-3冒泡演示结束选择排序的动态演示结束冒泡排序演示图4-2冒泡演示开始选择排序的动态演示开始选择排序演示图4-5选择演示结束快速排序的动态演结束选择柠序演示图4-4选择演示开始快速排序的动态演示开始快速排序演示快速毎序演示图4-7快速演示结束图4-6快速演示开始同时演示三种排序，比较他们的排序过程的快慢开始序演示II1 IlliIlli lull1 11 llllllllh.图4-8同时比较三种排序开始第一个排序快速排序完毕。快速排序横示选择护序廣不图4-9快速排序结束第二个排序一一选择排序完毕。迭择楼序演示冒ia推序離示图4-10选择排序结束最后一个排序一一冒泡排序完毕快速梓序横示llllllllllllllllimin,.图4-11冒泡排序结束4.7系统的特点在运行本系统的时候，选择不同的菜单选项，能够清楚的看出各种排序过 程的变化，例如：选择“冒泡法排序”时，可以看见绿色的长条逐渐向左移动，完全验 证了冒泡排序算法的思想。选择“选择法排序”时，可以看见绿色的长条是被交换到左边的过程， 这个也完全证明了选择排序算法的思想。选择“快速法排序”时，可以看见整个序列在经过 i=j的过程后，被 分成了 2个子序列，再排列两