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

综合排序软件 1．题目： 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。 1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。 2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。 3)如果采用4种或4种以上的方法者，可适当加分。 2. 课题研究的目的和意义： 排序是计算机程序设计中一种重要的操作，它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。目前我们已经掌握的排序方法很多，每一种方法都有其各自的优点，通过对各种算法的研究以及不同方法之间的比较研究，能让我们可以从更高的层次上理解和掌握排序算法，而且能够在不同环境下，根据数据的不同特点，选择不同的方法。因此，我们开展对排序算法的研究将更有利于我们解决问题，提高效率。 3.可行性论证： （1）就算法本身而言，它们是稳定的，时间复杂度是有限阶的，每种算法的思想是可行的。 （2）处理数据（20000个随机数）是有限的，并且同过这些排序方法可以实现排序。 4．课程总体设计方案： （1）对小组内个成员进行分配，每位小组成员负责一种算法。 （2）讨论研究流程：制定算法的总体思路,查阅相关资料，按照预先分配编写程序，程序整合，实验并修改。 （3）对程序中的排序方法进行扩充，小组集体研究了简单选择排序，希尔排序，快速排序三种方法。 （4）最后总结。 5.若干关键技术及设计结果 源程序： #include stdio.h #include stdlib.h #include time.h #define MAXSIZE 2300 typedef int KeyType; typedef int InfoType; typedef struct{ KeyType key; InfoType otherinfo; }RcdType; typedef struct{ RcdType r[MAXSIZE+1]; long length; }SqList; SqList CreaList () {//建立 long i; SqList L; for(i=1;iMAXSIZE+1;i++) { L.r[i].key=(rand()%MAXSIZE); } L.length=MAXSIZE; return L; }//建立 void PrintfList(SqList * L) {//打印 long i; for(i=1;iMAXSIZE+1;i++) { printf(%8d,L-r[i].key); } } //1折半 SqList BInsertSort(SqList L,long bj1[],long jh1[]) { bj1[0]=0;jh1[0]=0; long i,j,low,high,k; for(i=2; i=L.length; ++i) { L.r[0]=L.r[i]; jh1[0]+=1; low=1;high=i-1; while(low=high) { k=(low+high)/2; if(L.r[0].key L.r[k].key) {high=k-1;bj1[0]+=1;} else {low=k+1;bj1[0]+=1;} } for(j=i-1;j=high+1;j--) { L.r[j+1]=L.r[j];jh1[0]+=1;} L.r[high+1]=L.r[0]; jh1[0]+=1; } return L; }//折半 //2直接 SqList InsertSort(SqList L,long bj2[],long jh2[]) { long j,k; bj2[0]=0; jh2[0]=0; for(k=2; k=L.length; ++k) if(L.r[k].key L.r[k-1].key ) { bj2[0]+=1; L.r[0] = L.r[k]; L.r[k]=L.r[k-1]; jh2[0]+=2; for(j=k-2; L.r[0].keyL.r[j].key; --j) { L.r[j+1]=L.r[j]; jh2[0]+=1;bj2[0]+=1;