课程设计（论文）各种排序时间在不同情况下的时间消耗

1、课程设计(论文)任务书一、课程设计(论文)题目 各种排序时间在不同情况下的时间消耗 二、课程设计(论文)工作自 2007 年1月 8 日起至 2007 年 1月 12 日止。三、课程设计(论文) 地点: 15栋软件学院机房 四、课程设计(论文)内容要求：1本课程设计的目的1、使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 2课程设计的任务及要求1）基本要求：1.分析题

2、目，查阅相关资料；2.算法设计、数据结构设计； 3.编写代码并调试；4.完成课程设计报告。 2）创新要求： 在基本要求达到后，可进行创新设计，如对。3）课程设计论文编写要求（1）要按照书稿的规格打印誊写毕业论文（2）论文包括目录、绪论、正文、小结、参考文献、谢辞、附录等（3）毕业论文装订按学校的统一要求完成4）答辩与评分标准： （1）完成问题的解决方法分析：20分； （2）算法思想（流程）：20分； （3）数据结构：20分；（4）测试数据：20分（5）回答问题：20分。5）参考文献： 数据结构清华大学出版社 在网上搜索了测试代码时间消耗，产生随机数的相关函数 6）课程设计进度安排内容 天数地点

3、构思及收集资料 2图书馆组装与调试 5实验室撰写论文 3图书馆、实验室学生签名： 年 月 日课程设计(论文)评审意见（1）完成问题分析（20分）：优（）、良（）、中（）、一般（）、差（）； （2）算法思想（20分）：优（）、良（）、中（）、一般（）、差（）； （3）数据结构（20分）：优（）、良（）、中（）、一般（）、差（）；（4）测试数据 （20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人： 职称： 讲师 年 月 日目 目录 目 录-3 -正 文- 4 -一、问题描述

4、 - 4 -二、基本要求 - 4 -三、测试数据 - 4 -四、算法思想 - 4 -五、模块划分 - 6 -六、数据结构（附流程图） - 6 -七、源程序 - 7 -八、测试情况 - 24 -九、课程设计体会 - 27 - 一.问题描述： 测试 直接插入排序，折半插入排序，希尔排序，冒泡排序，双向冒泡排序，快速排序，简单选择排序，堆排序，基数排序排序算法，在不同的数据测试下（数据量的多少和数据的大小）所消耗的时间，及怎样提高排序的效率 二.基本要求：精确测试上述各种排序对同样的数据进行排序所消耗的时间，分析各种排序的在不同情况下的优劣三.测试数据： 每次进行排序的数据量，数据的范围可有用户输入

5、，确定数据范围和数量后，由系统自动产生随机数四.算法思想： 1 直接插入排序：最简单的排序方法，基本思想是将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增1的有序表2 折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现，即为折半插入排序3 希尔排序：先将整个待排记录分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序4 冒泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第n-1和第n个记录的关键字进

6、行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前n-1个记录进行同样操作。一共要进行n-1趟起泡排序5 快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序6 简单选择排序：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1=i=n）个记录交换7 堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前n-1记录进行选择，重新将它调整成

7、一个大顶堆，如此反复直到排序结束8 基数排序：按最低位优先法先对低位关键字进行排序，直到对最高位关键字排序为止，经过若干次分配和收集来实现排序五.模块划分：0 void random(long p,long n,long a,long b)：产生随机数 1 void straightinsertionsort(long p,long n) 直接插入排序，调用api相关函数计算直接插入排序的所消耗的时间2 void binaryinsertionsort(long p,long n) 折半插入排序，调用api相关函数计算折半插入排序的所消耗的时间3 void shellsort(long p,l

8、ong n) 希尔排序，调用api相关函数计算希尔排序所消耗的时间4 void bubblesort(long p,long n) 冒泡排序，调用api相关函数计算冒泡排序所消耗的时间5 void bubblesort_2(long p,long n) 双向冒泡排序，调用api相关函数计算双向冒泡排序所消耗的时间1 void quicksort(long p,long n) 快速排序，调用api相关函数计算快速排序所消耗的时间2 void selectsort(long p,long n) 简单选择排序，调用api相关函数计算简单选择排序所消耗的时间3 void heapsort(long p

9、,long n) 堆排序，调用api函数计算堆排序所消耗的时间4 void radixsort(long p,long n,int radix) 基数排序，调用api相关函数计算基数排序所消耗的时间5 void print(long p,long n) 输出排序结果，用来测试排序函数的正确性六.数据结构：程序流程图程序开始输出提示：输入将要产生随机数的个数和范围调用随机数函数，产生相应的随机数直接插入排序，并测试其时间消耗折半插入排序，并测试其时间消耗希尔排序，并测试其时间消耗快速排序，并测试其时间消耗冒泡排序，并测试其时间消耗双向起泡排序，并测试其时间消耗简单选择排序，并测试其时间消耗堆排序

