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

课程设计(论文)任务书一、课程设计(论文)题目 各种排序时间在不同情况下的时间消耗 二、课程设计(论文)工作自 2007 年1月 8 日起至 2007 年 1月 12 日止。三、课程设计(论文) 地点: 15栋软件学院机房 四、课程设计(论文)内容要求：1本课程设计的目的1、 使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法。2、使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。3、使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 2课程设计的任务及要求1）基本要求：1. 分析题目，查阅相关资料；2. 算法设计、数据结构设计； 3. 编写代码并调试；4. 完成课程设计报告。 2）创新要求： 在基本要求达到后，可进行创新设计，如对。3）课程设计论文编写要求（1）要按照书稿的规格打印誊写毕业论文（2）论文包括目录、绪论、正文、小结、参考文献、谢辞、附录等（3）毕业论文装订按学校的统一要求完成4）答辩与评分标准： （1）完成问题的解决方法分析：20分； （2）算法思想（流程）：20分； （3）数据结构：20分；（4）测试数据：20分（5）回答问题：20分。5）参考文献： 数据结构清华大学出版社 在网上搜索了测试代码时间消耗，产生随机数的相关函数 6）课程设计进度安排内容 天数地点构思及收集资料 2图书馆组装与调试 5实验室撰写论文 3图书馆、实验室学生签名： 年 月 日课程设计(论文)评审意见  （1）完成问题分析（20分）：优（）、良（）、中（）、一般（）、差（）； （2）算法思想（20分）：优（）、良（）、中（）、一般（）、差（）； （3）数据结构（20分）：优（）、良（）、中（）、一般（）、差（）；（4）测试数据 （20分）：优（）、良（）、中（）、一般（）、差（）；（5）回答问题（20分）：优（）、良（）、中（）、一般（）、差（）；（6）格式规范性及考勤是否降等级：是（）、否（）评阅人： 职称： 讲师 年 月 日目 目录 目 录-3 -正 文- 4 -一、问题描述 - 4 -二、基本要求 - 4 -三、测试数据 - 4 -四、算法思想 - 4 -五、模块划分 - 6 -六、数据结构（附流程图） - 6 -七、源程序 - 7 -八、测试情况 - 24 -九、课程设计体会 - 27 -       一. 问题描述： 测试 直接插入排序，折半插入排序，希尔排序，冒泡排序，双向冒泡排序，快速排序，简单选择排序，堆排序，基数排序排序算法，在不同的数据测试下（数据量的多少和数据的大小）所消耗的时间，及怎样提高排序的效率   二. 基本要求：精确测试上述各种排序对同样的数据进行排序所消耗的时间，分析各种排序的在不同情况下的优劣      三. 测试数据： 每次进行排序的数据量，数据的范围可有用户输入，确定数据范围和数量后，由系统自动产生随机数      四. 算法思想： 1 直接插入排序：最简单的排序方法，基本思想是将一个记录插入到已排好的有序表中，从而得到一个新的，记录数增1的有序表2 折半插入排序：插入排序的基本插入是在一个有序表中进行查找和插入，这个查找可利用折半查找来实现，即为折半插入排序3 希尔排序：先将整个待排记录分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体记录进行一次直接插入排序4 冒泡排序：首先将第一个记录的关键字和第二个记录的关键字进行比较，若为逆序，则将两个记录交换，然后比较第二个记录和第三个记录的关键字。依此类推，直到第N-1和第N个记录的关键字进行过比较为止。上述为第一趟排序，其结果使得关键字的最大纪录被安排到最后一个记录的位置上。然后进行第二趟起泡排序，对前N-1个记录进行同样操作。一共要进行N-1趟起泡排序5 快速排序：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，已达到整个序列有序6 简单选择排序：通过N-I次关键字间的比较，从N-I+1个记录中选出关键字最小的记录，并和第I（1<=I<=N）个记录交换7 堆排序：在堆排序的算法中先建一个大顶堆，既先选得一个关键字作为最大的记录并与序列中最后一个记录交换，然后对序列中前N-1记录进行选择，重新将它调整成一个大顶堆，如此反复直到排序结束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,long 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,long n) 堆排序，调用API函数计算堆排序所消耗的时间4 void RadixSort(long p,long n,int radix) 基数排序，调用API相关函数计算基数排序所消耗的时间5 void Print(long p,long n) 输出排序结果，用来测试排序函数的正确性六. 数据结构：程序流程图程序开始输出提示：输入将要产生随机数的个数和范围调用随机数函数，产生相应的随机数直接插入排序，并测试其时间消耗折半插入排序，并测试其时间消耗希尔排序，并测试其时间消耗快速排序，并测试其时间消耗冒泡排序，并测试其时间消耗双向起泡排序，并测试其时间消耗简单选择排序，并测试其时间消耗堆排序，并测试其时间消耗基数排序，并测试其时间消耗是否继续程序结束七. 源程序： #include <iostream>#include <ctime> 产生随机数#include <windows.h> 调用计算时间的函数#include <cmath>using namespace std;产生随机数，输入产生随机数的个数，范围，即可产生待排数据void Random(long p,long n,long a,long b)long max,min;if(a>b)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; 输出排序后的结果；用已检测排序的正确，是否能正确排序void Print(long p,long n)cout<<"n排序后的结果："for(long i=1;i<=n;i+)cout<<pi<<' '把字符数组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; QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart);for(long i=2;i<=n;+i)if(qi<qi-1) q0=qi;qi=qi-1;for(long j=i-2;q0<qj;-j)qj+1=qj;qj+1=q0;LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;/ Print(q,n); cout<<"n直接插入排序时间消耗："<<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; QueryPerformanceCounter(&m_liPerfStart); for(long i=2;i<n;i+) q0=qi; long low=1; long high=i-1; while(low<=high) long m=(low+high)/2; if(q0<qm) high=m-1; else low=m+1; for(long j=i-1;j>=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;/ Print(q,n);cout<<"n折半插入排序时间消耗："<<time<<" MS"delete q; 希尔排序：排序并测试排序过程中的时间消耗void ShellInsert(long q,long dk,long n)for(long i=dk+1;i<=n;i+)if(qi<qi-dk)q0=qi;for(long j=i-dk;j>0&&(q0<qj);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_liPerfFreq); 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_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart; Print(q,n);cout<<"n希尔排序时间消耗："<<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; QueryPerformanceCounter(&m_liPerfStart); for(long j=1;j<=n;j+)for(long i=1;i<=n-j;i+)if(qi>qi+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);cout<<"n冒泡排序时间消耗："<<time<<" MS"delete q;双向起泡排序：排序并测试排序过程中的时间消耗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(low<high&&change)change=0;for(long i=low;i<high;i+)if(qi>qi+1)long t=qi;qi=qi+1;qi+1=t;change=1;high-;for(i=high;i>low;i-)if(qi<qi-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);cout<<"n双向起泡排序时间消耗："<<time<<" MS"delete q;递归形式的快速排序：排序并测试排序过程中的时间消耗long Partition(long a,long low,long high)int m=alow;while(low<high)while(low<high&&ahigh>=m)-high;alow=ahigh;while(low<high&&alow<=m)+low;ahigh=alow;alow=m;return low;void Qsort(long a,long low,long high)if(low<high)int pivotloc=Partition(a,low,high);if(pivotloc-low<high-pivotloc)/改进后的快速排序效率确实提高了 /先对长度短的那一部分进行排序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=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);cout<<"n快速排序时间消耗："<<time<<" MS"delete q;/ Print(q,n);非递归形式的快速排序：用栈的性质void QuickSort(long 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(left<right)top+;Stop.left=left;Stop.right=right;while(top>0)start=Stop.left;end=Stop.right;top-;long pivot=qstart;i=start;j=end;for(; ;)while(i<j&&qi<=pivot)i+;while(i<j&&pivot<qj)j-;if(i<j)temp=qi;qi=qj;qj=temp;i+;j-;elsebreak;qj=pivot;if(start<i-1)top+;Stop.left=start;Stop.right=i-1;if(i+1<end)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_liPerfFreq); 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(qj<qk)k=j;long t=qk;qk=qi;qi=t;LARGE_INTEGER liPerfNow=0; QueryPerformanceCounter(&liPerfNow); double time=liPerfNow.QuadPart - m_liPerfStart.QuadPart; time/=m_liPerfFreq.QuadPart;/ Print(q,n);cout<<"n简单选择排序时间消耗："<<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(j<m&&qj<qj+1)+j;if(rc>=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; QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart); for(long i=n/2;i>0;i-)HeapAdjust(q,i,n);for(i=n;i>1;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.QuadPart; time/=m_liPerfFreq.QuadPart;/ Print(q,n);cout<<"n堆排序时间消耗："<<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; QueryPerformanceFrequency(&m_liPerfFreq); LARGE_INTEGER m_liPerfStart=0; QueryPerformanceCounter(&m_liPerfStart); for(int t=1;t<=radix;t+)for(int k=0;k<=10;k+)/?p1=new Radix;headk=p1;headk->next=0; tailk=headk;for(long i=1;i<=n;i+) long m=qi/L;long k=m%10;p1=new Radix;p1->rc=qi;p1->next=0;p2=headk;while(p2->next!=0)p2=p2->next;p2->next=p1;tailk=p1;for(k=0;k<10;)for(long j=k+1;j<10;j+)if(headj->next)/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.QuadPart; time/=m_liPerfFreq.QuadPart; /*Print(q,n);*/cout<<"n基数排序时间消耗："<<time<<" MS"delete q;int main() 主函数char choice;docout<<"排序时间消耗测试n"cout<<"输入随机数的个数，和范围："long n,a,b;cin>>n>>a>>b;long *p=new longn+1;Random(p,n,a,b);/ cout<<"产生的随机数："/for(int i=1;i<=n;i+)/cout<<pi<<' 'if(a>b)b=a;int radix=0;while(b)b=b/10;radix+; StraightInsertionSort(p,n);/直接插入排序BinaryInsertionSort(p,n);/折半插入排序/ ListInsertionSort(p,n);/表插入排序ShellSort(p,n);/希尔排序 QuickSort(p,n);/快速排序/ QuickSort(p,1,n); BubbleSort(p,n);/冒泡排序 BubbleSort_2(p,n);/双向起泡排序SelectSort(p,n);/简单选择排序HeapSort(p,n);/堆排序RadixSort(p,n,radix);/基数排序delete p;cout<<"nt继续请按Y或y："cin>>choice;while(choice='Y'|choice='y'); return 0; 八. 测试情况，运行结果分行： 从上述几组测试数据分析得： 当数据量大且数据范围较大进行排序时：希尔排序，快速排序，堆排序的时间消耗比较少，希尔，快排，堆排的效率都比较高当数据量大且范围较小时进行排序时：希尔排序的效率较高当数据量小且范围较小时进行排序时：直接插入排序效率较高当数据量小且范围较大时进行排序时：直接插入排序效率较高，其他排序效率都比较低，并且相差不大当数据范围较小时，基数排序效率有很大提高快速排序提高效率的方法:在一趟排序之后比较分割所得两部分的长度，且先对长度短的子序列中的记录进行快排，可使栈的最大深度可将为O（logn）。从而提高效率九体会： 这次课程设计最大的体会就是，编程主要工作应该是程序的调试，我在调试程序的时间花的最多，还有程序的构思，好的算法编程技巧能经受大量数据的考验高效率好的程序 这次编程遗憾也不少：在测试代码的时间消耗时，只是反复调用头文件提供的函数，自我感觉代码有点冗余，也想不出来什么好的方法。和那些经典代码比起来，自己真是差的太远。二十七