数据结构（课程设计）排序算法时间性能的分析.doc

《数据结构》课程设计报告 目录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc 1 需求分析 PAGEREF _Toc \h 1 HYPERLINK \l _Toc 1.1 问题描述 PAGEREF _Toc \h 1 HYPERLINK \l _Toc 1.2 设计内容 PAGEREF _Toc \h 1 HYPERLINK \l _Toc 2概要设计 PAGEREF _Toc \h 2 HYPERLINK \l _Toc 2.1 原始数据 PAGEREF _Toc \h 2 HYPERLINK \l _Toc 2.2 程序的流程 PAGEREF _Toc \h 2 HYPERLINK \l _Toc 2.3 总体设计图 PAGEREF _Toc \h 3 HYPERLINK \l _Toc 3详细设计和编码 PAGEREF _Toc \h 4 HYPERLINK \l _Toc 3.1 算法基本思想 PAGEREF _Toc \h 4 HYPERLINK \l _Toc 3.2 算法描述 PAGEREF _Toc \h 4 HYPERLINK \l _Toc 3.3 算法设计 PAGEREF _Toc \h 5 HYPERLINK \l _Toc 3.4算法时间分析 PAGEREF _Toc \h 8 HYPERLINK \l _Toc 4测试结果 PAGEREF _Toc \h 9 HYPERLINK \l _Toc 5小结 PAGEREF _Toc \h 9 HYPERLINK \l _Toc 参考文献 PAGEREF _Toc \h 10 HYPERLINK \l _Toc 附录：程序源代码 PAGEREF _Toc \h 10 PAGE \* MERGEFORMAT PAGE \* MERGEFORMAT 1 1 需求分析 1.1 问题描述 (1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。于是数据为整数。 (2) 输出的形式：输出在各种数目的随机数下，各种排序算法所用的时较次数。 (3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。 （4）测试数据。 1.2 设计内容 对各种排序方法（快速排序、堆排序、希尔排序、冒泡排序、归并排序）的时间性能进行比较。 设计并实现上述各种排序算法； 在排序中实现比较时间性能； 在输入中分别调用上述排序算法，并比较时间性能。 2概要设计 2.1 原始数据 1.抽象数据类型 ADT List 数据对象 D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系 R1＝{ ai-1 ,ai |ai-1 ,ai∈D, i=2,...,n } 基本操作 virtual void clear() = 0; bool insert(const Elem) = 0; bool append(const Elem) = 0; lbool remove(Elem) = 0; void setStart() = 0; void setEnd() = 0; void prev() = 0; void next() = 0; int leftLength() const = 0; int rightLength() const = 0; bool setPos(int pos) = 0; bool getValue(Elem) const = 0; void print() const = 0; 2.2 程序的流程 （1）输入模块：输入要排序的数的数量n。 （2）处理模块：系统产生n个随机数，对随机数进行排序。 （3）输出模块：将排序的结果输出。 2.3 总体设计图 主程序 主程序 冒泡排序 快速排序 堆排序 希尔排序 归并排序 主程序堆排序 主程序 堆排序 快速排序 冒泡排序 希尔排序 归并排序 输出整理排序数据，作出分析。 输入数据 图 SEQ 图 \* ARABIC 1 3详细设计和编码 3.1 算法基本思想 1.随机数的产生：利用sra