10、，并测试其时间消耗基数排序，并测试其时间消耗是否继续程序结束七.源程序： #include #include 产生随机数#include 调用计算时间的函数#include using namespace std;产生随机数，输入产生随机数的个数，范围，即可产生待排数据void random(long p,long n,long a,long b)long max,min;if(ab)max=a-b+1;min=b;elsemax=b-a+1;min=a; srand(unsigned)time(null);for(long i=1;i=n;i+)pi=rand()%max+min; 输出排序

11、后的结果；用已检测排序的正确，是否能正确排序void print(long p,long n)coutn排序后的结果：;for(long i=1;i=n;i+)coutpi ;把字符数组p赋给q void initiate(long p,long q,long n)for(long i=1;i=n;i+)qi=pi;直接插入排序：排序并测试排序过程中的时间消耗void straightinsertionsort(long p,long n)long *q=new longn+1;initiate(p,q,n);large_integer m_liperffreq=0; queryperform

12、ancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart);for(long i=2;i=n;+i)if(qiqi-1) q0=qi;qi=qi-1;for(long j=i-2;q0qj;-j)qj+1=qj;qj+1=q0;large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quad

13、part; time/=m_liperffreq.quadpart;/ print(q,n); coutn直接插入排序时间消耗：time ms;delete q; 折半插入排序：排序并测试排序过程中的时间消耗void binaryinsertionsort(long p,long n)long *q=new longn+1;initiate(p,q,n);large_integer m_liperffreq=0; queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformanceco

14、unter(&m_liperfstart); for(long i=2;in;i+) q0=qi; long low=1; long high=i-1; while(low=high) long m=(low+high)/2; if(q0=high+1;-j) qj+1=qj; qhigh+1=q0; large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart

15、;/ print(q,n);coutn折半插入排序时间消耗：time ms;delete q; 希尔排序：排序并测试排序过程中的时间消耗void shellinsert(long q,long dk,long n)for(long i=dk+1;i=n;i+)if(qi0&(q0qj);j-=dk)qj+dk=qj;qj+dk=q0;void shellsort(long p,long n)long *q=new longn+1;initiate(p,q,n); large_integer m_liperffreq=0; queryperformancefrequency(&m_liperff

16、req); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart); long t=log(n-1)/log(2);for(long k=1;k=t;k+)long dk=1; for(long i=1;i=t-k;i+) dk=dk*2;if(t!=k)dk+=1;shellinsert(q,dk,n);large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_lipe

17、rfstart.quadpart; time/=m_liperffreq.quadpart; print(q,n);coutn希尔排序时间消耗：time ms;delete q;冒泡排序：排序并测试排序过程中的时间消耗void bubblesort(long p,long n)long *q=new longn+1;initiate(p,q,n); large_integer m_liperffreq=0; queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecount

18、er(&m_liperfstart); for(long j=1;j=n;j+)for(long i=1;iqi+1)long t=qi;qi=qi+1;qi+1=t;/print(q,n);large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;/ print(q,n);coutn冒泡排序时间消耗：time ms;delete q;双向起泡排序：排序并测

19、试排序过程中的时间消耗void bubblesort_2(long p,long n)long *q=new longn+1;initiate(p,q,n); large_integer m_liperffreq=0; queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart); long low=0;long high=n;int change=1;while(lowhigh&change)change=0;for(long i

20、=low;iqi+1)long t=qi;qi=qi+1;qi+1=t;change=1;high-;for(i=high;ilow;i-)if(qiqi-1)long t=qi;qi=qi+1;qi+1=qi;change=1; low+;large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;/ print(q,n);coutn双向起泡排序时间消耗：t

