课程设计数据结构分析.docVIP

数据结构课程设计 题目排序综合2014/7/10 1、需求分析 1.1任务与分析 利用随机函数产生N个随机整数（20000以上），对这些数据使用多种方法进行排序。 基本要求： 1、至少采用五种方法（至少包括希尔排序、快速排序、堆排序）实现上述问题求解； 2、统计每一种方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法； 3、统计每种算法所用的比较次数和交换次数，最后列表显示。 根据所学内容，本程序列举了直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序六种排序方法。 1.2模块的划分 1.2.1输入模块 利用随机函数产生N个随机整数（20000以上），产生的数据个数由用户自己输入。 1.2.2输出模块 根据要求列表输出每一种算法所花费的时间、所用的比较次数和交换次数。 1.2.3程序功能 本程序是一个关于排序的综合系统，可以利用所写程序熟练掌握六种排序算法，找出时间性能最好的两种算法，输出每种算法所用的比较次数和交换次数，横向对比六种算法的优缺点。 1.2.4测试数据 2、概要设计 2.1抽象数据类型定义 SORT ADT { 数据对象：N=随机产生的数据元素； 基本操作： void InsertSort(int* r,int compare,int exchange )； void ShellSort(int* r,int compare,int exchange )； void BubbleSort(int* r,int compare,int exchange )； int Partition(int * r,int first,int end,int compare,int exchange)； void QuickSort(int* r,int compare,int exchange )； void SelectSort(int * r,int first,int end,int compare,int exchange)； void Sift(int * r,int k,int m,int compare,int exchange)； void HeapSort(int * r,int compare,int exchange)； } ADT SORT 2.2主程序流程 （1）先构造直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序六种排序方法的算法实现； （2）再构造随机函数的算法，利用随机函数产生N个随机整数（20000以上）。 （3）最后调用插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序六种排序方法的算法，并依次输出每一种算法所花费的时间、所用的比较次数和交换次数。 2.3函数调用关系 3、详细设计 3.1模块的分工 根据程序的要求，我主要设计希尔排序、快速排序、堆排序的算法，并构造随机函数，利用随机函数产生N个随机整数（20000以上）。 3.1.1希尔排序 （1）基本思想 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量dt=1(dtdt-l…d2d1)，即所有记录放在同一组中进行直接插入排序为止。一趟快速排序的算法1）设置两个变量i、j，排序开始的时候：i=0，j=N-1； 2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]； 3）从j开始向前有哪些信誉好的足球投注网站，即由后开始向前有哪些信誉好的足球投注网站(j--)，找到第一个小于key的值A[j]，将A[j]赋给A[i]； 4）从i开始向后有哪些信誉好的足球投注网站，即由前开始向后有哪些信誉好的足球投注网站(i++)，找到第一个大于key的A[i]，将A[i]赋给A[j]； 5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。（2）大根堆排序算法的具体步骤： 初始化操作：将R[1..n]构造为初始堆； 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。void ShellSort(int r[],int n) { for(d=n/2;d=1;d=d/2) { for(i=d+1;i=n;i++) { r[0]=r[i]; for(int j=i-d;j0r[0]r[j];j=j-d) r[j+d]=r[j]; r[j+d]=r[0];