算法分析大作业

目录

1.1背景和意义 ...................................................... 1 2.1设计的目的和意义 ................................................ 2 2.2目标与总体方案 .................................................. 2 2.3设计方法和内容 .................................................. 2 2.3.1 设计方法 ...................................................... 2 2.3.2 设计内容 ...................................................... 3 2.4设计创新和关键技术 .............................................. 5 2.4.1设计创新 ...................................................... 5 2.4.2关键技术 ...................................................... 6 2.5结论 ............................................................ 6 致谢 ................................................................ 6 参考文献 ............................................................ 6 附录A 源程序的清单 ................................................. 7

塔里木大学信息工程学院课程设计

前言

1.1背景和意义

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。 算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较。

计算机科学及应用活动中，最有挑战性的困难往往就是算法分析。人们总是根据应用实践的具体需求，抽象出描述简单而严格的一般性计算问题，专门研究设计这些问题的求解算法。算法设计追求用较低的时间和空间复杂性，计算得到满足要求的解。在过去的算法设计实践中，人们针对不同领域的问题设计了许多巧夺天工的求解算法；已形成若干之有效的算法分析技术。

而通过学习这门课程，我们学到了许多的算法思想。在一学期的学习之后，我们就通过本次的课程设计来检验自我的学习情况。

第 1 页 共 15 页

塔里木大学信息工程学院课程设计

正文

2.1设计的目的和意义

课程设计目的是为学生提供了一个既动手又动脑，独立实践的机会，将课本上的理论知识和实际有机的结合起来，锻炼学生的分析解决实际问题的能力。提高学生适应实际，实践编程的能力。通过实践让学生理论和实际操作相结合，更好的理解书面知识，并在巩固的基础上融会所学认识。

课程设计的意思是培养学生运用所学课程的知识分析解决实际问题的能力；查研究、查阅技术文献、资料、手册以及编写技术文献的能力；通过课程设计，要求学生在指导教师的指导下，独立完成设计课题的全部内容，包括：收集和调查有关技术资料。上机实验调试。

2.2目标与总体方案本次实验设计是内部排序问题，排序又又很多的方法，所以本程序用了不不同点排序方法，用了一项排序方法对随机产生的数据进行排序。在每个排序的子函数中对升序和降序再进行一次选择。是每个排序方法的实现算法不同。序方法的升序或者降序对它进行排序出来时间和空间复杂度。容量，然后随机对数组的每一个元素赋值。也是通过for循环一个个显示数组中每一个数据元素值。2.3设计方法和内容2.3.1 设计方法

本次实验主要是实现多种排序的方法功能模块一：

该模块实现的是直接插入排序方法，直接插入排序的基本思想是：假设待排序的记录存储在数组子区间R[1...i-1]和时有序表中只有一个元素中取出第一个元素，经过n-1次插入后，无序区为空，有序区中包含了全部功能模块二：

该模块实现的是简单选择排序方法，直接插入排序的基本思想是：每次从待排序的无序区中选择出关键字最大个记录交换位置。初始时，为有序区；第二趟在无序区为有序区；依次类推，做功能模块三：

该模块实现的是堆排序方法，直接插入排序的基本思想是：（2）掌握课程设计的基本步骤和方法。

while循环来判断是否退出排序程序，基本的思路都是随机产生一组无序的数据， ，然后现实每个排序方法的排序过程。最后现实统计该排序程序系统用的数据是通过数组进行存储的，

R[1...n]R[i...n],其中，前一个为排好序的有序区，而后一个为无序区。开始R[1]，无序区为不它插入到有序表区的适当位置，R[1...n]中选出最大或者最小的记录，将它与R[2...n]中选出最大n-1趟排序后，区间（1排序的每个模块的思路都差不多，

R[2....n]。排序过程中，只需要每次从无序区使之成为新的有序区。n个元素，至此，排序完毕。（最小）的记录，（最小）的记录与R[1....n]中记录递减（递增）有序。培养学生调3）根据课题的要求进行switch来选择case中的然后只然后用一中排先定义了数组的显示

R被划分成两个依次这样

R[1]交换，R[1]R[2]交换，此时R[1,2]

第 2 页 共 15 页

