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

南 京 理 工 大 学
课程设计汇报

作 者:
张琦
学 号：

教学点:
苏州市职业大学
专 业:
机电一体化工程
题 目:
冒泡排序

指导者：

评阅者：

4月

南 京 理 工 大 学
课程设计汇报评语

综合成绩：

指导者评语：

指导者(签字)：
年 月 日

课 程 设 计 报 告 摘 要

摘要：冒泡排序，是指计算机一个排序方法。冒泡排序基础概念是：依次比较相邻两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最终两个数，将小数放前，大数放后。至此第一趟结束，将最大数放到了最终。在第二趟：仍从第一对数开始比较（因为可能因为第2个数和第3个数交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一位置上已经是最大），第二趟结束，在倒数第二位置上得到一个新最大数（其实在整个数列中是第二大数）。如此下去，反复以上过程，直至最终完成排序。本程序采取Microsoft Visual C++ 6.0调试。
该排序方法也有部分不足地方。

关键词： 冒泡排序 比较 调试 排序

目 次

1 引言……………………………………………………………………………… 1
2 冒泡排序实现 ………………………………………………………………… 1
2.1 冒泡排序基础概念 ………………………………………………………… 1
2.2 冒泡排序引例………………………………………………………………… 1
2.3冒泡排序步骤图及程序代码………………………………………… 2
3 冒泡排序调试 ……………………………………………………………………4
3.1 冒泡排序调试方法 ……………………………………………………………4
3.2 程序调试 …………………………………………………………………………5
4 冒泡排序性能分析 ………………………………………………………………6
4.1 时间复杂度 ………………………………………………………………………6
4.2 空间复杂度 ………………………………………………………………………7
4.3 稳定性 ……………………………………………………………………………7
5 冒泡排序不足 ……………………………………………………………………7
结论 …………………………………………………………………………………… 9
致谢 ……………………………………………………………………………………10
参考文件………………………………………………………………………………11
附录A …………………………………………………………………………… 13

1 引言
在很多程序设计中，我们需要将一个数列进行排序，以方便统计，而冒泡排序一直因为其简练思想方法而倍受青睐
冒泡排序，是指计算机一个排序方法，它时间复杂度为O（n^2），即使不及堆排序、快速排序，不过有两个优点：1.“编程复杂度”很低，很轻易写出代码；2.含有稳定性，这里稳定性是指原序列中相同元素相对次序仍然保持到排序后序列，而堆排序、快速排序均不含有稳定性。不过，一路、二路归并排序、不平衡二叉树排序速度均比冒泡排序快，且含有稳定性，但速度不及堆排序、快速排序。冒泡排序是经过n-1趟子排序完成，第i趟子排序从第1个数至第n-i个数，若第i个数比后一个数大（则升序，小则降序）则交换两数。
因为冒泡排序方法简单，所以得到广泛应用。
2 冒泡排序实现
2．1 冒泡排序基础概念
冒泡排序基础概念是：依次比较相邻两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最终两个数，将小数放前，大数放后。至此第一趟结束，将最大数放到了最终。在第二趟：仍从第一对数开始比较（因为可能因为第2个数和第3个数交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一位置上已经是最大），第二趟结束，在倒数第二位置上得到一个新最大数（其实在整个数列中是第二大数）。如此下去，反复以上过程，直至最终完成排序。
用二重循环实现，外循环变量设为i，内循环变量设为j。假如有10个数需要进行排序，则外循环反复9次，内循环依次反复9，8，...，1次。每次进行比较两个元素全部是和内循环j相关，它们能够分别用a[j]和a[j+1]标识，i值依次为1,2,...,9，对于每一个i和j值依次为1,2,...10-i。
2．2 冒泡排序引例
将9,5,2,4四个数用冒泡排序方法进行排序。先把四个数依次存入R[1..4]数组中，具体排序过程以下图所表示：

