湖州师范学院数据结构DS大作业

求真学院

数据结构课程设计大作业

20142832班

题 目： 专 业： 学生姓名： 学 号 指导教师 完成日期：

排序效率的比较 计算机科学与技术

邵 斌

湖州师院求真学院信息工程系

目 录

一、 二、 三、 四、 五、 六、 七、

实验内容概述 ............................................................................................................................... 1 实验目的概述 ............................................................................................................................... 1 解题思路的描述 ........................................................................................................................... 1 源程序清单 ................................................................................................................................... 1 程序调试及测试结果 ................................................................................................................... 8 结论 ............................................................................................................................................... 9 参考文献 ..................................................................................................................................... 10

I

此处写大作业题目（宋体三号，居中）

【内容摘要】

200至300字左右，楷体BG2312五号

【关键字】XXXX，XXXXX，XXXXX，XXXXX(3到5个)

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素和集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率，处理各种问题。 该程序是用C语言编写的，它充分体现数据结构的理念与算法的魅力。 该程序植入多种排序方法，这些排序方法的算法各具有特色，利用多种算法达到同一效果，正所谓“条条大路通罗马”。并且，该程序还收集各算法的运行时间，通过对耗时的比较，为用户挑选出两种最优化的排序方法。

关键字：排序 逻辑运算 数据结构 时间复杂度

【Abstract】

中文摘要的翻译，五号，Times New Roman

【Key words】XXXXX，XXXXX，XXXXX，XXXXX

Data structure is the way of computer storage and organization data. A data structure is a data element and a set of data elements that have one or more specific relationships between each other. Typically, carefully selected data structures can be brought to a higher running or storage efficiency, processing a variety of problems.

The program is written in C language, it fully reflects the concept of data structure and algorithm charm. The program is implanted in a variety of sorting methods, these sorting algorithms have the characteristics of each algorithm, the use of a variety of algorithms to achieve the same effect, is the so-called \lead to Rome\comparison, for the user to pick out two kinds of optimization of the sorting method. Keywords: sorting logic operation data structure time complexity

一、 实验内容概述

对于直接插入排序、选择排序、冒泡排序、Shell排序、快速排序和堆排序等几种常见的排序算法进行练习，并且比较各算法在不同长度数据下的优劣。

要求：（１）被排序的对象由计算机随机生成，长度分别取２０，１００，５００三种。

（２）程序中要有对各种排序算法的比较，具体为比较次数和移动次数的统计。 （３）对课设的结果做比较分析

二、 实验目的概述

1. 巩固和加深学生对数据结构算法的理解，提高综合运用所学课程知识的能力；

2. 通过各个排序算法的实现，练习包括文件的读写、动态内存的申请、函数的应用、指针的应用等多种最基本的C语言操作；

3. 锻炼学生的动手能力与培养其独立思考的能力。

三、 解题思路的描述

这是一个算法性能评价的程序，重点在于算法的性能评价上。实现排序功能可以有多种方法，判断一个算法性能好坏的标准主要有时间复杂度和空间复杂度。在当今系统资源相对充足的计算机系统中，时间复杂度便成为最主要的评价标准。

对于每一个排序算法，都应当有两个返回值：比较次数和移动次数。这里采用指针传递地址的方式，通过修改形参的地址从而可以改变实参的值。每个排序算法中除了含被排序对象指针外，还有两个整型变量指针，用于传递算法执行过程中的比较次数和移动次数。

取定一种排序对象的长度，由计算机产生一定量的伪随机数后，主函数调用各个排序子函数，但由于排序对象也是指向一维数组的指针，在调用一次一种排序算法后，通过形参对指针的改变，被排序对象已经是有序的了。当再次调用其他函数时有可能使比较和移动次数达到最大或最小，就失去了比较的意义。因此，本程序中采用了子函数另开辟空间，参数只起到一个复制值的作用，在每个子函数结束前用delete() 来释放申请排序对象的指针，避免程序出现内存耗尽的情况。

四、 源程序清单

主要包括： #include #include #include int a[501],b[501]; int len;

//数组长度

void number()

1