题目2_排序综合_报告

理学院 课程设计说明书

课 程 名 称: 数据结构与算法A设计实践 课 程 代 码: 6015059

题 目 二: 排序综合 年级/专业/班: 2013/信科/2班 学 生 姓 名: 冯金慧 学 号: 3120130902209 开 始 时 间: 2015 年 12 月 28 日 完 成 时 间: 2016 年 01 月 10 日 课程设计成绩：

学习态度及平技术水平与实际时成绩（30） 能力（20） 创新（5） 说明书撰写质量（45） 总 分（100） 指导教师签名： 年 月 日

西华大学理学院课程设计说明书

数据结构与算法A设计实践任务书

学院名称： 理学院 课程代码：_6015059________ 专业： 信科 年级： 2012

一、 设计题目

排序综合（限最多一人完成）

二、主要内容

利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。

三、具体要求及提交的材料

1) 至少采用4种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 2) 统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 如果采用4种或4种以上的方法者，可适当加分。 测试数据及测试结果请在上交的资料中写明；

必须上机调试通过按《数据结构课程设计大纲》中的要求完成课程设计报告格式。 设计结束后，每个学生必须上交的材料有：

1 《课程设计报告》打印稿一份 2．课程设计的源代码电子文档一份

四、主要技术路线提示 无 五、进度安排

共计两周时间，建议进度安排如下：

1． 选题，应该在上机实验之前完成 2. 需求分析、概要设计可分配4学时完成 2． 详细设计可分配4学时 4. 调试和分析可分配10学时。 2学时的机动，可提前安排部分提前结束任务的学生答辩

六、 推荐参考资料

1. 2. 3. 4.

冯博琴 等编著，《软件技术基础》（修改版），西安交通大学出版社，1997 严蔚敏 等著，《数据结构》，清华大学出版社，2003 李芸芳 等著，《软件技术基础》（第二版），清华大学出版社，2000 徐孝凯 等著，《数据结构（C语言描述）》，清华大学出版社，2004

5. 指导教师 签名日期 年 月 日 6. 系 主 任 审核日期 年 月 日

西华大学理学院课程设计说明书

目 录

摘 要 ................................................................... 1 2 系统分析 ................................................................ 3

2.1功能需求 ........................................................... 3

2.1.1总体要求 ..................................................... 4 1.4 数据需求 ......................................................... 5 3、详细设计与实现 ......................................................... 5

3.1设计思路 ........................................................... 5 3.2详细编码 ........................................................... 5 3.3实验结果 .......................................................... 15 4．系统测试和结果分析 .................................................... 16

4.1设计测试数据 ...................................................... 16 4.2调试的详细过程 .................................................... 16 5、算法效率的分析 ........................................................ 22

5.1 耗费时间 ......................................................... 22 5.2性能分析 .......................................................... 22 5.3时间效率 .......................................................... 23 总 结 ................................................................... 24 参考文献 ................................................................. 26 附 录 .................................................................... 27

排序综合

摘 要

排序算法是数据结构学科经典的内容，其中内部排序现有的算法有很多种，其中包含冒泡排序，直接插入排序，简单选择排序，希尔排序，快速排序，堆排序等，各有其特点。对排序算法比较的分析可以遵循若干种不同的准则，通常以排序过程所需要的算法步数作为度量，有时也以排序过程中所作的键比较次数作为度量。特别是当作一次键比较需要较长时间，例如，当键是较长的字符串时，常以键比较次数作为排序算法计算时间复杂性的度量。当排序时需要移动记录，且记录都很大时，还应该考虑记录的移动次数。究竟采用哪种度量方法比较合适要根据具体情况而定。在下面的讨论中我们主要考虑用比较的次数作为复杂性的度量。

排序（sorting）是计算机程序设计的一种重要操作，他的功能是将一个数据元素（或记录）的任意序列，重新排列一个按关键字有序的序列。由于待排序的记录数量不同，使得排序过程中涉及的储存器不同，可将排序方法分为两大类：一类是内部排序，指的是待排序记录存放在计算机随机储存器中进行的排序过程；另一类是外部排序，指的是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。 内部排序又分为：插入排序、快速排序、选择排序、归并排序和基数排序。其中插入排序又分为：直接插入排序、其他插入排序和希尔排序；选择排序分为：简单选择排序、树形选择排序和堆排序；基数排序又分为：多关键字的排序和链式基数排序。

