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

　　PAGE 毕业设计(论文) 多种排序算法动态演示软件的设计与开发 论文作者姓名： 申请学位专业： 申请学位类别： 指导教师姓名（职称）： 论文提交日期： 多种排序算法动态演示软件的设计与开发 摘 要 随着计算机科学技术的不断提高和发展，其强大的运算功能已经逐渐融入人类社会的各个领域，并且在各个领域中发挥越来越重要的作用。当然，高效的运算速度并不代表无限快，在有限的资源空间里，要大大提高运算处理数据的速率，就需要我们使用那些在时间和空间上体现出高效的算法。本系统是为了演示在同一问题上，不同的算法在效率上存在的巨大差异。本系统采用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页 TOC \o 1-3 \h \z \u 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 第 PAGE 1 页 共 21 页 引言 系统背景 由于排序在计算机图形、计算机辅助设计、机器人、模式识别、基因排序工程及统计学等领域具有广泛应用，所以对排序的研究既有理论上的重要意义，又有实际应用价值。再加上现在信息产业的迅速发展，信息的流通量越来越大，如此庞大并且杂乱无章的信息数据十分难以管理和查询，就更加需要一种十分快捷而有效的编排手段来整理这些数据信息，让我们的工作效率得以提高。 系统开发的意义 在现代信息发达的今天，面对接受到大量的无序的信息，没有一个规则来编排和查询，会给我们的工作和信息交流带来十分的不便。因此，利用计算机的高速运用和计算能力，编写出一种合适的排序软件，能十分快捷的给我们在信息交流和查询带来便利。例如在互联网上为了使人们能够快速的访问和检索大量的信息，人们会运用许多快速并且优秀的算法对这些数据进行管理和操纵。优秀的算法还能帮助我们在互联网上快速找到最好的发送数据路线，以及怎么用搜索引擎来快速地找到信息所在的页面。 系统开发的相关技术 本系统利用Visual C++ 6.0作为开发平台，利用它的可视化界面，在其MFC环境下开发的一个演示三种不同排序算法，利用画刷画出三种不同的排序算法在排列随即产生的0-70个数的过程，并且能够对比这三种排序算法在相同的条件下，排序速率的快慢。运用VC编程语言，把一个程序中的算法和程序框架有效的结合起来，并且实现排序算法的动态演示。 系统开发的相关概念 首先我们要了解排序到底是什么？它的主要功能和目的是什么？简单的说，排序是利用一种算法，将一个无规则的序列排成一个有序序列的过程。而算法则是以一组值或者一个值的集合作为输入，经过一系列计算得到的一组值作为输出的过程，即是指那一系列将输入转化为输出的计算过程。 排序的方法有很多种，但是没有一种排序算法是通用的，即在任何情况下都能保持最快的排序速度。因此我们必须根据需要处理数据的特点来选择合适的算法。在排序的过程中，我们一般需要用到的两个基本操作步骤是：比较两个关键字的大小和将记录从一个位子移至另一个位子，即比较和交换。本系统设定的情况为，记录关键字都为整数，排序的结果是从大到小的排列，用到的三种排序算法为：冒泡排序法、选择排序法、快速排序法。 系统需求及分析 系统需求 本系统的硬件环境：CPU AMD 2800+，内存512M以上，硬盘80G以上。 本系统的软件环境：操作系统Windows XP,Visual C++ 6.0中文版。 系统开发环境选择 本系统运用的是Visual C++ 6.0中文版，它是微软公司开发出的一种集成开发环境，它拥有良好的可视化界面，它用来在Windows环境下开发应用程序，是一种功能强大、行之有效的可视化编程工具。在Visual C++ 6.0中能够进行多种操作，它的特点就是能够把原来抽象的数字、表格、功能逻辑等用直观的图形、图象的形式表现出来。排序算法本来就是一种抽象的逻辑功能，想要直观的把它演示出来，选择利用Visual C++ 6.0的可视化编程是非常明智的。而且本系统在开发过程中，能够用鼠标点击按钮和拖放图形化的对象，修改他们的属性和行为过程。这种可视化的编程方法简单、易学、易用，可以大大提高我们的工作效率。 系统的总体规划 本系统的总体结构如图 2-1所示： 动态演示排序系统 动态演示排序系统 同时进行冒泡排序选择排序快速排序 同时进行 冒泡排序 选择排序 快速排序 图2-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），直到相邻两数之间不再发生交换为止。 例如：一组待排序数列为： 6 6 8 5 4 9 7 图3-1 待排序组 根据算法思路（1）第一次对比后无变化； 根据算法思路（1）第二次对比发生变化：由于A[2]=8
　　A[3]=5,所以两者交换 6 6 5 8 4 9 7 图3-2 第一次交换 根据算法思路（1）第三次对比发生变化：由于A[3]=8
　　A[4]=4,所以两者交换 6 6 5 4 8 9 7 图3-3第二次交换 根据算法思路（1）第四次对比无变化； 根据算法思路（1）第五次对比发生变化：由于A[5]=9
　　A[6]=7，所有两者交换 6 6 5 4 8 7 9 图3-4第三次交换 到此第一轮的排序结束，根据算法思路（2），重新对以交换排列后的数列进行排序直到没有变化为止，生成最后的序列： 4 4 5 6 7 8 9 图3-5最后有序序列 分析冒泡排序法的效率，若记录一开始就是从大到小排列，则一次循环就能完成排序；若记录是“逆序”排列的，即是冲小到大的排列，则需n-1次循环（n为需要排序的记录总数），共n(n-1)/2次比较和交换。算法的负责度为O（n × n）. 选择算法及思想 选择排序算法的基本思想：每一趟 (例如第 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个数按从小到大的顺序排好了。 例如，一组待排数据为： 6 6 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]对调，得到新的序列： 4 4 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]对调 不动4 不动 4 5 8 6 9 7 图3-8第二次交换 …… 重复选择排序算法思路（4）,直到上面的排序工作不再有交换为止，得到最后序列为： 4 4 5 6 7 8 9 图3-9最终序列 分析选择排序算法效率，它实现的方式是：令i从1到n-1，进行n-1次选择操作。在选择排序算法的过程中，所需进行记录移动的造作次数比较少，但是，无论记录的初始排列如何，所需进行记录关键字间的比较次数均为n(n-1)/2。因此选择排序算法的复杂度为O(n × n). 快速算法及思想 快速排序算法的基本思想：采用分而治之的办法对一个表进行排序，任取待排序对象序列中的某个对象（例如取第一个对象）作为基准，按照该对象的关键码大小，将整个对象序列划分为左右两个子表－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） 50 50 39 66 98 76 14 28 图3-10待排序列 根据步骤（3）进行第一次交换后： 28 28 39 66 98 76 14 50 图3-11第一次交换 （关键数据key=50和28发生交换，此时j=6） 根据步骤（4）进行第二次交换后： 2839 28 39 50 98 76 14 66 图3-12第二次交换 （关键数据key=50和66发生交换，此时i=4） 根据步骤（5）将又一次执行算法（3）进行第三次交换： 28 28 39 14 98 76 50 66 图3-13第三次交换 （关键数据key=50和14发生交换，此时j=5） 根据步骤（5）又将执行一次算法（4）进行第四次交换： 28 28 39 14 50 76 98 66 图3-14第四次交换 （关键数据key=50和98发生交换，此时i=5） 此时我们可以看见j=i，所以此时结束此趟快速排序。在经过这趟快速排序后的结果是： 28 28 39 14 50 76 98 66 图3-15第五次交换 即所有大于初始关键数据“50”的数据全在其右边，所有小于初始关键数据“50”的数据全部在其左边。以“50”为数轴，把原序列分成了两子序列，即：low{28 39 14},high{76 98 66},再递归的方法分别对前子表low和后子表high进行类似的快速排序，从而完成所有数据序列的快速排序，最后把原来这个无序的数据序列排列成为一组有序的序列： 14 14 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-1所示： 图4-1 文件的组织 图4-1 文件的组织 创建视图框资源 添加新的菜单资源 创建视图框类 添加菜单响应函数 添加菜单中成员变量 源文件 添加全局指针 添加算法函数代码 修改构建函数实现演示 头文件 添加定义常量 添加全局函数 动态演示冒泡算法模块设计 首先，本系统是在Visual C++ 6.0中文版下MFC 环境下，设置的“MFC AppWizard(exe)”工程，工程名为:“tt”。相关的ID如表4_1,4_2所示 表4-1 为工程添加IDR_MAINFRAME的菜单选项 ID 说明文字 功能描述 IDC_SORT_BUBBLE 冒泡法排序 冒泡法排序 表4-2 打开类向导（Class Wizard）对话框向视图类添加响应函数 Object ID Messages Messages的描述 函数名 IDC_SORT_BUBBLE COMMAND 选择该菜单 OnSortBubble 表4-3 通过类查看（ClassView）选项卡，向视图类添加成员变量 变量类型 变量名 功能描述 int m_SortBubble[N] 记录关键字 CRect m_SortBubbleRect 动态演示矩形范围 BOOL IsSortBubble 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-
　　i;j--) { if(data[j]
　　data[j-1]) { 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 =0; pview=this; issortbubble=false; } 为了让大家看清楚排序之间对比和交换的过程，修改响应函数“onsortbubble”,产生0-70随即整数来进行排序： void cttview::onsortbubble() { for(int i=0;i
　　data[key]) { key=j; pView-
　　Invalidate(TRUE); } Sleep(DELAY1); } Sleep(DELAY); tmp=data; data=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
　　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 =0; pview=this; issortquick=false; } 修改响应函数“onsortquick”,产生0-70随即整数来进行排序： void cttview::onsortquick() { for(int i=0;i
　　A[3]=5,所以两者交换 6 6 5 8 4 9 7 图3-2 第一次交换 根据算法思路（1）第三次对比发生变化：由于A[3]=8
　　A[4]=4,所以两者交换 6 6 5 4 8 9 7 图3-3第二次交换 根据算法思路（1）第四次对比无变化； 根据算法思路（1）第五次对比发生变化：由于A[5]=9
　　A[6]=7，所有两者交换 6 6 5 4 8 7 9 图3-4第三次交换 到此第一轮的排序结束，根据算法思路（2），重新对以交换排列后的数列进行排序直到没有变化为止，生成最后的序列： 4 4 5 6 7 8 9 图3-5最后有序序列 分析冒泡排序法的效率，若记录一开始就是从大到小排列，则一次循环就能完成排序；若记录是“逆序”排列的，即是冲小到大的排列，则需n-1次循环（n为需要排序的记录总数），共n(n-1)/2次比较和交换。算法的负责度为O（n × n）. 选择算法及思想 选择排序算法的基本思想：每一趟 (例如第 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个数按从小到大的顺序排好了。 例如，一组待排数据为： 6 6 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]对调，得到新的序列： 4 4 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]对调 不动4 不动 4 5 8 6 9 7 图3-8第二次交换 …… 重复选择排序算法思路（4）,直到上面的排序工作不再有交换为止，得到最后序列为： 4 4 5 6 7 8 9 图3-9最终序列 分析选择排序算法效率，它实现的方式是：令i从1到n-1，进行n-1次选择操作。在选择排序算法的过程中，所需进行记录移动的造作次数比较少，但是，无论记录的初始排列如何，所需进行记录关键字间的比较次数均为n(n-1)/2。因此选择排序算法的复杂度为O(n × n). 快速算法及思想 快速排序算法的基本思想：采用分而治之的办法对一个表进行排序，任取待排序对象序列中的某个对象（例如取第一个对象）作为基准，按照该对象的关键码大小，将整个对象序列划分为左右两个子表－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） 50 50 39 66 98 76 14 28 图3-10待排序列 根据步骤（3）进行第一次交换后： 28 28 39 66 98 76 14 50 图3-11第一次交换 （关键数据key=50和28发生交换，此时j=6） 根据步骤（4）进行第二次交换后： 2839 28 39 50 98 76 14 66 图3-12第二次交换 （关键数据key=50和66发生交换，此时i=4） 根据步骤（5）将又一次执行算法（3）进行第三次交换： 28 28 39 14 98 76 50 66 图3-13第三次交换 （关键数据key=50和14发生交换，此时j=5） 根据步骤（5）又将执行一次算法（4）进行第四次交换： 28 28 39 14 50 76 98 66 图3-14第四次交换 （关键数据key=50和98发生交换，此时i=5） 此时我们可以看见j=i，所以此时结束此趟快速排序。在经过这趟快速排序后的结果是： 28 28 39 14 50 76 98 66 图3-15第五次交换 即所有大于初始关键数据“50”的数据全在其右边，所有小于初始关键数据“50”的数据全部在其左边。以“50”为数轴，把原序列分成了两子序列，即：low{28 39 14},high{76 98 66},再递归的方法分别对前子表low和后子表high进行类似的快速排序，从而完成所有数据序列的快速排序，最后把原来这个无序的数据序列排列成为一组有序的序列： 14 14 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-1所示： 图4-1 文件的组织 图4-1 文件的组织 创建视图框资源 添加新的菜单资源 创建视图框类 添加菜单响应函数 添加菜单中成员变量 源文件 添加全局指针 添加算法函数代码 修改构建函数实现演示 头文件 添加定义常量 添加全局函数 动态演示冒泡算法模块设计 首先，本系统是在Visual C++ 6.0中文版下MFC 环境下，设置的“MFC AppWizard(exe)”工程，工程名为:“tt”。相关的ID如表4_1,4_2所示 表4-1 为工程添加IDR_MAINFRAME的菜单选项 ID 说明文字 功能描述 IDC_SORT_BUBBLE 冒泡法排序 冒泡法排序 表4-2 打开类向导（Class Wizard）对话框向视图类添加响应函数 Object ID Messages Messages的描述 函数名 IDC_SORT_BUBBLE COMMAND 选择该菜单 OnSortBubble 表4-3 通过类查看（ClassView）选项卡，向视图类添加成员变量 变量类型 变量名 功能描述 int m_SortBubble[N] 记录关键字 CRect m_SortBubbleRect 动态演示矩形范围 BOOL IsSortBubble 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-
　　i;j--) { if(data[j]
　　data[j-1]) { 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 =0; pview=this; issortbubble=false; } 为了让大家看清楚排序之间对比和交换的过程，修改响应函数“onsortbubble”,产生0-70随即整数来进行排序： void cttview::onsortbubble() { for(int i=0;i
　　data[key]) { key=j; pView-
　　Invalidate(TRUE); } Sleep(DELAY1); } Sleep(DELAY); tmp=data; data=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
　　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 =0; pview=this; issortquick=false; } 修改响应函数“onsortquick”,产生0-70随即整数来进行排序： void cttview::onsortquick() { for(int i=0;i