计算机专业课程设计项目说明说.doc

南 京 理 工 大 学课程设计汇报作 者:张琦学 号：教学点:苏州市职业大学专 业:机电一体化工程题 目:冒泡排序指导者： 评阅者： 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 #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=i;j-) /*对目前无序区ai.n自下向上扫描*/ if(aj+1aj) /*交换统计*/ 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(nMAX) 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;iaj+1时才交换，若相等则不交换，所以，冒泡排序是稳定排序。总而言之，冒泡排序基础思想是：相邻关键字进行比较，不适宜就交换。因为冒泡排序方法简单，所以得到广泛应用。5 冒泡排序不足冒泡排序法存在不足及改善方法：第一，在排序过程中，实施完最终排序后，即使数据已全部排序完备，但程序无法判定是否完成排序，为了处理这一不足，可设置一个标志位flag，将其初始值设置为非0，表示被排序表是一个无序表，每一次排序开始前设置flag值为0，在进行数据交换时，修改flag为非0。在新一轮排序开始时，检验此标志，若此标志为0，表示上一次没有做过交换数据，则结束排序；不然进行排序；第二，当排序数据比较多时排序时间会显著延长。改善方法：快速排序：具体做法：任意选择某一统计（通常取第一个统计），比较其关键字和全部统计关键字，并将关键字比它小统计全部放在它前面，将比它大统计均存放在它后面，这么，经过一次排序以后，可将全部统计以该统计所在分界点分为两部分，然后分别对这两部分进行快速排序，直至排序完局部冒泡排序算法对冒泡排序改善：在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或数次数据交换，在传统冒泡排序算法及多年来部分改善算法中，只统计一趟扫描有没有数据交换信息，对数据交换发生位置信息则不予处理。为了充足利用这一信息，能够在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。局部冒泡排序和冒泡排序算法含有相同时间复杂度，而且在正序和逆序情况下，所需关键字比较次数和移动次数完全相同。因为局部冒泡排序和冒泡排序数据移动次数总是相同，而局部冒泡排序所需关键字比较次数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改善，当比较次数较少优点不足以抵消其程序复杂度所带来额外开销，而当数据量较大时，局部冒泡排序时间性能则显著优于冒泡排序。结 论经过了这一次课程设计，愈加具体了解了冒泡排序排序方法，从它最开始基础概念到步骤图设计设计，程序编写，最终到程序调试，系统掌握了冒泡排序操作和程序思绪。因为多个排序方法大同小异，所以在这次课程设计以后，对于其它多个排序方法也有了愈加深刻了解。计算机软件在现代社会已近得到了最广泛利用，对于我们学生来说，掌握必需计算机软件基础知识是必不可少。学完这门课后我们对计算机软件基础料了解了更多知识，对计算机软件业有了更多了解，这对我们以后发展有了很大帮助。致 谢这篇论文完成离不开老师和同学支持，感谢老师细心指导，在论文排版上感谢老师意见，才使得这篇论文排版如此整齐。在步骤图绘制和程序编写时，碰到困难难以继续，在同学热心帮助下，我找到了对应参考书，在参考书上我发觉了处理困难方法，才能继续书写论文。也感谢舍友细心帮我核查，改掉其它细小毛病。最终感谢南京理工大学能给我这次机会，让我学到更多知识，也感谢苏州市职业大学对我教育和指导。参 考 文 献1 宁正元，王秀丽.算法和数据结构，：29322 杨辉.杨辉纵横图论，：12143 唐王希.太乙金镜式经，：35374 王力柱。c/c+和数据结构。栈，（8）：1421525 徐孝凯，贺桂英。数据结构。栈和队列，（10）：76926 吴乃陵，李海文。c+程序设计。栈，（8）：8087 ，2632707 陈媛，何波，涂晓江，涂飞。算法和数据结构。栈，（4）8 张勇，刘君仪。数据结构。栈，（8）：961079 王挺，周会平。c+程序设计。（1）：3038 10严蔚敏，吴伟民。数据结构。北京：清华大学出版社，附录A：程序代码：#include #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=i;j-) /*对目前无序区Ri.n自下向上扫描*/ if(aj+1aj) /*交换统计*/ 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(nMAX) 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();