数据库课程设计综合排序软件.doc

综合排序软件1题目： 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 3)如果采用4种或4种以上的方法者，可适当加分。2. 课题研究的目的和意义： 排序是计算机程序设计中一种重要的操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。目前我们已经掌握的排序方法很多，每一种方法都有其各自的优点，通过对各种算法的研究以及不同方法之间的比较研究，能让我们可以从更高的层次上理解和掌握排序算法，而且能够在不同环境下，根据数据的不同特点，选择不同的方法。因此，我们开展对排序算法的研究将更有利于我们解决问题，提高效率。 3.可行性论证：（1）就算法本身而言，它们是稳定的，时间复杂度是有限阶的，每种算法的思想是可行的。（2）处理数据（20000个随机数）是有限的，并且同过这些排序方法可以实现排序。4课程总体设计方案： （1）对小组内个成员进行分配，每位小组成员负责一种算法。 （2）讨论研究流程：制定算法的总体思路,查阅相关资料，按照预先分配编写程序，程序整合，实验并修改。 （3）对程序中的排序方法进行扩充，小组集体研究了简单选择排序，希尔排序，快速排序三种方法。 （4）最后总结。5.若干关键技术及设计结果源程序：#include #include #include #define MAXSIZE 2300typedef int KeyType;typedef int InfoType;typedef struct KeyType key; InfoType otherinfo;RcdType; typedef struct RcdType rMAXSIZE+1; long length;SqList;SqList CreaList () /建立long i; SqList L; for(i=1;iMAXSIZE+1;i+) L.ri.key=(rand()%MAXSIZE); L.length=MAXSIZE; return L; /建立void PrintfList(SqList * L)/打印long i; for(i=1;iri.key); /1折半SqList BInsertSort(SqList L,long bj1,long jh1)bj10=0;jh10=0; long i,j,low,high,k; for(i=2; i=L.length; +i) L.r0=L.ri; jh10+=1;low=1;high=i-1;while(low=high) k=(low+high)/2; if(L.r0.key =high+1;j-) L.rj+1=L.rj;jh10+=1; L.rhigh+1=L.r0; jh10+=1; return L;/折半 /2直接SqList InsertSort(SqList L,long bj2,long jh2) long j,k;bj20=0;jh20=0;for(k=2; k=L.length; +k) if(L.rk.key L.rk-1.key ) bj20+=1; L.r0 = L.rk; L.rk=L.rk-1; jh20+=2; for(j=k-2; L.r0.key=2;j-)for(i=1;iL.ri+1.key) L.r0=L.ri;L.ri=L.ri+1;L.ri+1=L.r0;jh30+=3;bj30+=1; else bj30+=1;return L;/冒泡/4堆排序 SqList HeapAdjust(SqList L,int s,int m ,long bj4,long jh4) /建堆 RcdType rc; long j; rc=L.rs; for(j=2*s;j=m;j*=2) if(jm&L.rj.keyL.rj+1.key) j+; if(jm) bj40+=1; if(L.rj.key0;i-)L=HeapAdjust(L,i,L.length,bj4,jh4);for(i=L.length;i1;i-)L.r0=L.ri;L.ri=L.r1;L.r1=L.r0;jh40+=3;L=HeapAdjust(L,1,i-1,bj4,jh4); return L;/堆排序 /5简单选择排序SqList SeledSort(SqList L,long bj5,long jh5) long i,j,k;bj50=0;jh50=0;for(i=1; i=L.length; +i) j=i; for(k=i+1; k=L.length; +k) if(L.rk.keyL.rj.key) j=k;bj50+=1; if(i!=j) L.r0 = L.ri; L.ri = L.rj; L.rj = L.r0; jh50+=3; else bj50+=1; return L;/简单选择排序/6希尔SqList ShellSort(SqList L,int dk ,long bj6,long jh6) long i,j; for(i=1+dk;i=L.length;i+) if(L.ri.key0&L.r0.key0)bj60+=1; L.rj+dk=L.r0; jh60+=1; else bj60+=1; return L; SqList ShallSort(SqList L,long bj6,long jh6)jh60=0; bj60=0;int dlta=64,32,16,8,4,2,1; long i; for(i=0;ir0.key=L-rlow.key; pivotkey=L-rlow.key;jh70+=2; while(lowhigh) while(lowhigh & pivotkeyrhigh.key) -high;if(lowrlow.key=L-rhigh.key;jh70+=1; while(lowrlow.key)=pivotkey) +low;if(lowrhigh.key=L-rlow.key;jh70+=1; L-rlow.key=L-r0.key ;jh70+=1; return low;void QSort(SqList * L,int low,int high,long bj7,long jh7 ) long pivotloc; if(lowhigh) pivotloc=Partition(L,low,high, bj7,jh7); QSort(L,low,pivotloc-1, bj7,jh7 ); QSort(L,pivotloc+1,high, bj7,jh7 ); SqList QuickSort(SqList L,long bj7,long jh7 ) bj70=0;jh70=0; QSort(&L,1,L.length, bj7,jh7 ); return L;/快速void time( void )/时间 struct tm *newtime; char tmpbuf128; time_t lt1; time( <1 ); newtime=localtime(<1); strftime( tmpbuf, 128, 今天是： %A, day %d of %B in the year %Y.n, newtime); printf(tmpbuf);void time1(void)/时间struct tm *ptr;time_t lt;lt =time(NULL);ptr=gmtime(<);printf( 现在是：);printf(ctime(<);main() long i,n,k; SqList L,Q; long bj11,bj21,bj31,bj41,bj51,bj61,bj71;/比较 long jh11,jh21,jh31,jh41,jh51,jh61,jh71;/交换 clock_t start1,start2,start3, start4,start5, start6,start7;/开始 clock_t finish1,finish2,finish3,finish4,finish5,finish6,finish7;/结束 /long start,finish; long m,t; SqList CreaList (); printf(n*n); time(); time1(); printf(*n); printf(20000个数没能实现。暂时只实现2400个数。希望老师能给分析一下。谢谢！);start1: printf(n请选择：n1.进入；n2.退出。n); scanf(%d,&n); if(n=1) start: printf(n请选择：n0.全部排序；n1.折半插入排序；n2.直接插入排序；n3.冒泡排序；n4.堆排序；); printf(n5.简单选择排序；n6.希尔排序；n7.快速排序；n8.退出。n); scanf(%d,&k); if(k!=8&k!=0) printf(是不是显示结果：n1.显示。2。不显示。n); scanf(%d,&m); switch(k) case 0: Q=CreaList(); L=Q; printf(是不是显示生成的数：n1.显示。2。不显示。n); scanf(%d,&m); if(m=1) printf(n20000个随机的数为:n); PrintfList(&L) ; start1=clock(); L=BInsertSort(L,bj1,jh1); if(m=1) printf(n20000个排好序的数为:n); PrintfList(&L); finish1=clock(); printf(n1.用折半插入排序法用的时间为%f秒；,(double)(finish1 - start1)/CLOCKS_PER_SEC); printf(n 交换%ld次,比较%ld次。n,jh10,bj10); L=Q; start2=clock(); L=InsertSort(L,bj2,jh2); finish2=clock(); printf(n2.用直接插入排序法用的时间为%f秒；,(double)(finish2 - start2)/CLOCKS_PER_SEC); printf(n 交换%ld次,比较%ld次。n,jh20,bj20); L=Q; start3=clock(); L=Bubble(L,bj3,jh3); finish3=clock(); printf(n3.用冒泡排序法用的时间为%f秒；,(double)(finish3 - start3)/CLOCKS_PER_SEC); printf(n 交换%ld次,比较%ld次。n,jh30,bj30); L=Q; start4=clock(); L=HeapSort(L,bj4,jh4); finish4=clock(); printf(n4.用堆排序法用的时间为%f秒；,(double)(finish4 - start4)/CLOCKS_PER_SEC); printf(n 交换%ld次,比较%ld次。n,jh40,bj40); L=Q; start5=clock(); L=SeledSort(L,bj5,jh5); finish5=clock(); printf(n5.用简单选择排序法用的时间为%f秒；,(double)(finish5-start5)/CLOCKS_PER_SEC); printf(n 交换%ld次,比较%ld次。n,jh50,bj50); L=Q; start6=clock(); L=ShallSort(L,bj6,jh6); finish6=clock(); printf(n6.用希尔排序法用的时间为%f秒；,(double)(finish6-start6)/CLOCKS_PER_SEC); printf(n 交换%ld次,比较%ld次。n,jh60,bj60); L=Q; start7=clock(); L=QuickSort(L,bj7,jh7); finish7=clock(); printf(n7.用快速排序法用的时间为%f秒；,(double)(finish7-start7)/CLOCKS_PER_SEC); printf(n 交换%ld次,比较%ld次。n,jh70,bj70); goto start; case 1: L=CreaList(); start1=clock(); printf(%fn,start1); L=BInsertSort(L,bj1,jh1); finish1=clock(); printf(%fn,finish1); if(m=1) printf(n20000个用折半插入排序法排好序的数为:n); PrintfList(&L); printf(n用折半插入排序法用的时间为%f秒；,(double)(finish1 - start1)/CLOCKS_PER_SEC); printf(n交换%ld次,比较%ld次。n,jh10,bj10); goto start; case 2: L=CreaList(); start2=clock(); L=InsertSort(L,bj2,jh2); finish2=clock(); if(m=1) printf(n20000个用直接插入排序法排好序的数为:n); PrintfList(&L); printf(n用直接插入排序法用的时间为%f秒；,(double)(finish2 - start2)/CLOCKS_PER_SEC); printf(n交换%ld次,比较%ld次。n,jh20,bj20); goto start; case 3: L=CreaList(); start3=clock(); L=Bubble(L,bj3,jh3); finish3=clock(); if(m=1) printf(n20000个用冒泡排序法排好序的数为:n); PrintfList(&L); printf(n用冒泡排序法用的时间为%f秒；,(double)(finish3 - start3)/CLOCKS_PER_SEC); printf(n交换%ld次,比较%ld次。n,jh30,bj30); goto start; case 4: L=CreaList(); start4=clock(); L=HeapSort(L,bj4,jh4); finish4=clock(); if(m=1) printf(n20000个用堆排序法排好序的数为:n); PrintfList(&L); printf(n用堆排序法用的时间为%f秒；,(double)(finish4 - start4)/CLOCKS_PER_SEC); printf(n交换%ld次,比较%ld次。n,jh40,bj40); goto start; case 5: L=CreaList(); start5=clock(); L=SeledSort(L,bj6,jh6); finish5=clock(); if(m=1) printf(n20000个用简单选择排序法排好序的数为:n); PrintfList(&L); printf(n用简单选择排序法用的时间为%f秒；,(double)(finish5 - start5)/CLOCKS_PER_SEC); printf(n交换%ld次,比较%ld次。n,jh50,bj50); goto start; case 6: L=CreaList(); start6=clock(); L=ShallSort(L,bj6,jh6); finish6=clock(); if(m=1) printf(n20000个用希尔排序法排好序的数为:n); PrintfList(&L); printf(n用希尔排序法用的时间为%f秒；,(double)(finish6 - start6)/CLOCKS_