21、ime ms;delete q;递归形式的快速排序：排序并测试排序过程中的时间消耗long partition(long a,long low,long high)int m=alow;while(lowhigh)while(low=m)-high;alow=ahigh;while(lowhigh&alow=m)+low;ahigh=alow;alow=m;return low;void qsort(long a,long low,long high)if(lowhigh)int pivotloc=partition(a,low,high);if(pivotloc-lowhigh-pivotl

22、oc)/改进后的快速排序效率确实提高了 /先对长度短的那一部分进行排序qsort(a,low,pivotloc); qsort(a,pivotloc+1,high);elseqsort(a,low,pivotloc); qsort(a,pivotloc+1,high);void quicksort(long p,long n)long *q=new longn+1; initiate(p,q,n);large_integer m_liperffreq=0; queryperformancefrequency(&m_liperffreq); large_integer m_liperfstart

23、=0; queryperformancecounter(&m_liperfstart); qsort(q,1,n);large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperffreq.quadpart;/ print(q,n);coutn快速排序时间消耗：time ms;delete q;/ print(q,n);非递归形式的快速排序：用栈的性质void quicksort(long

24、p,long left,long right)long *q=new longright-left+2;initiate(p,q,right-left+1);struct stacklong left;long right;stack s99999;long top=-1,i,j,start,end,temp;if(left0)start=stop.left;end=stop.right;top-;long pivot=qstart;i=start;j=end;for(; ;)while(ij&qi=pivot)i+;while(ij&pivotqj)j-;if(ij)temp=qi;qi=q

25、j;qj=temp;i+;j-;elsebreak;qj=pivot;if(starti-1)top+;stop.left=start;stop.right=i-1;if(i+1end)top+;stop.left=i-1;stop.right=end;print(q,right-left+1);简单选择排序：排序并测试排序过程中的时间消耗void selectsort(long p,long n)long *q=new longn+1;initiate(p,q,n);large_integer m_liperffreq=0; queryperformancefrequency(&m_lipe

26、rffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart); for(long i=1;i=n;i+)long k=i;for(long j=i+1;j=n;j+)if(qjqk)k=j;long t=qk;qk=qi;qi=t;large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.quadpart; time/=m_liperf

27、freq.quadpart;/ print(q,n);coutn简单选择排序时间消耗：time ms;delete q; 堆排序：排序并测试排序过程中的时间消耗void heapadjust(long q,long s,long m)long rc=qs;for(long j=2*s;j=m;j*=2)if(jm&qj=qj)break;qs=qj;s=j;qs=rc;void heapsort(long p,long n) long *q=new longn+1;initiate(p,q,n); large_integer m_liperffreq=0; queryperformancefr

28、equency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart); for(long i=n/2;i0;i-)heapadjust(q,i,n);for(i=n;i1;i-)long t=q1;q1=qi;qi=t;heapadjust(q,1,i-1);large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart

29、.quadpart; time/=m_liperffreq.quadpart;/ print(q,n);coutn堆排序时间消耗：time ms;delete q;基数排序：排序并测试排序过程中的时间消耗void radixsort(long p,long n,int radix)struct radix 基数排序数据结构体long rc;radix * next;long *q=new longn+1;initiate(p,q,n);int l=1;radix * head11,* tail11;radix * p1,* p2; large_integer m_liperffreq=0; q

30、ueryperformancefrequency(&m_liperffreq); large_integer m_liperfstart=0; queryperformancecounter(&m_liperfstart); for(int t=1;t=radix;t+)for(int k=0;knext=0; tailk=headk;for(long i=1;irc=qi;p1-next=0;p2=headk;while(p2-next!=0)p2=p2-next;p2-next=p1;tailk=p1;for(k=0;k10;)for(long j=k+1;jnext)/tailk-next=headj-next;/ k=j;break;tailk-next=headj-next;k=j;p1=head0-next;i=1;while(p1)qi=p1-rc;p1=p1-next;i+;l*=10;large_integer liperfnow=0; queryperformancecounter(&liperfnow); double time=liperfnow.quadpart - m_liperfstart.