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

《数据结构课程设计排序算法时间性能的分析.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计排序算法时间性能的分析.doc（21页珍藏版）》请在沃文网上搜索。

1、数据结构课程设计报告 目录1 需求分析11.1 问题描述11.2 设计内容12概要设计22.1 原始数据22.2 程序的流程22.3 总体设计图33详细设计和编码43.1 算法基本思想43.2 算法描述43.3 算法设计53.4算法时间分析84测试结果95小结9参考文献10附录：程序源代码101 需求分析1.1 问题描述(1) 输入的形式和输入值的范围：本程序要求实现各种算法的时间性能的比较，由于需要比较的数目较大，不能手动输入，于是采用系统生成随机数。用户输入随机数的个数n，然后调用随机事件函数产生n个随机数，对这些随机数进行排序。于是数据为整数。(2) 输出的形式：输出在各种数目的随机数下

2、，各种排序算法所用的时较次数。(3) 程序所能达到的功能：该程序可以根据用户的输入而产生相应的随机数，然后对随机数进行各种排序，根据排序进行时间和次数的比较。（4）测试数据。1.2 设计内容对各种排序方法（快速排序、堆排序、希尔排序、冒泡排序、归并排序）的时间性能进行比较。（1） 设计并实现上述各种排序算法；（2） 在排序中实现比较时间性能；（3） 在输入中分别调用上述排序算法，并比较时间性能。2概要设计2.1 原始数据1.抽象数据类型ADT List 数据对象 D ai | ai ElemSet, i=1,2,.,n, n0 数据关系 R1 |ai-1 ,aiD, i=2,.,n 基本操作

3、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;

4、void print() const = 0;2.2 程序的流程（1）输入模块：输入要排序的数的数量n。（2）处理模块：系统产生n个随机数，对随机数进行排序。（3）输出模块：将排序的结果输出。2.3 总体设计图主程序冒泡排序快速排序堆排序希尔排序归并排序主程序堆排序快速排序冒泡排序希尔排序归并排序输出整理排序数据，作出分析。输入数据图 13详细设计和编码3.1 算法基本思想1.随机数的产生：利用srand()产生随机数。2.快速排序：选定一记录，将所有其他记录关键字与记录的关键字比较, 若则将记录换至之前,若则将记录换至之后，继续对前后两部分记录进行快速排序，直至排序范围为1。3.希尔排序：将

5、序列分割成若干子序列分别进行直接插入排序，待序列记录基本有序时再对整体进行一次直接插入排序。4.冒泡排序：比较并交换相邻的元素对，直到所有元素都被放到正确的地方为止。5.归并排序：将两个或者多个有序表归并成一个有序表。6.堆排序：首先将数组转化为一个满足堆定义的序列，然后将堆顶的最大元素取出，再将剩下的数排成堆，再取堆顶数值，。如此下去，直到堆为空。到最后结束时，就排出了一个由小到大排列的数组。3.2 算法描述（1）快速排序是对起泡排序的一种改进。它的基本思想是：通过一趟排序将待排记录分别分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字大小，则可分别对这两部分记录继续进行排序

6、，以达到整个序列有序。（2） 堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或大于）它的父结点。只需一记录大小的辅助空间，每个待排序的记录仅占用一个存储空间。它的思想是：先是对堆做比较，左子数小于本数，右子数大于本数，然后不停比较、交换，最后达到整个数组的排序。（3） 希尔排序它又称“缩小增量排序”，又是一种属插入排序类的方法，但在时间效率上有很大改进。它的思想是：先把数组分成等长的两个数组，用ri与rn/2+i比较小的在前，大的在后，然后在一刚刚两两一组的两组做比较，就这样，每次比较，每组数的个数都是上一次的两

7、倍，最后完成整个数组的排序。（4） 冒泡排序它是一种“交换”进行排序的方法之中最简单的一种。它的思想是：相邻的两个元素进行比较，将小的调到前面，大的调到后面。（5） 归并排序“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。它的算法思想是：先把数组对半分多次，直到每组只有两个数据时，进行比较、排序，然后再两两合并，最后做到整个数组的排序完成。3.3 算法设计（1）产生随机数：直接调用函数srand(),以时间作为随机种子进行选择，并把随机数装入数组中。unsigned long int *Sort:setRan(unsigned long int num)unsigned long