图一
第一趟结果：5 2 4 9 最大数9在R[4]中。

图二
第二趟结果：2 4 5 9 第二大数数5在R[3]。

图三
第一趟结果：5 2 4 9 第三大数4在R[2]中.
以上第一趟比较结果出来一个最大数9，发表放在R[4]中；第二趟出来次大树5，放在R[3]中，……；四个数进行三趟。其比较过程为相邻两数比较，小浮上去，大沉下来。
2．3 冒泡排序步骤图及程序代码
2.3.1 冒泡排序步骤图
依据冒泡排序排序过程可得以下程序步骤图：

图四
2.3.2 冒泡排序程序
本程序编写采取调用子函数方法，先定义一个子函数Bubble_Sort(n)实现冒泡排序功效，在主函数中输入要排序数字，在调用子函数后实现数字排序。
#include <stdio.h>
#define MAX 255
#define clrscr()
#define exit
#define getch()
int a[MAX];
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--) /*对目前无序区a[i..n]自下向上扫描*/
if(a[j+1]<a[j]) {/*交换统计*/
a[0]=a[j+1]; /*a[0]不是哨兵，仅做暂存单元*/
a[j+1]=a[j];
a[j]=a[0];
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",&a[i]);
puts("the sequence you input is:");
for(i=1;i<=n;i++)
printf("%4d",a[i]);
Bubble_Sort(n);
puts("\nThe sequence after bubble_sort is:");
for(i=1;i<=n;i++)
printf("%4d",a[i]);
puts("\n Press any key to quit…");
getch();
}
3 冒泡排序调试
3．1 冒泡排序调试方法
本程序采取Microsoft Visual C++ 6.0调试，首先打开软件，新建一个C++ source file 文件，输入文件名称，选择适宜文件目录。图所表示：

图五
新建好文件后，开始编辑程序，然后点击组建——编译，如出现错误可按F4查找错误，修改至无错误位置，可有警告。程序检验无错误就可点击运行程序。

图六
3．2 调试过程
根据上面调试方法运行程序后，首先要输入排序数据总个数。

图七
输入对应数字（比如 5 ）后显示是

图八
依次输入5个数，每隔一个输入一个空格，待5个数输入完成后点击回车确定。第一行显示是输入次序，第二行显示排完次序一串数字，如输入2，38,5,47，50五个数。

图九
4 冒泡排序性能分析
4．1 时间复杂度
通常情况下冒泡排序时间复杂度为O（n*n）。但当排序数完全正序时候，n个数只进行一趟，比较n-1次，其时间复杂度为O(n)，这是冒泡排序最好情况。比如将2,4,6,8,10五个数用冒泡排序，只进行一趟，比较四次，不发生数据交换，排序就结束了。
4．2 空间复杂度
和直接插入排序一样，不管有待排序数n有多大，辅助空间只需要一个m，用于两数交换运算，所以，冒泡排序空间复杂度也为O（1）。
4．2 稳定性
从程序能够看出，当a[j]>a[j+1]时才交换，若相等则不交换，所以，冒泡排序是稳定排序。
总而言之，冒泡排序基础思想是：相邻关键字进行比较，不适宜就交换。因为冒泡排序方法简单，所以得到广泛应用。
5 冒泡排序不足
冒泡排序法存在不足及改善方法：
第一，在排序过程中，实施完最终排序后，即使数据已全部排序完备，但程序无法判定是否完成排序，为了处理这一不足，可设置一个标志位flag，将其初始值设置为非0，表示被排序表是一个无序表，每一次排序开始前设置flag值为0，在进行数据交换时，修改flag为非0。在新一轮排序开始时，检验此标志，若此标志为0，表示上一次没有做过交换数据，则结束排序；不然进行排序；
第二，当排序数据比较多时排序时间会显著延长。
改善方法：快速排序：具体做法：任意选择某一统计（通常取第一个统计），比较其关键字和全部统计关键字，并将关键字比它小统计全部放在它前面，将比它大统计均存放在它后面，这么，经过一次排序以后，可将全部统计以该统计所在分界点分为两部分，然后分别对这两部分进行快速排序，直至排序完
局部冒泡排序算法对冒泡排序改善：
在冒泡排序中，一趟扫描有可能无数据交换，也有可能有一次或数次数据交换，在传统冒泡排序算法及多年来部分改善算法中，只统计一趟扫描有没有数据交换信息，对数据交换发生位置信息则不予处理。为了充足利用这一信息，能够在一趟全局扫描中，对每一反序数据对进行局部冒泡排序处理，称之为局部冒泡排序。局部冒泡排序和冒泡排序算法含有相同时间复杂度，而且在正序和逆序情况下，所需关键字比较次数和移动次数完全相同。因为局部冒泡排序和冒泡排序数据移动次数总是相同，而局部冒泡排序所需关键字比较次数常少于冒泡排序，这意味着局部冒泡排序很可能在平均比较次数上对冒泡排序有所改善，当比较次数较少优点不足以抵消其程序复杂度所带来额外开销，而当数据量较大时，局部冒泡排序时间性能则显著优于冒泡排序。