本次课程设计就是运用VS2010环境编译的程序，首先产生2000个随机数，然后写出几种不同的排序方法分别对产生的随机数进行排序并记录下各种不同法师的排序所耗费的时间，从而找出排序速度比较快的两种方法，并对不同的排序的性能进行了统计与分析。

关键词：随机数，排序，时间效率，时间复杂度，文件操作

1

西华大学理学院课程设计说明书

1 引 言

1. 1问题的提出

首先，如何产生20000个随机数；其次，对所产生的随机数如何存入文件以方便不同的排序函数所调用；最后，如何处理运用各种排序方法对所产生的随机数进行排序后的结果，并将分析其排序效率。

1.2 C语言

C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。

1.3 C语言发展过程

1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。

1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本《可移植的C语言编译程序》。

1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著《The C Programming Language》，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。

1.4任务与分析

任务是先产生出20000个随机数，然后再实现分别采用快速排序、气泡排序、直接插入排序、归并排序、简单选择排序、堆排序对刚产生的随机数进行排序，并按照要求，需要记录出不同方法排序所花费的时间，所以需要编写一个记录时间的函数模块，在排序开始时调用该函数记录所耗费的时间。

分析：首先，随机数产生的较多时不太好方便操作，于是在写随机数模块时可以先产生较少的随机数进行调试和检查。其次是这学期数据结构这门课中学的排序方法比较多，结合这学期学习的数据结构这门课程，我选择了快速排序、气泡排序、直接插入排序、归并排序、简单选择排序、堆排序这几种排序方式。接着，对随机数采用不同的方式进行排序，想到了将不同的排序方法依次分块写成函数，需要采用哪种方式排序时仅需要调用相应的函数就行了。最后需要记录下不同排序所耗费的时间，就需要再写一个记录耗时的函数了，这样把一个大问题分成若干个小问题，解决起来就简单方便的多了。

2

排序综合

初步想法是利用随机数函数产生20000个随机数，将产生的20000个数放到一个一维数组中，并显示20000个数；设置菜单选项，以选择6种不同的排序方法中的一种进行排序；采用每种排序方法时统计该算法耗时，在屏幕和文件中输出排序结果，之后回到菜单选择界面，然而我又想到不同的排序方式所做出的排序结果不能相互干扰，于是最终我选择将随机数存入文件中，以免排序时混淆。在输出排序结果时我想到不同的排序结果存入不同的文件中，这样结果就简单明了了。

2 系统分析

2.1功能需求

此课题是研究排序综合问题，并用不同的方式对所产生的的2000个随机数进行排序的问题。

确定其主要的几个模块的功能： 1、产生随机数

2、对所产生的随机数进行文件存储 3、用户选择模块

4、不同排序方式调用函数模块 5、文件存储模块 6、计时模块 7、菜单模块

对课题研究的进一步分析，我明确了我需要做的具体步骤：首先需要成功产生随机数，才能继续下一步的运用各种不同的排序方式对随机数进行排序。然后将几种不同的排序方式各自分成一个子快，编写出相应的6个函数（快速排序、冒泡排序、直接插入排序、归并排序、简单选择排序、堆排序），还有一个记录时间的函数模块，然后在主程序里面提示各个选项对相应的功能，用户输入相应的操作数，分别调用不同的函数，打印出相应的排序结果和所耗费的时间。最后，根据调试的结果对各个不同的排序方式加以分析。因此，实际需要设计的服务就是生成随机数，以及不同排序方法的函数编写，以及记录时间的函数的编写，为了直观和方便，画出流程图如下图1：

3

西华大学理学院课程设计说明书

排序综合 耗时函数 图1 程序总的流程图

退出 生成随机数 快速排序 冒泡排序 直接插入排序 归并排序 简单选择排序 堆排序 流程图很直观的描述了整个程序服务过程。

2.1.1总体要求

首先主函数中必须成功生成随机数，在这里我采取了随机种子来达到产生随机数的要求、首先，用户想要对随机数采用不同的方式进行排序，并得到其相应的耗时，就必须按照先序成功创建需要排序的对象即随机数。其次，用户要对随机数进行排序，那就需要知道他想采用的排序方法是什么。这需要用户手动输入选择序号。通过用户输入的信息，计算机就可以进行相关的操作，根据用户输入的信息选择相应的排序方式对所产生的随机数进行排序，输出相应的排序顺序和排序耗时供用户浏览了；我们就要用相应的程序去实现这个过程,这才是我们最后的目的。

