数据结构c语言设计,比较各种排序方法的效率

选择四种以上的排序方法，采用随机生成的数据，登记并比较各个排序方法的比较次数和交换次数，验证各个排序方法效率的理论分采用顺序存储结构，登记多次结果各种排序方法的平均效率的比较。1、课程设计说明书(所使用的数据结构说明、程序流程图、功能模块指导教师签名日期年月日系主任审核日期年月日 各种排序算法的N-S图 31.总流程图模块 3 3.冒泡排序模块 54.简单选择模块 5 1.直接插入排序函数 72.冒泡排序函数 83.简单选择排序函数 94.快速排序函数 105.堆排序函数 11 8.主函数 16 4.1登陆画面 204.2各种排序结果显示画面(100个数据随机生成5次)…21 机生成100次) 24 6.1课程设计中遇到的主要问题和解决方法 246.2本程序的创新和得意之处 256.3设计中存在的不足及改进的设想 256.4本次课程设计的感想和心得体会 251一.算法分析直接插入排序：将记录插入到已排好序的有序表中，得到一个新的，冒泡排序：是基于交换排序的一种算法。它是依次两两比较待排序元素；若为逆序(递增或递减)则进行交换，将待排序元素列中的最大(小)关键字交换到最后位置，直到全部元素序：通过一趟排序将待排记录分割成独立的两部分，其中一部关键字均比另一部分记录的关键字小，则可分别使记录序列按关键字非递减有序排列，则在堆排序的算法中L2C的基础语法一起2直接插入函数是一个将记录插入到已排好序的静态数组的应用L用3TF入随机生成的次数for(i=0;i<t;i++)4forfor(i=2;i<=n;++i)keyRikeyTR[0]=R[i];R[i]=R[i-1];for(j=i-2;R[0].key<R[j].key;--j)R[j+1]=R[j];b[0]++;if(j!=0)bT5k=j;if(i!=kk=j;if(i!=k)Tfor(j=1;j<=n-i;j++)yTR[j]<=>R[j+1]forfor(i=1;i<n;i++)k=i;for(j=i+1;j<=n;j++)eyRkkeyTRkR[i];b[2]+=3;6intinti;if(low<high)T intinti；ifor(i=n;i>1;--i)R[1]<=>R[i] 7程序#include<stdio.h>#include<stdlib.h>#include<time.h>#include<windows.h>#defineMAXSIZE50000typedefintkeytype键字类型为整型typedefstructkeytypekey;datatypeRMAXSIZE构体数组intab定义比较次数和交换次数doublec[5],Ttime;插入排序voidInsertSortdatatypeR],intn)//直接插入排序{for(i=2;i<=n;++i){ifRikeyRi].key){8R[0]=R[i];//复制为哨兵R[i]=R[i-1];b[0]+=2;for(j=i-2;R[0].key<R[j].key;--j)b[0]++;a;}ifja;R[j+1]=R[0];//插入到正确位置b[0]++;}}}序voidBubble_Sort(datatypeR[],intn)//冒泡排序{for(i=1;i<=n-1;i++)for(j=1;j<=n-i;j++){9a;if(R[j].key>R[j+1].key){R[0]=R[j];R[j+1]=R[0];b[1]+=3;}}}>简单选择排序voidSelectSortdatatypeR[],intn)//简单选择排序{for(i=1;i<n;i++){for(j=i+1;j<=n;j++){a;j{}}}winthigh{wpivotkeyRlowkey轴记录关键字whilelowhigh){whilelow<high&&R[high].key>=pivotkey)while(low<high&&R[low].key<R[0].key)}{{}{typercintjy{RsRjb]++;}srcvoidHeapSortdatatypeRintn序{fori=n/2;i>0;--i)fori=n;i>1;--i){}voidPridatatypeRintn函数{printfdRi.key);ntfn}voidrandselectintn数{LARGE_INTEGERm_liPerfFreq={0};LARGE_INTEGERmliPerfStart0};RGEINTEGERliPerfNowRMAXSIZERMAXSIZERMAXSIZE;foriini+){printfdRi.key=rand()%n);}ntfnRikeyRikeyRikeyRikeyRikeyRikeyRikeyRikeyrformanceFrequencymliPerfFreqQueryPerformanceCountermliPerfStart时开始QueryPerformanceCounterliPerfNow束liPerfFreqQuadPartprintf的顺序:\n");nyPerformanceFrequencymliPerfFreqQueryPerformanceCountermliPerfStart时开始BubbleSortRn);//冒泡排序QueryPerformanceCounterliPerfNow束liPerfFreqQuadPartprintf的顺序:\n");RnrformanceFrequencymliPerfFreqQueryPerformanceCountermliPerfStart时开始SelectSortRn序QueryPerformanceCounterliPerfNow束liPerfFreqQuadPartprintf顺序:\n");RnrformanceFrequencymliPerfFreqQueryPerformanceCountermliPerfStart时开始QSortRn速排序QueryPerformanceCounterliPerfNow束liPerfFreqQuadPartprintf的顺序:\n");RnrformanceFrequencymliPerfFreqQueryPerformanceCountermliPerfStart时开始HeapSortRn//堆排序QueryPerformanceCounterliPerfNow束liPerfFreqQuadPartprintf顺序:\n");Rn}{ntfnntfnntfnprintf--------------*\n");--------------*\n");n{n}ntfnntfn----------*\n");----------*\n");tntfn{electnprintf("统计第%d次随机数据的比较次数和交换次数为\n",i+1);printf-----------------------------------------n;printf("********排序方式比较次数交换次数printf********直接泡dtdtfnab,c[0]);dtdtfnab1],c[1]);冒择printf("********简单dtdtfnab,c[2]);intfnprintf("********快速选排序dtdtfnab3],c[3]);printf("********堆排dtdtfnabc[4]);printf-------------}printf平均比较次数和平均移动次数为\n");printf-----------------------------------------n;printf("********排序方式平均比较次数平均交换次数直接%-10d\t%-10d\t%-12f\n",a[0]/t,b[0]/t,c[0]/t);printf("********冒泡%-10d\t%-10d\t%-12f\n",a[1]/t,b[1]/t,c[1]/t);printf("********简单选择%-10d\t%-10d\t%-12f\n",a[2]/t,b[2]/t,c[2]/t);printf("********快速排序%-10d\t%-10d\t%-12f\n",a[3]/t,b[3]/t,c[3]/t);printf("********堆排序%-10d\t%-10d\t%-12f\n",a[4]/t,b[4]/t,c[4]/t);}使用.(1)课程设计中遇到的主要问题和解决方法：排序算法的效率都有些挑战，在这个课程设计中，主要是对于一些基本的知识，熟悉程度不够，特别是对于比较次数和交换次数的统计，刚开始是跟理论值相差甚大，然后自己看了好几遍的书和上网看了一的依据才把问题在编译时有时会出现较多的出错提示，这时要理解提示信息的含义，并据此改正错误。当编译提示的出错信息不止一条时，只须先注重其中第一条，每次改完一个错误后先编译一次，因为从第二个错误开始的若干错误很可能是随带错误，只要更正了第一个错误可能就没(2)我的创新和得意之处：是伪随机数,结果都不同，是可以随意输入随机生成数据的个数，程序执行时可以输入大量数据，有利于精确求取比较次数和交换次数。