结 论

经过了这一次课程设计，愈加具体了解了冒泡排序排序方法，从它最开始基础概念到步骤图设计设计，程序编写，最终到程序调试，系统掌握了冒泡排序操作和程序思绪。因为多个排序方法大同小异，所以在这次课程设计以后，对于其它多个排序方法也有了愈加深刻了解。
计算机软件在现代社会已近得到了最广泛利用，对于我们学生来说，掌握必需计算机软件基础知识是必不可少。学完这门课后我们对计算机软件基础料了解了更多知识，对计算机软件业有了更多了解，这对我们以后发展有了很大帮助。

致 谢

这篇论文完成离不开老师和同学支持，感谢老师细心指导，在论文排版上感谢老师意见，才使得这篇论文排版如此整齐。在步骤图绘制和程序编写时，碰到困难难以继续，在同学热心帮助下，我找到了对应参考书，在参考书上我发觉了处理困难方法，才能继续书写论文。也感谢舍友细心帮我核查，改掉其它细小毛病。
最终感谢南京理工大学能给我这次机会，让我学到更多知识，也感谢苏州市职业大学对我教育和指导。

参 考 文 献

[1] 宁正元，王秀丽.算法和数据结构，：29～32
[2] 杨辉.杨辉纵横图论，：12～14
[3] 唐王希.太乙金镜式经，：35～37
[4] 王力柱。c/c++和数据结构。栈，（8）：142～152
[5] 徐孝凯，贺桂英。数据结构。栈和队列，（10）：76～92
[6] 吴乃陵，李海文。c++程序设计。栈，（8）：80～87 ，263～270
[7] 陈媛，何波，涂晓江，涂飞。算法和数据结构。栈，（4）
[8] 张勇，刘君仪。数据结构。栈，（8）：96～107
[9] 王挺，周会平。c++程序设计。（1）：30～38
[10]严蔚敏，吴伟民。数据结构。北京：清华大学出版社，

附录A：
程序代码：
#include <stdio.h>
#define MAX 255
#define clrscr()
#define exit
#define getch()
int a[MAX];
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--) /*对目前无序区R[i..n]自下向上扫描*/
if(a[j+1]<a[j]) {/*交换统计*/
a[0]=a[j+1]; /*R[0]不是哨兵，仅做暂存单元*/
a[j+1]=a[j];
a[j]=a[0];
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",&a[i]);
puts("the sequence you input is:");
for(i=1;i<=n;i++)
printf("%4d",a[i]);
Bubble_Sort(n);
puts("\nThe sequence after bubble_sort is:");
for(i=1;i<=n;i++)
printf("%4d",a[i]);
puts("\n Press any key to quit…");
getch();
}