8、 int *ra;ra=(unsigned long int*)malloc(num*sizeof(unsigned long int);srand(time(NULL);for(unsigned long int m=0;mnum;m+)ram=rand();coutendl;return ra;（2）快速排序：要实现快速排序首先选择一个轴值，这里选取数组第一个为轴值。定义两个标识low,high。high标识最后一个元素的位置，从后向前，将关键字与轴值比较，直至遇到小于轴值的关键字，前移，low标识在第二个元素的位置，从前向后，将关键字与轴值比较，直至遇到大于轴值的关键字，后移。当low,

9、high相遇后第一趟排序结束。调整数列，轴值左边的为比轴值小的，右边为比轴值大的。对轴值左边（即low到pivotkey-1的数）和右边的子列（pivotkey+1到high的数）分别进行上述递归快速排序，直到范围为1结束。int partition(int a,int low,int high)/快速排序中的一趟 int pivotkey; /作为枢轴来使用 pivotkey=alow; while(lowhigh) while(low=pivotkey) -high; alow=ahigh; while(lowhigh&alow=pivotkey) +low; ahigh=alow; al

10、ow=pivotkey; return low;void qsort(int a,int low,int high)/快速排序的递归形式 int pivotloc; if(lowhigh) pivotloc=partition(a,low,high);/一趟排序结果的调用 qsort(a,low,pivotloc-1); qsort(a,pivotloc+1,high); （3） 希尔排序：先把数组分成等长的两个数组，用ri与rn/2+i比较小的在前，大的在后，然后在一刚刚两两一组的两组做比较，就这样，每次比较，每组数的个数都是上一次的两倍，最后完成整个数组的排序。void ShellInse

11、rt(sqList &L,int dk)/对顺序表L作一趟希尔插入排序。For (i=dk+1;i0<(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj;/记录后移，查找插入位置L.rj+dk=L.r0;/插入(4) 冒泡排序（bubble sort）：将被排序的记录数组R1.n垂直排列，每个记录Ri看作是重量为Ri.key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上飘浮。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交

12、换二者的位置。即依次比较(Rn，Rn-1)，(Rn-1，Rn-2)，(R2，R1)；对于每对气泡(Rj+1，Rj)，若Rj+1.keyRj.key，则交换Rj+1和Rj的内容。第一趟扫描完毕时，最轻的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R1上。扫描R2.n。扫描完毕时，次轻的气泡飘浮到R2的位置上最后，经过n-1趟扫描可得到有序区R1.n (5) 堆排序：将序列看成是完全二叉树，完全二叉树中所有非终端结点的值均不大于（或不小于)其左右孩子结点的值。若在输出堆顶最小值之后，使得剩余的元素序列又重建成一个堆，则得到次小值。如此反复，就得到一个有序序列。（6）归并排序：归并排序

13、是将一个无序数组n1r分成两个数组n1r/2与nr/2+1r，分别对这两个小数组进行归并排序，然后再将这两个数组合并成一个大数组。由此我们看出归并排序时一个递归过程。归并排序的主要工作便是“合并”，两个小规模数组合并成大的，两个大的再合并成更大的，当然元素比较式在合并的过程中进行的。3.4算法时间分析希尔排序：当n在某个特定范围内，希尔排序所需的比较次数和移动次数约为n的1.3次方，当n-无穷大时，可减少到n(log2n)22。冒泡排序：当原始数据正向有序时，冒泡排序出现最好情况。此时，只需进行一趟排序，作n-1次关键字比较，因此最好情况下的时间复杂度是O(n)。当原始数据反向有序时，冒泡排序

14、出现最坏情况。此时，需进行n-1趟排序，第i趟作(n-i)次关键字间的比较，并且需执行(n-i)次元素交换，所以，比较次数为：因此,最坏情况下的时间复杂度为O(n2)。快速排序：如果每一次分划操作后，左、右两个子序列的长度基本相等，则快速排序的效率最高，其最好情况时间复杂度为O(nlog2n)；反之，如果每次分划操作所产生的两个子序列，其中之一为空序列，此时，快速排序效率最低，其最坏情况时间复杂度为O(n2)。如果选择左边第一个元素为主元，则快速排序的最坏情况发生在原始序列正向有序或反向有序时。快速排序的平均情况时间复杂度为O(nlog2n)。堆排序：堆排序的时间，主要由建立初始堆和反复重建堆

15、这两部分的时间开销构成，它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlogn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是不稳定的，算法时间复杂度O(nlogn)。归并排序：在最佳、平均、最差情况下，时间复杂度为(n log n)，不足的就是需要两倍的空间代价，当输入的待排序数据存储在链表中时，归并排序是一个很好的选择.4测试结果1. 程序主界面图 25小结 通过此次课程设计使我更加深入的了解了各种排序算法的思想和基本原理。对内部排序算法的基本运算有所掌握，充分理解了各种排序算法的优缺点。学会了如何把学

16、到的知识用于解决实际问题，锻炼了自己的动手能力。在设计的整个过程中我遇到了很多问题，使我认识了自己的不足，还有很多地方有待改正和提高。但和同学积极沟通讨论，相互学习，相互帮助，一个人的力量是渺小的，但团结的力量是不容忽视的，也同样锻炼了我们的协作能力，为以后在学习工作中能更好发展打下了坚实的基础。这次课程设计使我受益匪浅。参考文献1王昆仑,李红等编著. 数据结构与算法. 北京:中国铁道出版社,2007.2苏仕华等编著. 数据结构课程设计. 北京：机械工业出版社 ,2005.3苏仕华编著. 数据结构与算法解析. 合肥:中国科学技术大学出版社,2004.4郭嵩山等著. 国际大学生程序设计竞赛例题解

17、. 北京:电子工业出版社,2008.5刘大有,唐海鹰等编著. 数据结构. 北京:高等教育出版社,2001.6徐孝凯编著.数据结构实用教程. 北京: 清华大学出版社,1999.7严蔚敏,陈文博编著. 数据结构及算法教程. 北京: 清华大学出版社,2001.8刘振安,刘燕君等编著. C 程序设计课程设计. 北京: 机械出版社,2004.9胡学钢. 数据结构与算法设计指导. 北京: 清华大学出版社, 1999.附录：程序源代码/*cout:输出 cin：输入 endl:换行system(pause)：屏幕暂停 （去掉这句屏幕瞬间自动关闭）*/#include#include#include#incl

18、ude using namespace std;/命名空间，使cout/cin起作用const int maxsize=9999;int num=0;/定义全局变量，为每一趟的输出做准备int x=0;templateclass sortlist private: int SortNum; int currentsize;/数据表中数据元素的个数 public: type *arr;/存储数据元素的向量（排序表） sortlist():currentsize(0)arr=new typemaxsize;/构造函数 sortlist(int n)arr=new typemaxsize;curre

19、ntsize=n; void insert(int i,type x)arri=x; sortlist()delete arr;/析构函数 void swap(type &x,type &y)/数据元素x和y交换位置 type temp=x;x=y;y=temp; void bubblesort();/冒泡排序 void selectsort();/快速排序 void heapsort();/堆排序 void mergesort(sortlist &table);/归并排序 void shellsort();/希尔排序 void filterdown(const int start);/建立最

20、大堆 void mergepass(sortlist&sourcetable,sortlist&mergedtable,const int len);/一趟归并 void merge(sortlist&sourcetable,sortlist&mergedtable,const int left,const int mid,const int right);/两路归并算法;template /冒泡排序OKvoid sortlist: bubblesort()SortNum = 0;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerfo

21、rmanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获取时间Count1int i=1;double d;int finish=0;/0表示还没有排好序while ( icurrentsize & !finish )finish=1;/排序结束标志置为,假定已经排好序for (int j=0; j arrj+1 )/逆序swap(arrj,arrj+1);/相邻元素交换位置finish=0;SortNum+;/排序结束标志置为,表示本趟发生了交换，说明还没有排好序i+;QueryPerformanceCounter(&Count2)

22、;/获取时间Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;cout冒泡排序算法,排序时间为d ms endl;cout冒泡排序算法，交换次数为 SortNumendl;num = 0; coutendl;template /快速排序OKvoid sortlist:selectsort()SortNum = 0;double d;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg)

23、;QueryPerformanceCounter(&Count1);/获取时间Count1int i=0;int finish = 0; /0表示还没有排好序while (icurrentsize-1 & ! finish)finish = 1;/排序结束标志置为，假定已经排好序for (int j=i+1; j arrj)swap (arri,arrj);finish = 0;SortNum+;i+;QueryPerformanceCounter(&Count2);/获取时间Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)F

24、reg.QuadPart*1000.0;cout快速选择排序算法,排序时间为d ms endl;cout快速选择排序算法，交换次数为 SortNum+endl;num = 0;/SortNum = 0;coutendl;template /建立最大堆void sortlist:filterdown(const int start)/向下调整使从start开始到currentsize-1为止的子表成为最大堆int i=start,j=2*i+1;/j为i的左孩子int tablesize=currentsize;type temp=arri;while (j = currentsize-1)if

25、 (jcurrentsize-1 & arrj= arrj)break;elsearri = arrj;i = j;j = 2*j+1;SortNum+;SortNum+;arri = temp;template /堆排序OKvoid sortlist:heapsort()SortNum = 0;double d;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获取时间Count1int tablesize=curr

26、entsize,i;for ( i=(currentsize-2)/2; i=0; i-)filterdown(i); /初始建堆for (i=currentsize-1; i=1; i-)swap(arr0,arri);/堆顶元素和最后一个元素交换currentsize-;filterdown(0);/重建最大堆QueryPerformanceCounter(&Count2);d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;cout堆排序算法,排序时间为d ms endl;cout堆排序算法，交

27、换次数为 SortNumendl;num = 0;/SortNum = 0;currentsize = tablesize;template /希尔排序OKvoid sortlist:shellsort()SortNum = 0;double d; LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获取时间Count1if (currentsize=1; div/=2) for (int i=div; icurrent

28、size; i+=div) for (int j=i; (arrj=0; j-=div) swap(arrj,arrj-div); SortNum+; QueryPerformanceCounter(&Count2);/获取时间Count2d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000.0;cout希尔排序算法,排序时间为d ms endl;cout希尔排序算法，交换次数为 SortNumendl;num = 0;/SortNum = 0;coutendl;template void sortlist

29、:merge(sortlist&sourcetable,sortlist&mergedtable,const int left,const int mid,const int right)int i=left,j=mid+1,k=left;/指针初始化/i是前一段的当前元素位置，j是后一段的当前元素位置，k是辅助数组的当前位置while (i=mid & j=right)if (sourcetable.arri = sourcetable.arrj)mergedtable.arrk = sourcetable.arri;i+;k+;SortNum+;elsemergedtable.arrk =

30、 sourcetable.arrj;j+;k+;SortNum+;if (i = mid)for (int p=k,q=i; q=mid; p+,q+)SortNum+;mergedtable.arrp = sourcetable.arrq;elsefor (int p=k,q=j; q=right; p+,q+)mergedtable.arrp = sourcetable.arrq;/把后一段复制到SortNum;mergedtable;template /归并排序循环调用它void sortlist:mergepass(sortlist&sourcetable,sortlist&merge

31、dtable,const int len)int i = 0;while (i+2*len = currentsize-1)/表示至少有个子序列merge(sourcetable,mergedtable,i,i+len-1,i+2*len-1);i+=2*len;SortNum+;if (i+len = currentsize-1)/若只有最后两个子序列merge(sourcetable,mergedtable,i,i+len-1,currentsize-1);SortNum+;else/若只有最后一个子序列for (int j=i; j=currentsize-1; j+)mergedtab

32、le.arrj=sourcetable.arrj;SortNum+;template /归并排序OKvoid sortlist:mergesort(sortlist &table )/按数据元素关键字非递减的顺序对排序表table中数据元素进行递归排序SortNum = 0;double d;LARGE_INTEGER Freg;LARGE_INTEGER Count1,Count2;QueryPerformanceFrequency(&Freg);QueryPerformanceCounter(&Count1);/获取时间Count1sortlist temptable;int len=1;

33、while (len currentsize)mergepass(table,temptable,len);len*=2;mergepass(temptable,table,len);len*=2;QueryPerformanceCounter(&Count2);d=(double)(Count2.QuadPart-Count1.QuadPart)/(double)Freg.QuadPart*1000;cout归并排序算法,排序时间为d ms endl;cout归并排序算法，交换次数为 SortNumendl;num = 0;int main()/主函数 int c=1; while ( c

34、!= 0) cout=排序的时间性能的分析=endlendl;cout=5种排序的排序时间和交换次数=endl;int n,number ;coutn;srand(int)time(NULL); sortlisttable(n);int i;for ( i=0; in; i+)number = 100+rand()%(10000-100+1);table.insert(i,number); table.bubblesort();/冒泡排序 coutendl; table.heapsort();/堆排序OK coutendl;table.mergesort(table);/归并排序OK coutendl;for (i=0; in; i+)number = 100+rand()%(10000-100+1);table.insert(i,number);table.selectsort();/快速选择排序coutendl; for (i=0; in; i+)number = 100+rand()%(10000-100+1);table.insert(i,number);table.shellsort();/希尔排序coutendl;system(pause);return 0; .忽略此处.20