4

排序综合

1.4 数据需求

随机产生20000个数

3、详细设计与实现

3.1设计思路

要完成对随机数的排序，有很多种方法可以实现。但是结合自己的知识掌握情况，我选择了比较适合自己的算法，其他的算法还有很多，只是都不是很熟悉，我的思想大多都来源于书上，这学期数据结构所学的排序方法比较多，我选择的有快速排序、冒泡排序、直接插入排序、归并排序、简单选择排序、堆排序。有了上面的分析，下一步自然就是完成分步它的程序了，不能用程序描述出来那在好也没有用的。 3.2详细编码 //包含头文件

#include \#include #include #include #include #include #include #include #include #include #include using namespace std;

//定义的结构体

#define M 2000 //产生随机数个数的定义 const int MAXSIZE=20000; typedef struct{

int key;

}RedType;

5

西华大学理学院课程设计说明书

typedef struct{ RedType r[MAXSIZE+1]; int length; }Sqlist;

typedef Sqlist HeapType; clock_t start,finish; using namespace std;

//自定义函数原型说明

int SelectMin(int a[],int i,int m)//简单选择排序

void Merge (RedType SR[],RedType TR[],int i,int m,int n) //2-路归并排序 int Partition(Sqlist &L, int low, int high)//快速排序 void HeapAdjust(HeapType &H, int s, int m) //堆排序 double duration(clock_t x,clock_t y)//算法耗时统计

//随机数的产生

int i, j, a[M];

char ch;

//定义i,j；待排序数组a[M]; //字符ch,用于记录选项;

srand((unsigned)time(NULL));//设置随机种子; for (i = 1; i < M + 1; i++)

a[i] = rand() % 5000; //随机生成待排序数组a;

