计算机课程设计说明说.doc

南 京 理 工 大 学课程设计报告作 者:张琦学 号：8教学点:苏州市职业大学专 业:机电一体化工程题 目:冒泡排序指导者： 评阅者： 2013年 4月南 京 理 工 大 学课程设计报告评语综合成绩： 指导者评语： 指导者(签字)： 年 月 日课 程 设 计 报 告 摘 要摘要：冒泡排序，是指计算机的一种排序方法。冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。本程序采用Microsoft Visual C+ 6.0调试。该排序方法也有一些不足的地方。关键词： 冒泡排序 比较 调试 排序目 次1 引言 12 冒泡排序的实现 12.1 冒泡排序的基本概念 12.2 冒泡排序引例 12.3冒泡排序的流程图及程序代码 23 冒泡排序的调试 43.1 冒泡排序的调试方法 43.2 程序调试 54 冒泡排序的性能分析 64.1 时间复杂度 64.2 空间复杂度 74.3 稳定性 75 冒泡排序的不足 7结论 9致谢 10参考文献11附录A 131 引言在许多程序设计中，我们需要将一个数列进行排序，以方便统计，而冒泡排序一直由于其简洁的思想方法而倍受青睐冒泡排序，是指计算机的一种排序方法，它的时间复杂度为O（n2），虽然不及堆排序、快速排序，但是有两个优点：1.“编程复杂度”很低，很容易写出代码；2.具有稳定性，这里的稳定性是指原序列中相同元素的相对顺序仍然保持到排序后的序列，而堆排序、快速排序均不具有稳定性。不过，一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快，且具有稳定性，但速度不及堆排序、快速排序。冒泡排序是经过n-1趟子排序完成的，第i趟子排序从第1个数至第n-i个数，若第i个数比后一个数大（则升序，小则降序）则交换两数。因为冒泡排序方法简单，所以得到广泛应用。2 冒泡排序的实现21 冒泡排序的基本概念冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。用二重循环实现，外循环变量设为i，内循环变量设为j。假如有10个数需要进行排序，则外循环重复9次，内循环依次重复9，8，.，1次。每次进行比较的两个元素都是与内循环j有关的，它们可以分别用aj和aj+1标识，i的值依次为1,2,.,9，对于每一个i和j的值依次为1,2,.10-i。22 冒泡排序引例将9,5,2,4四个数用冒泡排序方法进行排序。先把四个数依次存入R1.4数组中，具体排序过程如下图所示：图一第一趟结果：5 2 4 9 最大数9在R4中。图二第二趟结果：2 4 5 9 第二大数数5在R3。图三第一趟结果：5 2 4 9 第三大数4在R2中.以上第一趟比较结果出来一个最大数9，发表放在R4中；第二趟出来次大树5，放在R3中，；四个数进行三趟。其比较过程为相邻两数比较，小的浮上去，大的沉下来。23 冒泡排序的流程图及程序代码2.3.1 冒泡排序的流程图根据冒泡排序的排序过程可得如下的程序流程图：图四2.3.2 冒泡排序的程序本程序的编写采用调用子函数的方法，先定义一个子函数Bubble_Sort(n)实现冒泡排序的功能，在主函数中输入要排序的数字，在调用子函数后实现数字的排序。#include <stdio.h>#define MAX 255#define clrscr()#define exit#define getch()int aMAX;void Bubble_Sort(int n) /* a (1.n)是带排序的文件，采用自下向上扫描，对a做冒泡排序*/ int i,j; int exchange; /*交换标志*/ for (i=1;i<n;i+) /*最多做n-1趟排序*/ exchange=0; /*本趟排序前，交换标志应为假*/ for(j=n-1;j>=i;j-) /*对当前无序区ai.n自下向上扫描*/ if(aj+1<aj) /*交换记录*/ a0=aj+1; /*a0不是哨兵，仅做暂存单元*/ aj+1=aj; aj=a0; exchange=1; /*发生了交换，故将交换标志置为真*/ if(!exchange)/*本趟排序未发生交换，提前终止算法*/ return;void main() int i,n; clrscr(); puts("Please input total element number of the sequence:"); scanf("%d",&n);if(n<=0|n>MAX) printf("n must more then 0 and less then %d.n",MAX); exit(0);puts("please input the elemengt one by one:");for(i=1;i<=n;i+) scanf("%d",&ai);puts("the sequence you input is:");for(i=1;i<=n;i+) printf("%4d",ai);Bubble_Sort(n);puts("nThe sequence after bubble_sort is:");for(i=1;i<=n;i+) printf("%4d",ai);puts("n Press any key to quit");getch();3 冒泡排序的调试31 冒泡排序的调试方法本程序采用Microsoft Visual C+ 6.0调试，首先打开软件，新建一个C+ source file 文件，输入文件名称，选择合适的文件目录。如图所示：图五新建好文件后，开始编辑程序，然后点击组建编译，如出现错误可按F4查找错误，修改至无错误位置，可有警告。程序检查无错误就可点击运行程序。图六32 调试过程按照上面的调试方法运行程序后，首先要输入的排序数据的总个数。图七输入相应的数字（例如 5 ）后显示的是图八依次输入5个数，每隔一个输入一个空格，待5个数输入完成后点击回车确定。第一行显示的是输入的顺序，第二行显示的排完顺序的一串数字，如输入2，38,5,47，50五个数。图九4 冒泡排序的性能分析41 时间复杂度一般情况下冒泡排序的时间复杂度为O（n*n）。但当排序的数完全正序的时候，n个数只进行一趟，比较n-1次，其时间复杂度为O(n)，这是冒泡排序的最好情况。比如将2,4,6,8,10五个数用冒泡排序，只进行一趟，比较四次，不发生数据交换，排序就结束了。42 空间复杂度和直接插入排序一样，不管有待排序数n有多大，辅助空间只需要一个m，用于两数交换运算，因此，冒泡排序的空间复杂度也为O（1）。42 稳定性从程序可以看出，当aj>aj+1时才交换，若相等则不交换，因此，冒泡排序是稳定的排序。综上所述，冒泡排序的基本思想是：相邻关键字进行比较，不合适就交换。因为冒泡排序方法简单，所以得到广泛应用。5 冒泡排序的不足冒泡排序法存在的不足及改进方法：第一，在排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法判断是否完成排序，为了解决这一不足，可设置一个标志位flag，将其初始值设置为非0，表示被排序的表是一个无序的表，每一次排序开始前设置flag值为0，在进行数据交换时，修改flag为非0。在新一轮排序开始时，检查此标志，若此标志为0，表示上一次没有做过交换数据，则结束排序；否则进行排序；第二，当排序的数据比较多时排序的时间会明显延长。改进方法：快速排序：具体做法：任意选取某一记录（通常取第一个记录），比较其关键字与所有记录的关键字，并将关键字比它小的记录全部放在它的前面，将比它大的记录均存放在它的后面，这样，经过一次排序之后，可将所有记录以该记录所在的分界点分为两部分，然后分别对这两部分进行快速排序，直至排序完局部冒泡排序算法对冒泡排序的改进：在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或多次数据交换，在传统的冒泡排序算法及近年来的一些改进的算法中，只记录一趟扫描有无数据交换的信息，对数据交换发生的位置信息则不予处理。为了充分利用这一信息，可以在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。局部冒泡排序与冒泡排序算法具有相同的时间复杂度，并且在正序和逆序的情况下，所需的关键字的比较次数和移动次数完全相同。由于局部冒泡排序和冒泡排序的数据移动次数总是相同的，而局部冒泡排序所需关键字的比较次数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改进，当比较次数较少的优点不足以抵消其程序复杂度所带来的额外开销，而当数据量较大时，局部冒泡排序的时间性能则明显优于冒泡排序。结 论通过了这一次的课程设计，更加详细的了解了冒泡排序的排序方法，从它最开始的基本概念到流程图的设计设计，程序的编写，最后到程序的调试，系统的掌握了冒泡排序的操作以及程序思路。由于几种排序的方法大同小异，所以在这次课程设计之后，对于其他的几种排序方法也有了更加深刻的了解。计算机软件在现代社会已近得到了最广泛的利用，对于我们学生来说，掌握必要的计算机软件基础知识是必不可少的。学完这门课后我们对计算机软件基础料了解了更多的知识，对计算机软件业有了更多的了解，这对我们以后的发展有了很大的帮助。致 谢这篇论文的完成离不开老师和同学的支持，感谢老师的细心指导，在论文的排版上感谢老师的意见，才使得这篇论文排版如此的整齐。在流程图的绘制以及程序的编写时，遇到困难难以继续，在同学的热心帮助下，我找到了相应的参考书，在参考书上我发现了解决困难的方法，才能继续书写论文。也感谢舍友细心的帮我核查，改掉其他的细小毛病。最后感谢南京理工大学能给我这次机会，让我学到更多的知识，也感谢苏州市职业大学对我的教育和指导。参 考 文 献1 宁正元，王秀丽.算法与数据的结构，2006：29322 杨辉.杨辉的纵横图论，2003：12143 唐王希.太乙金镜式经，2000：35374 王力柱。c/c+与数据结构。栈，2003（8）：1421525 徐孝凯，贺桂英。数据结构。栈和队列，2004（10）：76926 吴乃陵，李海文。c+程序设计。栈，2003（8）：8087 ，2632707 陈媛，何波，涂晓江，涂飞。算法与数据结构。栈，2005（4）8 张勇，刘君仪。数据结构。栈，2006（8）：961079 王挺，周会平。c+程序设计。2005（1）：3038 10严蔚敏，吴伟民。数据结构。北京：清华大学出版社，2001附录A：程序代码：#include <stdio.h>#define MAX 255#define clrscr()#define exit#define getch()int aMAX;void Bubble_Sort(int n) /* a (1.n)是带排序的文件，采用自下向上扫描，对R做冒泡排序*/ int i,j; int exchange; /*交换标志*/ for (i=1;i<n;i+) /*最多做n-1趟排序*/ exchange=0; /*本趟排序前，交换标志应为假*/ for(j=n-1;j>=i;j-) /*对当前无序区Ri.n自下向上扫描*/ if(aj+1<aj) /*交换记录*/ a0=aj+1; /*R0不是哨兵，仅做暂存单元*/ aj+1=aj; aj=a0; exchange=1; /*发生了交换，故将交换标志置为真*/ if(!exchange)/*本趟排序未发生交换，提前终止算法*/ return;void main() int i,n; clrscr(); puts("Please input total element number of the sequence:"); scanf("%d",&n);if(n<=0|n>MAX) printf("n must more then 0 and less then %d.n",MAX); exit(0);puts("please input the elemengt one by one:");for(i=1;i<=n;i+) scanf("%d",&ai);puts("the sequence you input is:");for(i=1;i<=n;i+) printf("%4d",ai);Bubble_Sort(n);puts("nThe sequence after bubble_sort is:");for(i=1;i<=n;i+) printf("%4d",ai);puts("n Press any key to quit");getch();