数据结构课程设排序算法时间性能的分析.docVIP

目录 1 需求分析 1 1.1 问题描述 1 1.2 设计内容 1 2概要设计 2 2.1 原始数据 2 2.2 程序的流程 2 2.3 总体设计图 3 3详细设计和编码 4 3.1 算法基本思想 4 3.2 算法描述 4 3.3 算法设计 5 3.4算法时间分析 8 4测试结果 9 5小结 9 参考文献 10 附录：程序源代码 10 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 总体设计图 图 1 3详细设计和编码 3.1 算法基本思想 1.随机数的产生：利用srand()产生随机数。 2.快速排序：选定一记录，将所有其他记录关键字与记录的关键字比较, 若则将记录换至之前,若则将记录换至之后，继续对前后两部分记录进行快速排序，直至排序范围为1。 3.希尔排序：将序列分割成若干子序列分别进行直接插入排序，待序列记录基本有序时再对整体进行一次直接插入排序。 4.冒泡排序：比较并交换相邻的元素对，直到所有元素都被放到正确的地方为止。5.归并排序：将两个或者多个有序表归并成一个有序表。 6.堆排序：首先将数组转化为一个满足堆定义的序列，然后将堆顶的最大元素取出，再将剩下的数排成堆，再取堆顶数值，…。如此下去，直到堆为空。到最后结束时，就排出了一个由小到大排列的数组。 3.2 算法描述 （1）快速排序 是对起泡排序的一种改进。它的基本思想是：通过一趟排序将待排记录分别分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字大小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 堆排序 是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或大于）它的父结点。只需一记录大小的辅助空间，每个待排序的记录仅占用一个存储空间。它的思想是：先是对堆做比较，左子数小于本数，右子数大于本数，然后不停比较、交换，最后达到整个数组的排序。 希尔排序 它又称“缩小增量排序”，又是一种属插入排序类的方法，但在时间效率上有很大改进。它的思想是：先把数组分成等长的两个数组，用r[i]与r[n/2+i]比较小的在前，大的在后，然后在一刚刚两两一组的两组做比较，就这样，每次比较，每组数的个数都是上一次的两倍，最后完成整个数组的排序。 冒泡排序 它是一种“交换”进行排序的方