cout << \产生20000个随机数\\\\/\system(\

for (i = 1; i < M + 1; i++) //每个元素占6个字符，每行十个元素的格式输出随机生成的待

排序数组a;

{ }

system(\

cout << setw(6) << a[i] << \if (i % 10 == 0)

cout << endl;

经过用户的按键操作，很容易就可以创建出2000个随机数，并弹出菜单项，用户

6

排序综合

输入对应的操作序号，计算机很快确定排序的方式并输出排出的顺序和所耗费的时间字样给用户，用户就可以继续输入选项进行下一步操作；这样，需要实现的第一个功能就很轻松的完成了。 //简单选择排序

简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i个记录交换之，直至整个序列非递减。

int SelectMin(int a[],int i,int m)//简单选择排序 {

int p,n,t; t=a[i];

for(p=i+1;p

{if(a[p]

for(n=i,p=i;p

{if(a[n]==t) break;} return n;

//归并排序

假设初始序列含有n个记录，则可看成是n个有序子序列，每个子序列的长度为1，然后两两归并，得到「n/2」个长度为2或1的有序子序列；在两两归并,......,如此重复，直至得到一个长度为n的有序序列为止。

void Merge(RedType SR[], RedType TR[], int i, int m, int n) //2-路归并排序 {

//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] int j, k;

for (j = m + 1, k = i; i <= m&&j <= n; ++k) { }

if (i <= m)

while (k <= n&&i <= m) TR[k++] = SR[i++]; //将剩余的SR[i..m]复制到TR

7

if (SR[i].key < SR[j].key) TR[k] = SR[i++]; //将SR中的记录由小到大并入TR else TR[k] = SR[j++];

西华大学理学院课程设计说明书

}

if (j <= n)

while (k <= n&&j <= n) TR[k++] = SR[j++]; //将剩余的SR[j..n]复制到TR

void MSort(RedType SR[], RedType TR1[], int s, int t) { }

int m; RedType * TR2;

TR2 = new RedType[M + 1]; if (s == t) TR1[t] = SR[s]; else { }

delete[]TR2;

m = (s + t) / 2; // 将SR[s..t]平分为SR[s..m]和SR[m+1..t] MSort(SR, TR2, s, m); // 递归地将SR[s..m]归并为有序的TR2[s..m] MSort(SR, TR2, m + 1, t); // 将SR[m+1..t]归并为有序的TR2[m+1..t] Merge(TR2, TR1, s, m, t); // 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t]

//冒泡排序

冒泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的关键字；以此类推，直至第n-1个记录和第n个记录的关键字进行过比较为止，结果使得关键字最大的记录被安置到最后一个记录的位置上；然后继续进行直至整个序列有序。

//冒泡排序;

8

{

int t;

//定义整形数据t

//建立冒泡排序结果保存文件;

ofstream output(\冒泡排序.txt\start = clock();

//开始起泡排序算法执行时间计时

//执行起泡排序算法

for (j = 1; j < M + 1; j++) {

for (int i = 1; i

排序综合

}

if (a[i]>a[i + 1]) { }

t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;

finish = clock(); //终止冒泡排序算法执行时间计时 printf( \显示冒泡排序结果:\\n\

for (i = 1; i < M + 1; i++)//每个元素占6个字符,以空格隔开，每100个元素换行

保存排序后数组;

{ }

output << setw(6) << a[i] << \if (i % 100 == 0)

printf(\

for (i = 1; i < M + 1; i++)//每个元素占6个字符,以空格隔开，每10个元素换行输

出排序后数组;

{ }

printf(\冒泡排序完成,结果已保存!\\n\

cout << setw(6) << a[i] << \if (i % 10 == 0)

printf(\

cout << \冒泡排序消耗时间为: \秒\//输出起泡排序算法耗时(s);

system(\

goto loop;//返回程序主菜单;

} break;

// 直接插入排序

9

西华大学理学院课程设计说明书

直接插入排序：先将序列中的第1个记录看成是一个有序的子序列，然后从第2个记录起逐个进行插入，直至整个序列变成关键字非递减有序序列为止，整个排序过程进行n-1趟插入。

int i,j;

//直接插入排序;

10

{

int i, j; Sqlist L;

//声明结构体;

//初始化结构体长度为0;

L.length = 0;

ofstream output(\直接插入排序.txt\建立直接插入排序结果保存文件; for (i = 1; i < M + 1; i++)//初始化直接插入排序结构体中的数据; { }

start = clock();

//开始直接插入排序算法执行时间计时;

//执行插入排序算法;

L.r[i].key = a[i]; L.length++;

for (i = 2; i <= L.length; ++i) { }

if (L.r[i].key < L.r[i - 1].key) { }

L.r[0] = L.r[i]; L.r[i] = L.r[i - 1];

for (j = i - 2; L.r[0].key < L.r[j].key; --j)

L.r[j + 1] = L.r[j];

L.r[j + 1] = L.r[0];

finish = clock(); //结束直接插入排序算法执行时间计时; cout << \显示直接插入排序的结果:\

for (i = 1; i < M + 1; i++)//每个元素占6个字符,以空格隔开，每100个元素换行

排序综合

保存排序后数组;

{ }

output << setw(6) << L.r[i].key << \if (i % 100 == 0)

printf(\

for (i = 1; i < M + 1; i++)//每个元素占6个字符,以空格隔开，每10个元素换行输

出排序后数组;

{ }

printf( \直接插入排序完成,结果已保存!\\n\

//

cout << setw(6) << L.r[i].key << \if (i % 10 == 0)

printf(\

cout << \直接插入排序消耗时间为 \秒\

输出直接排序算法耗时(s);

system(\

goto loop; //返回程序主菜单;

} break;

//快速排序

通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

int Partition(Sqlist &L, int low, int high) //快速排序 {

int pivotkey;

L.r[0] = L.r[low]; //用子表的第一个记录作枢轴 pivotkey = L.r[low].key; //枢轴记录关键字 while (low < high) {

while (low < high && L.r[high].key >= pivotkey) --high;

11

西华大学理学院课程设计说明书

}

}

L.r[low] = L.r[high]; //将比枢轴记录小的记录移到低端 while (low < high && L.r[low].key <= pivotkey) ++low; L.r[high] = L.r[low]; //将比枢轴大的记录移到高端

L.r[low] = L.r[0]; //枢轴记录到位 return low; //返回枢轴位置

void Qsort(Sqlist &L, int low, int high) { 置 }

}

Qsort(L, pivotloc + 1, high); // 对高子表递归排序 int pivotloc;

if (low < high) //长度大于1 {

pivotloc = Partition(L, low, high); //将L.r[low..high]一分为二

Qsort(L, low, pivotloc - 1); // 对低子表递归排序，pivotloc是枢轴位

// 堆排序

首先由无序序列建成一个堆，输出堆顶元素后，以堆中最后一个元素替代之，此时根节点的左右子树均为堆，则仅需自上至下进行调整即可，直至所有元素按非递减顺序输出。

void HeapAdjust(HeapType &H, int s, int m) //堆排序 { int j; RedType rc; rc = H.r[s];

for (j=2*s; j<=m; j*=2) {

if (j

12

排序综合

if (rc.key >= H.r[j].key) break; H.r[s] = H.r[j]; s = j; }

H.r[s] = rc; }

void HeapSort(HeapType &H) { int i; RedType temp;

for (i=H.length/2; i>0; --i) HeapAdjust ( H, i, H.length ); for (i=H.length; i>1; --i)

{

temp=H.r[i]; H.r[i]=H.r[1]; H.r[1]=temp;

HeapAdjust(H, 1, i-1); } }

//计算时间的函数

double duration(clock_t x, clock_t y) //算法耗时统计 { }

double dur;

dur = (double)(y - x) / CLOCKS_PER_SEC; return dur;

到此为止，所有功能已经分别实现了，通过执行各个函数，就可以完成相应的功能。现在唯一需要做的就是找个函数来将他们“集中起来”，用来组合在一起，才能让它们互相配合，一起工作。这个任务当然是由main()来完成了：

void main()

13

西华大学理学院课程设计说明书

{

printf(\

printf(\功 能： 排 序 综 合\\n\\n\printf(\编 译 环 境：V S 2 0 1 0\\n\\n\printf(\发 布 日 期：2 0 1 5 - 1 1 - 2 5\\n\\n\

printf(\程序开始！***********************\\n\int i, j, a[M]; char ch;

//定义i,j；待排序数组a[M]; //字符ch,用于记录选项;

srand((unsigned)time(NULL));//设置随机种子; for (i = 1; i < M + 1; i++)

a[i] = rand() % 5000; //随机生成待排序数组a;

printf( \产生200个随机数\\\\/\\n\system(\

for (i = 1; i < M + 1; i++) //每个元素占6个字符，每行十个元素的格式输出随机生成的待

排序数组a;

{ }

system(\

cout << setw(6) << a[i] << \if (i % 10 == 0)

printf(\

loop:

//排序算法主菜单;

printf(\菜 单\\n\

printf(\printf( \请选择你要使用的排序方法:\\n\

printf(\快速排序;\\n\\t\\t2.起泡排序;\\n \\t\\t3.直接插入排序;\\n \\t\\t4.归并排

序;\\n\

14

printf( \简单选择排序;\\n\\t\\t6.堆排序;\\n\\t\\t7.退出.\\n\printf(\

排序综合

loop1://排序过程;

fflush(stdin);

//清除文件缓冲区，文件以写方式打开时将缓冲区内容写入文件;为了确

保不影响后面的数据读取;

ch = getchar();

//获取选项,选择相应的排序算法;

在main（）里，对各个相应的操作指定了想象的选择序号，使用户简单明了，形象直观，首先必须成功生成2000个随机数，现实中一样。因为你需要排序的对象不明确，又如何能准确的确定相应的查找方式呢，因为生成就是确定需要排序的对象，所以先确定了对象，然后通过一个友好的容易操作的界面面向用户，这样即使用户对计算机一窍不通，也能够轻松的使用这个系统进行随机数的各种排序了。为了使用户能够在进行了一项操作之后还能进行另外的操作，例如：快速排序之后还可以继续选择堆排序等等。所以让程序一直执行，直到用户输入退出的信息后才中止程序，这样做程序显得更人性化些！

到此，整个程序也就完成了。 3.3实验结果

文件存储排序部分结果如下图：

图0

15

西华大学理学院课程设计说明书

4．系统测试和结果分析

4.1设计测试数据

随机生成2000个数(为了直观一些我本次调试只是生成了200个随机数) 4.2调试的详细过程

对于所有执行过程，通过图片最好说明问题了，程序开始如下图所示： 0. 运行程序初始界面：

图 1

1.生成随机数，按任意键即可，如下图2：

图 2

2.点击任意键继续 ，弹出选择菜单，并提示用户选择需要的服务如图3：

16

排序综合

图 3

4.选择“1”服务时，如图4/1-2所示：

图 4.1

图4.2

5.这时用户可继续选择进行操作，如果选“2”服务时，如图5/1-2所示：

17

西华大学理学院课程设计说明书

图5.1

图5.2

6.输入了“3”服务时，如图6/1-2所示：

18

排序综合

图6.1

图 6.2

6.输入了“4”服务时，如图7/1-2所示：

19

西华大学理学院课程设计说明书

图7.1

图7.2

7.输入了“5”服务时，如图8/1-2所示：

20

排序综合

图8.1

图8.2

8.输入了“6”服务时，如图9/1-2所示：

图9.1

21

西华大学理学院课程设计说明书

图 9.2

9.输入了“7”服务时，如图10所示：

图 10

整个对随机数的产生，快速排序、冒泡排序、直接插入排序、归并排序、简单选择排序、堆排序的操作过程就是这样，很简单。

5、算法效率的分析 5.1 耗费时间

对20000个随机数各种排序平均运行时间统计如下表：

快速排序 冒泡排序 0.001s

0.009s 直接插入排序 0s 归并排序 0.059s 简单选择 0.021s 堆排序 0.001s 5.2性能分析

(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。

当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜；

(3)若n较大，则应采用时间复杂度为的排序方法：快速排序、堆排序或归并排序。

22

排序综合

（4）堆排序适合于数据量非常大的场合（百万数据）。堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。

5.3时间效率

1. 插入排序的算法的时间复杂度为：

2. 希尔排序的算法的时间复杂度为n的1.2次幂

3. 冒泡排序的算法的时间复杂度为：O（n^2）。当数据为正序，将不会有交换，复杂度为O(n)。

4. 快速排序的算法时间复杂度为：O(nlogn),是所有内部排序方法中最好的，大多数情况下总是最好的。

5. 简单排序的算法的时间复杂度为O(n^2)： 6. 堆排序的算法的时间复杂度为：O(nlogn)

23

西华大学理学院课程设计说明书

总 结

在一个学期后的基础理论知识的学习后进入实践的操作虽然仍就有些困难但也是另一种进步的好途径。这次的课程设计主要是对基础知识的灵活使用，这就让我进一步提高了对数据结构知识的巩固。这次设计的完成，困难是少不了的，还有许多其他的难题让我都曾不知所措，但通过努力最终解决它们让我体会到成就感，更重要的是我的能力在无形中得到了提升和优化。

这次课程设计的心得体会通过实习我的收获如下:1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。

我通过课程设计建立系统设计的整体思想，锻炼编写程序、调试程序的能力，学习文档编写规范，培养独立学习、吸取他人经验。同时，充分弥补了课堂教学及普通实验中知识深度与广度有限的缺陷，更好地帮助从全局角度把握课程体系，并且可以将理论与实际联系。在课程设计的过程中不仅仅是书本上的知识，这便促使我去查阅更多的课外资料来充实自己的内容，同时学会在面对困难时要耐心得分析它细心得解决它以及通过合作更完美得深入了解剖析它以便得到提高。细心、耐心、团结、求知，是我这次课程设计最大的收获。

24

排序综合

致 谢

本次设计是在陈晓亮老师的悉心指导和热心帮助下完成的。他给我的程序设计和论文提出了很多宝贵的意见，并给我作了仔细的修改。在他的鼓励与耐心的指导下，我的设计和论文才能快速、保质量完成。在和陈老师的接触中，他给我以毫不保留的指导，促进了我对专业知识的巩固和提高，让我受益匪浅。然后还要感谢大学的所有的老师，为我打下博大精深的专业知识的基础，同时还要感谢所有的同学们，正是因为有了大家的相互学习相互交流，才让我有了做题灵感，正是因为有了你们的支持和鼓励，此次设计才会顺利完成。在此，衷心的谢谢您们

总之，数据结构课程设计让我受益良多，我会好好珍惜像这种难得的机会，努力学习知识。也感谢帮助了我的老师、同学。

25

西华大学理学院课程设计说明书

参考文献

[1] 严蔚敏，吴伟民，数据结构（C语言版）.北京：清华大学出版社，1997 [2] 谭浩强，C程序设计（第三版）.北京：清华大学出版社，2005

[3] Jeri R.Hanly，Elliot B. Koffman，问题求解与程序设计C语言版（第四版）.北京：清华大学出版社，2007-1

[4] 何钦铭，颜晖，C语言设计教程.北京:高等教育出版社，2008年 [5] 吴文虎，程序设计基础.北京:清华大学出版社，2003

26

排序综合

附 录

// 数据结构3一元多项式的加减乘.cpp : 定义控制台应用程序的入口点。 //

//========================二叉树的遍历============================ //========================执行软件VS2010========================== //========================发布日期：2015-11-28==================== #include \#include #include #include #include #include #include #include #include #include #include

//====================头文件===================== #define M 200 //产生随机数个数的定义 const int MAXSIZE = 20000; typedef struct{

int key;

}RedType; typedef struct{ RedType r[MAXSIZE + 1];

int length;

}Sqlist;

typedef Sqlist HeapType; clock_t start, finish; using namespace std;

27

西华大学理学院课程设计说明书

//////============基本排序算法=================/////// void Merge(RedType SR[], RedType TR[], int i, int m, int n); void MSort(RedType SR[], RedType TR1[], int s, int t); int SelectMin(int a[], int i, int m); int Partition(Sqlist &L, int low, int high); void Qsort(Sqlist &L, int low, int high); void HeapAdjust(HeapType &H, int s, int m); void HeapSort(HeapType &H);

double duration(clock_t x, clock_t y);

/////////=========================================/////////////// void control(int a[]); void menu();

/////////==============具体排序函数================////////// //快速选择排序

void quick_select_sort(int a[]); //冒泡排序

void bubble_sort(int a[]); //插入排序

void insert_sort(int a[]); //归并排序

void merge_sort(int a[]); //简单选择排序

void simple_select_sort(int a[]); //堆排序

void heap_sort(int a[]);

/////////////====================================//////////////// void main() {

28

printf(\

printf(\功 能： 排 序 综 合\\n\\n\

排序综合

printf(\编 译 环 境：V S 2 0 1 0\\n\\n\printf(\发 布 日 期：2 0 1 5 - 1 1 - 2 5\\n\\n\

printf(\程序开始！***********************\\n\int i, arr[M];

//定义i,j；待排序数组arr[M];

srand((unsigned)time(NULL));//设置随机种子; for (i = 1; i < M + 1; i++)

arr[i] = rand() % 5000; //随机生成待排序数组a;

printf(\产生200个随机数\\\\/\\n\system(\

for (i = 1; i < M + 1; i++) //每个元素占6个字符，每行十个元素的格式输出随机生成的待

排序数组a;

{ }

system(\

cout << setw(6) << arr[i] << \if (i % 10 == 0)

printf(\

fflush(stdin);//清除文件缓冲区，文件以写方式打开时将缓冲区内容写入文件;为了确保不影响后面的数据读取; }

void control(int a[]) {

menu(); char ch; while (1) {

scanf_s(\switch (ch) {

29

control(arr);

//字符ch,用于记录选项;

//获取选项,选择相应的排序算法;

西华大学理学院课程设计说明书

30

case '1':

//快速选择排序 quick_select_sort(a); system(\getchar(); menu(); break;

case '2':

//冒泡排序; bubble_sort(a); system(\getchar(); menu(); break;

case '3':

//直接插入排序 insert_sort(a); system(\getchar(); menu(); break;

case '4':

//归并排序算法; merge_sort(a); system(\getchar(); menu(); break;

case '5':

//简单选择排序;

排序综合

simple_select_sort(a); system(\ getchar(); menu();

break;

case '6': //堆排序算法; heap_sort(a); system(\ getchar(); menu();

break;

case '7': //结束程序;

printf(\谢谢您的使用！\\n\ system(\ exit(1); getchar();

break;

default: printf(\输入错误,请重新输入!\\n\ break;

}

}

} //主菜单 void menu() { printf(\菜 单\\n\

printf(\

31

西华大学理学院课程设计说明书

printf(\请选择你要使用的排序方法:\\n\

printf(\快速排序;\\n\\t\\t2.起泡排序;\\n \\t\\t3.直接插入排序;\\n \\t\\t4.归并排

序;\\n\ }

//快速选择排序

void quick_select_sort(int a[]) {

32

printf(\简单选择排序;\\n\\t\\t6.堆排序;\\n\\t\\t7.退出.\\n\printf(\

int i; Sqlist L;

//声明结构体; //初始化长度为0;

//快速选择排序结果保存文件;

//初始化快速选择排序结构链表的数据;

L.length = 0;

ofstream output(\快速排序.txt\for (i = 1; i < M + 1; i++) { }

start = clock(); Qsort(L, 1, M);

L.r[i].key = a[i]; L.length++;

//将待排序的数组数据存入排序算法的结构体中;

//计算排序算法结构的长度length;

//开始算法执行时间计时; //调用快速排序算法进行排序;

finish = clock(); //终止算法执行时间计时; printf(\显示快速排序结果:\\n\

for (i = 1; i < M + 1; i++) //每个元素占6个字符,以空格隔开，每100个元素换行保存排序 { }

for (i = 1; i < M + 1; i++) //每个元素占6个字符,以空格隔开，每10个元素换行输出排序

output << setw(6) << L.r[i].key << \if (i % 100 == 0)

printf(\

排序综合

{ }

printf(\快速排序完成,结果已保存!\\n\

cout << \快速排序消耗时间为: \秒\//输出

cout << setw(6) << L.r[i].key << \if (i % 10 == 0)

printf(\

快速算法耗时(s); }

//冒泡排序

void bubble_sort(int a[]) {

int i,j,t;

//定义整形数据t

//建立冒泡排序结果保存文件;

ofstream output(\冒泡排序.txt\start = clock();

//开始起泡排序算法执行时间计时

//执行起泡排序算法

for (j = 1; j < M + 1; j++) { }

for (int i = 1; ia[i + 1]) { }

t = a[i]; a[i] = a[i + 1]; a[i + 1] = t;

finish = clock(); //终止冒泡排序算法执行时间计时 printf(\显示冒泡排序结果:\\n\

for (i = 1; i < M + 1; i++)//每个元素占6个字符,以空格隔开，每100个元素换行保存排序后

{

output << setw(6) << a[i] << \

33

西华大学理学院课程设计说明书

}

if (i % 100 == 0)

printf(\

for (i = 1; i < M + 1; i++)//每个元素占6个字符,以空格隔开，每10个元素换行输出排序后数组;

{ }

printf(\冒泡排序完成,结果已保存!\\n\

cout << \冒泡排序消耗时间为: \秒\//输出

cout << setw(6) << a[i] << \if (i % 10 == 0)

printf(\

起泡排序算法耗时(s); }

//插入排序

void insert_sort(int a[]) {

34

//system(\

int i, j; Sqlist L;

//声明结构体;

//初始化结构体长度为0;

//建立直接插入排序结果保存文件; //初始化直接插入排序结构体中的数据;

L.length = 0;

ofstream output(\直接插入排序.txt\for (i = 1; i < M + 1; i++) { }

start = clock();

L.r[i].key = a[i]; L.length++;

//开始直接插入排序算法执行时间计时;

//执行插入排序算法;

for (i = 2; i <= L.length; ++i) {

if (L.r[i].key < L.r[i - 1].key)

排序综合

}

finish = clock(); //结束直接插入排序算法执行时间计时;

printf( \显示直接插入排序的结果:\\n\每个元素占6个字

{ }

L.r[0] = L.r[i]; L.r[i] = L.r[i - 1];

for (j = i - 2; L.r[0].key < L.r[j].key; --j)

L.r[j + 1] = L.r[j];

L.r[j + 1] = L.r[0];

符,以空格隔开，每100个元素换行保存排序后数组;

{ }

output << setw(6) << L.r[i].key << \if (i % 100 == 0)

printf(\

for (i = 1; i < M + 1; i++)//每个元素占6个字符,以空格隔开，每10个元素换行输出排序后数组;

{ }

printf(\直接插入排序完成,结果已保存!\\n\

cout << \直接插入排序消耗时间为 \秒\

//

cout << setw(6) << L.r[i].key << \if (i % 10 == 0)

printf(\

输出直接排序算法耗时(s); }

//归并排序

void merge_sort(int a[]) {

35

//system(\

西华大学理学院课程设计说明书

int i; Sqlist L;

//声明结构体; //初始化结构体长度;

//建立归并排序算法结果保存文件;

//初始化排序结构体中的数据;

L.length = 0;

ofstream output(\归并排序.txt\for (i = 1; i < M + 1; i++) { }

start = clock();

L.r[i].key = a[i]; L.length++;

//开始归并排序算法执行时间计时;

//调用归并排序算法;

MSort(L.r, L.r, 1, L.length);

finish = clock(); //结束归并排序算法执行时间计时; printf(\显示归并排序结果:\\n\

for (i = 1; i < M + 1; i++) //每个元素占6个字符,以空格隔开，每100个元素换行保存排序

后数组;

{ }

for (i = 1; i < M + 1; i++) //每个元素占6个字符,以空格隔开，每10个元素换行输出排序

output << setw(6) << L.r[i].key << \if (i % 100 == 0)

printf(\

后数组;

{ }

printf(\归并排序完成,结果已保存!\\n\

cout << \归并排序消耗时间为: \秒\//输出

cout << setw(6) << L.r[i].key << \if (i % 10 == 0)

printf(\

归并排序算法耗时(s);

36

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