1 引言
1.1 系统背景
由于排序在计算机图形、计算机辅助设计、机器人、模式识别、基因排序工程及统计学等领域具有广泛应用,所以对排序的研究既有理论上的重要意义,又有实际应用价值。再加上现在信息产业的迅速发展,信息的流通量越来越大,如此庞大并且杂乱无章的信息数据十分难以管理和查询,就更加需要一种十分快捷而有效的编排手段来整理这些数据信息,让我们的工作效率得以提高。
1.2 系统开发的意义
在现代信息发达的今天,面对接受到大量的无序的信息,没有一个规则来编排和查询,会给我们的工作和信息交流带来十分的不便。因此,利用计算机的高速运用和计算能力,编写出一种合适的排序软件,能十分快捷的给我们在信息交流和查询带来便利。例如在互联网上为了使人们能够快速的访问和检索大量的信息,人们会运用许多快速并且优秀的算法对这些数据进行管理和操纵。优秀的算法还能帮助我们在互联网上快速找到最好的发送数据路线,以及怎么用搜索引擎来快速地找到信息所在的页面。
1.3 系统开发的相关技术
本系统利用Visual C++ 6.0作为开发平台,利用它的可视化界面,在其MFC环境下开发的一个演示三种不同排序算法,利用画刷画出三种不同的排序算法在排列随即产生的0-70个数的过程,并且能够对比这三种排序算法在相同的条件下,排序速率的快慢。运用VC编程语言,把一个程序中的算法和程序框架有效的结合起来,并且实现排序算法的动态演示。
1.4 系统开发的相关概念
首先我们要了解排序到底是什么?它的主要功能和目的是什么?简单的说,排序是利用一种算法,将一个无规则的序列排成一个有序序列的过程。而算法则是以一组值或者一个值的集合作为输入,经过一系列计算得到的一组值作为输出的过程,即是指那一系列将输入转化为输出的计算过程。
排序的方法有很多种,但是没有一种排序算法是通用的,即在任何情况下都能保持最快的排序速度。因此我们必须根据需要处理数据的特点来选择合适的算法。在排序的过程中,我们一般需要用到的两个基本操作步骤是:比较两个关键字的大小和将记录从一个位子移至另一个位子,即比较和交换。本系统设定的情况为,记录关键字都为整数,排序的结果是从大到小的排列,用到的三种排序算法为:冒泡排序法、选择排序法、快速排序法。
2 系统需求及分析
2.1 系统需求
本系统的硬件环境:CPU AMD 2800+,内存512M以上,硬盘80G以上。
本系统的软件环境:操作系统Windows XP,Visual C++ 6.0中文版。
2.2 系统开发环境选择
本系统运用的是Visual C++ 6.0中文版,它是微软公司开发出的一种集成开发环境,它拥有良好的可视化界面,它用来在Windows环境下开发应用程序,是一种功能强大、行之有效的可视化编程工具。在Visual C++ 6.0中能够进行多种操作,它的特点就是能够把原来抽象的数字、表格、功能逻辑等用直观的图形、图象的形式表现出来。排序算法本来就是一种抽象的逻辑功能,想要直观的把它演示出来,选择利用Visual C++ 6.0的可视化编程是非常明智的。而且本系统在开发过程中,能够用鼠标点击按钮和拖放图形化的对象,修改他们的属性和行为过程。这种可视化的编程方法简单、易学、易用,可以大大提高我们的工作效率。
2.3 系统的总体规划
本系统的总体结构如图2-1所示:
冒泡排序 |
选择排序 |
同时进行 |
动态演示排序系统 |
快速排序 |
3 系统设计思想
3.1 冒泡算法及思想
冒泡排序算法的基本思想:冒泡法的原理很简单,基本思想就是比较相临的两个记录的关键字,若前者比后者小则交换,若前者比后者大则保持不变。先将第一个记录与第二个记录比较,然后是第二个与第三个比较,直到倒数第二个与最后一个记录。比较一轮结束之后,关键字大的记录均向前移动。然后开始新一轮的比较,知道一轮比较下来,不再有记录的交换发生为止。整个过程就有点象水中的气泡上升的过程,轻的往上浮,重的向下沉,这个算法的名字也就由此得来。算法的步骤如下:
(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),直到相邻两数之间不再发生交换为止。
例如:一组待排序数列为:
SHAPE\* MERGEFORMAT
8 |
5 |
4 |
9 |
7 |
图3-1待排序组
根据算法思路(1)第一次对比后无变化;
根据算法思路(1)第二次对比发生变化:由于A[2]=8 > A[3]=5,所以两者交换
SHAPE\* MERGEFORMAT
5 |
8 |
4 |
9 |
7 |
图3-2第一次交换
根据算法思路(1)第三次对比发生变化:由于A[3]=8 > A[4]=4,所以两者交换
SHAPE\* MERGEFORMAT
5 |
4 |
8 |
9 |
7 |
图3-3第二次交换
根据算法思路(1)第四次对比无变化;
根据算法思路(1)第五次对比发生变化:由于A[5]=9 > A[6]=7,所有两者交换
SHAPE\* MERGEFORMAT
5 |
4 |
8 |
7 |
9 |
图3-4第三次交换
到此第一轮的排序结束,根据算法思路(2),重新对以交换排列后的数列进行排序直到没有变化为止,生成最后的序列:
SHAPE\* MERGEFORMAT
5 |
6 |
7 |
8 |
9 |
图3-5最后有序序列
分析冒泡排序法的效率,若记录一开始就是从大到小排列,则一次循环就能完成排序;若记录是“逆序”排列的,即是冲小到大的排列,则需n-1次循环(n为需要排序的记录总数),共n(n-1)/2次比较和交换。算法的负责度为O(n×n).
3.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个数按从小到大的顺序排好了。
例如,一组待排数据为:
SHAPE\* MERGEFORMAT
8 |
5 |
4 |
9 |
7 |
图3-6待排序列
根据选择排序算法思路(1),从A[1]=6向后检查,发现最小的数为A[4]=4;
根据选择排序算法思路(2),把A[1]和A[4]进行比较,得出:A[1]=6 > A[4]=4,所以把A[4]和A[1]对调,得到新的序列:
SHAPE\* MERGEFORMAT
8 |
5 |
6 |
9 |
7 |
图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]对调
不动 |
5 |
8 |
6 |
9 |
7 |
图3-8第二次交换
……
重复选择排序算法思路(4),直到上面的排序工作不再有交换为止,得到最后序列为:
SHAPE\* MERGEFORMAT
5 |
6 |
7 |
8 |
9 |
图3-9最终序列
分析选择排序算法效率,它实现的方式是:令i从1到n-1,进行n-1次选择操作。在选择排序算法的过程中,所需进行记录移动的造作次数比较少,但是,无论记录的初始排列如何,所需进行记录关键字间的比较次数均为n(n-1)/2。因此选择排序算法的复杂度为O(n×n).
3.3 快速算法及思想
快速排序算法的基本思想:采用分而治之的办法对一个表进行排序,任取待排序对象序列中的某个对象(例如取第一个对象)作为基准,按照该对象的关键码大小,将整个对象序列划分为左右两个子表-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)
SHAPE\* MERGEFORMAT
39 |
66 |
98 |
76 |
14 |
28 |
图3-10待排序列
根据步骤(3)进行第一次交换后:
SHAPE\* MERGEFORMAT
39 |
66 |
98 |
76 |
14 |
50 |
图3-11第一次交换
(关键数据key=50和28发生交换,此时j=6)
根据步骤(4)进行第二次交换后:
SHAPE\* MERGEFORMAT
39 |
50 |
98 |
76 |
14 |
66 |
图3-12第二次交换
(关键数据key=50和66发生交换,此时i=4)
根据步骤(5)将又一次执行算法(3)进行第三次交换:
SHAPE\* MERGEFORMAT
39 |
14 |
98 |
76 |
50 |
66 |
图3-13第三次交换
(关键数据key=50和14发生交换,此时j=5)
根据步骤(5)又将执行一次算法(4)进行第四次交换:
SHAPE\* MERGEFORMAT
39 |
14 |
50 |
76 |
98 |
66 |
图3-14第四次交换
(关键数据key=50和98发生交换,此时i=5)
此时我们可以看见j=i,所以此时结束此趟快速排序。在经过这趟快速排序后的结果是:
SHAPE\* MERGEFORMAT
39 |
14 |
50 |
76 |
98 |
66 |
图3-15第五次交换
即所有大于初始关键数据“50”的数据全在其右边,所有小于初始关键数据“50”的数据全部在其左边。以“50”为数轴,把原序列分成了两子序列,即:low{28 39 14},high{76 98 66},再递归的方法分别对前子表low和后子表high进行类似的快速排序,从而完成所有数据序列的快速排序,最后把原来这个无序的数据序列排列成为一组有序的序列:
SHAPE\* MERGEFORMAT
28 |
39 |
50 |
66 |
76 |
98 |
图3-16最终序列
分析快速排序算法的效率,如果每次划分对一个对象定位后,该对象的左侧子序列与右侧子序列的长度相同,则下一步将是对两个长度减半的子序列进行排序,这是最理想的情况。在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.1 系统的文件的组织
本系统所含文件的组织如图4-1所示:
图4-1文件的组织 |
添加新的菜单资源 |
创建视图框类 |
添加菜单响应函数 |
添加菜单中成员变量 |
源文件 |
添加全局指针 |
添加算法函数代码 |
修改构建函数实现演示 |
头文件 |
添加定义常量 |
添加全局函数 |