）通过调查研究和上机实习，（如果不退出则进行所有的排序方法都在主函数中有一个入口，通过排序再把排序后的数据再存入数组中，中，在排序的过程的某一时刻，把该记录与该区中的第一塔里木大学信息工程学院课程设计

在排序过程中，将记录数组R[1...n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉数中双亲结点和孩子结点之间的内在关系，在当前无序中选择关键字最大（最小）的记录。 功能模块四：

该模块实现的是冒泡排序方法，直接插入排序的基本思想是：

通过相邻元素之间的比较和交换，使排序关键字较大（较小）的元素逐渐从底部移向顶部，即从下标较大的元素移向下标较小的元素。 功能模块五：

该模块实现的是快速排序方法，直接插入排序的基本思想是：

首先在当前无序区R[low...high]中任取一个记录作为排序比较的基准，用此基准将当前无序区划分为两个较小的无序区：R[low...i-1]和R[i+1...high],并使左边的无序区中所有记录的关键字均小于等于基准的关键字，右边的无序区中的所有记录的关键字都大于等于基准的关键字，而基准记录则位于最终排序的位置i上。这个过程成为一趟快速排序。当R[low...i]和 R[i+1...high]均非空时，分别对它们进行上述的划分过程，直到所有的无序区中的记录均已排好序为止。 功能模块六：

该模块实现的是2-路归并排序方法，直接插入排序的基本思想是：

将待排序文件看成n个长度为1的有序子文件，把这些子文件两两归并，得到n/2个长度为2（或者最后一个长度为1）的有序子文件；然后再把这n/2个有序文件的子文件两两归并，如此反复，知道最后得到一个长度为n的有序文件为止。 2.3.2 设计内容

由于程序段会在后面的附录出现在此就不再将相应程序在此段出现，只给出相应的实验图

图2-1 直接插入排序

第 3 页 共 15 页

塔里木大学信息工程学院课程设计

图2-2 单选择排序

图2-3 堆排序

图2-4 冒泡排序

第 4 页 共 15 页

塔里木大学信息工程学院课程设计

图2-5 快速排序

图2-6 2-路归并排序

2.4设计创新和关键技术

2.4.1设计创新

算法的设计取决于数据（逻辑）结构，而算法的实现依赖于采用的存储结构。数据的运算是在数据的逻辑结构上定义的操作算法，如检索、插入、删除、更新的排序等。在本设计程序中，我将平时认为较为简单的排序问题进行了一次简单的集中。当多种排序方法放到一起后我们更能看出各种方法的优点以及不足。同时还能在此同时我还在具体的实践中发现、学习很多以前自己还未能掌握的东西。

对于本次实验我个人认为最大的创新是将多种排序方法集中在一起比较，将各中排序方法执行之后我们会对这些排序方法又更多的了解。

第 5 页 共 15 页

塔里木大学信息工程学院课程设计

在本设计程序中，充分体现了上述的操作，虽然只是运用局部操作，但是仍然起到了关键作用。

使用C语言和C++相结合的方式，使得程序运行更灵活，处理更方便，在表现方式方面得到了创新。 2.4.2关键技术

该课程设计的数据结构就是利用数组来对所有的排序进行存储。由于排序的方法又有多种，所以只是用数组的数据结构存储每次排序的始末状态，不同的方法都可以使用相同点数据结构.

在该课设种还多次运用了在算法分析上所学的递归算法以及二分法，这些方法在各个不同的排序方法中都有不同的体现方式。

2.5结论

在本次课程设计过程中我学到了很多的知识，一个一个的子函数都是自己想通了算法才开始写的，而不足之处还是又很多，首先是自己编程不够熟悉，面够完善，还有待好好改进。

致谢首先要感谢学校、学院给我提供了这次宝贵的课程设计机会，能力，把理论和实践联系到了一起，取得了巨大的收获。计条件，使我能在规定时间内保质保量的完成这次设计。本课题在选题及设计过程中都得到陈杰老师的悉心指导，老师表示我深深的谢意。

很高兴能独自完成一个关于c++语言的算法设计。的时间，也让老师操了一番苦心。在此次设计中遇到了好多的问题，于课程设计书才明白所用函数的用法，更重要的是以前在上课时，全面。把需要讲的几乎都讲过。老师的细心教学，语言的东西。从而在这次设计中因有这样的知识渊博老师而感到骄傲，我们提供机房，让我们有良好的学习环境，最后献上我真诚的谢意。在此我还要感谢的人还有庄连成同学，是他给我细心分析各种算法思想和用法，以编成了这个精简实用的程序。

在编写程序的过程中，我不仅得到了同学们的热情帮助，读书籍，我的能力得到了提高，同时养成了科学、严谨的学习作风和生活习惯，并且通过这次的课程设计也让我们更清楚的认识到这C++语言的功能及用法，设计的灵魂。在此，我对同学们的热情帮助表示衷心的感谢！示忠心的感谢！对辛苦为我们指导的老师说声谢谢。参考文献

[1] 朱大铭 马绍汉编著.算法设计与分析 高等教育出版社[2] 谭浩强编著.C++面向对象程序设计题解与上机指导[3] 谭浩强编著.C++面向对象程序设计.北京：清华大学出版社[4] 孔令德 叶瑶 杨慧炯编著.C++程序设计案例精编[5] 甘玲 石岩 李盘林编著.解析C++面向对象程序设计[6] 邓阿奇著.Visual C++ 教程.清华大学出版社[7] 钱能.C++程序设计.清华大学出版社

C++编程，以前很少实践，在实现功能方让我充分锻炼了实际操作并为我释疑解惑。都是经过老师所给的关老师讲课细心，C++语言以及其他并且也谢谢校领导为

还有老师们的大力支持认真阅深刻体会到了算法是程序同时也对老师的不辞辛苦而表

第 6 这次然15 页

首先是用写完了之后又一点点小小的成就感。也许算法写得过去复杂，

同时也要感谢学院提供了良好的设

在此对陈杰这次的课程设计不仅我们花去了不少而且又很使我们学会了好多关于我才得

.北京：.中国铁道出版社.清华大学出版社 页 共 塔里木大学信息工程学院课程设计

附录A

源程序的清单

#include #include

#define N 11 // 用来存排序用的数据，其中第一个元素经常作为“哨兵”和交换用 int sjs[7],kjs[7]; //分别用来描述排序所用的时间和空间性能,从第二个 元素开始使用 int sum; //用来计排序的次数

int sm[N]; //用来作为辅助存储空间，用于2-路归并排序中 using namespace std; //函数声明 int zjcr(int s[]); int jdxz(int s[]);

int ddpx(int s[],int n); int mppx(int s[]);

int kspx(int s[],int low,int high); int gbpx(int s[],int sm[],int n); int main()

{ cout<<\*\

cout<<\ 内 部 排 序 问 题 \ cout<<\endl;

cout<<\ \

cout<<\ 计算机科学与技术专业12-3 龙 森 5011208224 \

int ch,c=1; //其中ch用来标记所选择的排序方法，c用来判断是否推出排序程序 while(c!=0)

{ cout<<\========\\n\

cout<<\ 0 退出排序程序\

cout<<\ 1 直接插入排序 2 简单选择排序\ cout<<\ 3 堆排序 4 冒泡排序 \ cout<<\ 5 快速排序 6 2-路归并排序\

cout<<\======\

cout<<\请选择您要用的排序方法： \ cin>>ch;

//随机产生排序用的数据 int s[N]; int i;

for(i=1;i<=N-1;i++) {s[i]=rand()0;}

cout<<\随机产生用来排序的原始数据如下： \

第 7 页 共 15 页

塔里木大学信息工程学院课程设计

for(i=1;i<=N-1;i++) {cout<

switch(ch)

{ case 0:c=0;break; case 1:zjcr(s);break; case 2:jdxz(s);break;

case 3:ddpx(s,N-1);break; case 4:mppx(s);break;

case 5:kspx(s,1,N-1);break; case 6:gbpx(s,sm,N-1);break;

default:cout<<\您的输入不正确，选择的范围是〈0，输入： \ } }

system(\ return 0; }

//=====================================函 ============================================

//直接插入排序算法 int zjcrs(int s[]) { sum=0; int i,j;

for(i=2;i<=N-1;i++) {

if(s[i]

{s[0]=s[i]; //s[0]作为哨兵 for(j=i-1;s[0]

s[j+1]=s[0]; }

sum++;

cout<<\第\趟排序结果: \ for(int i=1;i<=N-1;i++) {cout<

，2，3 4，5，6 定第 8 页义15 页

1，〉，请重新数的 共 塔里木大学信息工程学院课程设计

kjs[1]=1; //该算法中只有一个辅助存储空间即s[0]

cout<<\该方法的时间复杂度为： \ 空间复杂度为： \ return 0; }

int zjcr(int s[]) //直接插入排序的主要函数

{ cout<<\您选择的是: [直接插入排序方法] \\n\ cout<<\数据的初始顺序如下: \ int i; for(i=1;i<=N-1;i++) {cout<

sjs[1]=kjs[1]=0; //时空计数清零 zjcrs(s);

cout<<\排序后数据的顺序如下： for(i=1;i<=N-1;i++) {cout<

//简单选择排序算法 int jdxzs(int s[]) { sum=0; int i,j,k;

for(i=1;i<=N-1;i++)

{ k=i ; //记录关键字最小的记录位置 for(j=i+1;j<=N-1;j++) {

if(s[j]

k=j; //更新最小记录的位置 }

if(k!=i)//与第i个记录进行交换 {

s[0]=s[i]; s[i]=s[k]; s[k]=s[0]; sjs[2]++; }

sum++;

cout<<\第\次排序结果 for(int i=1;i<=N-1;i++) {cout<

\: \第 9 页 共 15 页

塔里木大学信息工程学院课程设计

kjs[2]=1; //只有一个辅助空间s[0]

cout<<\该方法的时间复杂度为： \ 空间复杂度为： \ return 0; }

int jdxz(int s[]) //简单选择排序的主要函数

{ cout<<\您选择的是: [简单选择排序方法] \\n\ cout<<\数据的初始顺序如下 int i; for(i=1;i<=N-1;i++) {cout<

cout<<\排序后数据的顺序如下： for(i=1;i<=N-1;i++) {cout<

//堆排序算法

int jdd(int s[],int i,int n) //调整大根堆{ s[0]=s[i]; //倍份待筛结点元素值 int j=2*i; //s[j]为s[i]的左孩子 while(j<=n) //当 s[i]的左孩子不为空时 {

if(j

j++; //j为i 结点较大孩子的下标 if(s[0]>=s[j])

break; //找到位置,终止循环 sjs[3]++; s[i]=s[j]; i=j; j=2*i; }

s[i]=s[0]; return 0; }

int ddpxs(int s[],int n) { sum=0;

: \ \ 第 10 页 共 15 页

塔里木大学信息工程学院课程设计

int i;

for(i=n/2;i>0;i--) jdd(s,i,n); for(i=n;i>1;i--) { s[0]=s[1]; s[1]=s[i]; s[i]=s[0]; sjs[3]++; sum++;

cout<<\第\次排序后的结果： for(int t=1;t<=N-1;t++) {cout<

kjs[3]=1; //只用了一个辅助存储空间 cout<<\该方法的时间复杂度为：\ return 0; }

int ddpx(int s[],int n)

{ cout<<\您选择的是: [堆排序方法 cout<<\数据的初始顺序如下 int i; for(i=1;i<=N-1;i++) {cout<

cout<<\排序后数据的顺序如下： for(i=1;i<=N-1;i++) {cout<

//冒泡排序算法

int mppxs(int s[]) { sum=0; int i,j;

for(i=1;i=i;j--) if(s[j]

{ s[0]=s[j-1]; //s[0] \s[0]

\] \\n\: \ \

页 共 15 页

空间复杂度为： 作为交换时的暂存单元第 11 塔里木大学信息工程学院课程设计

s[j-1]=s[j]; s[j]=s[0]; sjs[4]++; }

sum++;

cout<<\第\排序后的结果是: \ for(int i=1;i<=N-1;i++) {cout<

kjs[4]=1; //只用了一个用于交换的暂存单元 cout<<\该方法的时间复杂度\ return 0; }

int mppx(int s[]) //冒泡排序的主要函数{ cout<<\您选择的是: [冒泡排序方法 cout<<\数据的初始顺序如下 int i;; for(i=1;i<=N-1;i++) {cout<

cout<<\排序后数据的顺序如下： for(i=1;i<=N-1;i++) {cout<

//快速排序算法

int huafens(int s[],int i,int j) //快速划分函数 {

s[0]=s[i]; //s[0]为辅存 kjs[5]++; while(i

while(i=s[0]) j--; if(i

s[i]=s[j]; i++; sjs[5]++;

s[0]

为： \

] \\n\: \ \ 复杂度为： 页 共 15 页

空间第 12 塔里木大学信息工程学院课程设计

}

while(i

s[j]=s[i]; j--;

sjs[5]++; } }

s[i]=s[0]; return i; }

int kspxs(int s[],int low,int high) {

if(low

p=huafens(s,low,high); sum++;

cout<<\第\次划分的结果为: \ for(int j=1;j<=N-1;j++) {cout<

int kspx(int s[],int low,int high)

{ cout<<\您选择的是: [快速排序方法] \\n\ cout<<\数据的初始顺序如下: \ int i; for(i=1;i<=N-1;i++) {cout<

sum=0; //排序次数清零 sjs[5]=kjs[5]=0; kspxs(s,1,N-1);

cout<<\该方法的时间复杂度为： \\

cout<<\排序后数据的顺序如下： \ for(i=1;i<=N-1;i++) {cout<

页 共 15 页

空间复杂度为：第 13 塔里木大学信息工程学院课程设计

cout<

//2-路归并排序算法

int gbzs(int s[],int sm[],int low,int m,int high)//核心操作，对相邻的两个子文件进行升排序 { int i,j,k; i=low; j=m+1;

k=low; //初始化

while(i<=m&&j<=high) {

if(s[i]<=s[j])

{sm[k++]=s[i++]; sjs[6]++;} else

{sm[k++]=s[j++]; sjs[6]++;} }

while(i<=m)

{sm[k++]=s[i++];//将s[low,m]中剩余的部分复制到 sjs[6]++;} while(j<=high)

{sm[k++]=s[j++];//将 s[m+1,high]中剩余的部分复制到 sjs[6]++;} return 0; }

int gbycs(int s[],int sm[],int len,int n)//做一趟归并升排序{ int i;

for(i=1;i+2*len-1

gbzs(s,sm,i,i+len-1,n); else

for(int j=i;j<=n;j++) sm[j]=s[j]; return 0; }

int gbpxs(int s[],int sm[],int n) //升序 { int m=0; int len=1; while(len

sm中 sm中 第 14 15 页

页 共 塔里木大学信息工程学院课程设计

{

gbycs(s,sm,len,n); sum++;

cout<<\第\次排序后的顺序显示： \ for(int i=1;i<=10;i++) {cout<

gbycs(sm,s,len,n); }

kjs[6]=N-1;

cout<<\该方法的时间复杂度\ return 0; }

int gbpx(int s[],int sm[],int n)

{ cout<<\您选择的是: [2-路归并排序方法 cout<<\数据的初始顺序如下 int i; for(i=1;i<=N-1;i++) {cout<

sjs[6]=kjs[6]=0; gbpxs(s,sm,N-1);

cout<<\排序后数据的顺序如下： for(i=1;i<=N-1;i++) {cout<

为： \] \\n\: \ \复杂度为： 页 共 15 页

空间第 15

塔里木大学信息工程学院课程设计

{

gbycs(s,sm,len,n); sum++;

cout<<\第\次排序后的顺序显示： \ for(int i=1;i<=10;i++) {cout<

gbycs(sm,s,len,n); }

kjs[6]=N-1;

cout<<\该方法的时间复杂度\ return 0; }

int gbpx(int s[],int sm[],int n)

{ cout<<\您选择的是: [2-路归并排序方法 cout<<\数据的初始顺序如下 int i; for(i=1;i<=N-1;i++) {cout<

sjs[6]=kjs[6]=0; gbpxs(s,sm,N-1);

cout<<\排序后数据的顺序如下： for(i=1;i<=N-1;i++) {cout<

为： \] \\n\: \ \复杂度为： 页 共 15 页

空间第 15

本文来源：https://www.bwwdw.com/article/gpxr.html