课程设计说明书

兰州理工大学。

计算机与通信学院。

2024年春季学期。

算法与数据结构课程设计。

题目：排序算法性能分析。

专业班级：计算机（3）班。

姓名：马菊英。

学号： 09240339

指导教师：张永

成绩。排序（sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为内部排序和外部排序两种，在此讨论的是内部排序，所谓内部排序，就是先把待排序数据都放在内存中，再进行排序。

1)可利用连续的存储单元存放待排序记录，实现起泡排序、直接插入排序、选择排序、快速排序、希尔排序、堆排序、归并排序等功能；

2)利用随机函数产生n个随机整数，正序、逆序数据作为测试数据，各排序算法对这些合法的输入数据都能产生满足要求的结果；

3)各排序算法对随机产生的无序的n个整数也能够得出满足规格要求的结果，对算法实现过程中的异常情况能给出有效信息；

4) 由于各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间，可通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以及计算各排序花费时间，以取得直观的感受。

关键词：内部排序；随机整数；比较次数；移动次数；花费时间等。

排序（sorting）是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列。由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为内部排序和外部排序两种，在此讨论的是内部排序，所谓内部排序，就是先把待排序数据都放在内存中，再进行排序。

内部排序算法主要有：选择排序、起泡排序、直接插入排序、希尔排序、快速排序、堆排序、归并排序等。内部排序的方法很多，但就其全面性能而言，很难提出一种被认为是最好的方法，每一种方法都引各自的优缺点，适合在不同的环境（如记录的初始排列状态等）下使用。

因而对各种排序算法进行排序性能的分析有助于排序算法的选择，以便提高程序运行效率，节省程序运行的空间。由于知识学习有限，程序中有许多不足之处还望老师们批评指正，在以后的学习实践中我将努力学习改正。谢谢老师们！！！

问题描述。各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。可以通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以及各排序算法花费时间，以取得直观感受。

1）使用连续的存储单元存放待排序记录，实现插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等功能；

2）利用随机函数产生n个随机整数、正序、逆序数据作为测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；

3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息。

#define maxsize 30000 //定义随机数的个数限制在30000以内。

typedef int keytype定义关键字类型为整数类型。

typedef struct

从i=1；执行语句i++；直到i=n-1; 产生n-1个随机数据；

2) int nixu(int n)函数。

用于产生n-1个逆序排列的随机数据，也是利用for循环语for(i=n-1;i>=1;i--)数据从n-1开始产生。

产生n-1个逆序排列的随机整数。

3) int data(int n)函数。

随机的产生n-1个随机数据。

int data(int n)

time_t t;

int i;

srand((unsigned) time(&t));

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

a[i]=rand()%1000; /将随机产生的数据存放在数组a中。

r[i]=a[i];d[i]=a[i]; 将数组a中元素拷贝到数组r和d中

printf("%d ",a[i]);

printf("");

return 1;}

利用已定义的随机库函数srand()和rand(),加语句srand((unsigned) time(&t));

a[i]=rand()%1000; 将产生的随机整数存储在数组a中，并拷贝在数组r和d中。

4) int switch2 (char k,int &n)函数。

选择正序、逆序还是随机方式产生随机数；利用一个switch语句switch (k)

case 1:

case 2:

case 3:

default :break; }

输入1，执行函数zhengxu(n);产生n-1个正序排列的随机整数；

输入2，执行函数nixu(n); 产生n-1个逆序排列的随机整数；

输入3，执行函数data(n); 产生n-1个随机排列的随机整数；

5) int switch(char t,int n)函数。

用于选择并执行排序算法，同时计算排序花费时间。利用一个switch语句。

time_t start ,end;

switch(t)

case 1:

case 2:

case 3:{ start=clock();

xuanze(a,n);

end=clock();

usetime[3]=(end-start)*1.0/clocks_per_sec;

课程设计说明书

课程设计说明书

课程设计说明书

课程设计说明书

其他用户还读了